1.使用链表或者数组来保存图的结构,bfs和dfs(用函数嵌套来解决记忆问题)
''' 图的表示:算法导论22章 图又2中表示方式: 1.是链表:一个节点跟他相连的节点都用一个链表穿起来. 然后n个节点就用n个链表来储存这个图的信息 2.是矩阵:用节点数n,n*n的矩阵来储存,两个点如果有边就存1. 优势和劣势: 1.链表:适用于稀疏图,但是很难判断一个边是否存在 2.矩阵:反之. `''' ''' 拓扑排序 一．定义 对一个有向无环图(Directed Acyclic Graph简称DAG)G进 行拓扑排序(Topological Sort),是将G中所有顶点排成一个线 性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在 线性序列中出现在v之前。通常将这样的线性序 列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。''' ''' 用链表来拓扑排序 入度是图论算法中重要的概念之一。它通常指有向 图中某点作为图中边的终点的次数之和。''' ''' 入度表 对于DAG的拓扑排序，显而易见的办法!!!!!!!! 这是一个好方法： 找出图中0入度的顶点； 依次在图中删除这些顶点，删除后再找出0入度的顶点； 然后再删除……再找出…… 直至删除所有顶点，即完成拓扑排序 为了保存0入度的顶点，我们采用数据结构栈（亦可用队列）；算法的可视化可参看这里。 图用邻接表（adjacency list）表示，用数组inDegreeArray[]记录结点的入度变化情况。C实现：''' class Graph(): def __init__(self,n): self.vertex_num=n self.edge=[] for i in range(n):#2-dim-empty list cannot use *99 self.edge.append([]) self.indegree=[0]*n self.count=0#作为dfs里面的flag self.whether_exist=[0]*self.vertex_num #vertex_index=0,1,2,3,4.... def addedge(self,n,m): self.edge[n].append(m) self.indegree[m]+=1 def topological_sort(self): a=[] b=len(self.indegree) while (b): for i in range(len(self.indegree)): if 0 not in self.indegree: return False if self.indegree[i]==0: a.append(i) self.indegree[i]-=1 for j in self.edge[i]: self.indegree[j]-=1 b-=1 break def bfs(self,root):#board first search广度优先遍历 #广度优先遍历,深度优先遍历都是只从一个root点出发,遍历跟他有关系的点. #所以不连通的图需要多次从不同的root出发进行遍历才行.那个后话了. #这个很麻烦,可不可以做一个count让函数第一次被调用时候才跑这句话. #可以给class加一个变量.写在__init__里面 #好像广度搜索不能写递归,一些递归就深度了. self.output=[] if root not in self.output: self.output.append(root) tmp=self.edge[root] tmp2=[] while 1: for i in range(len(tmp)): if tmp[i] not in self.output: self.output.append(tmp[i]) c=[] for i in range(len(tmp)): for j in range(len(self.edge[tmp[i]])): if self.edge[tmp[i]][j] not in self.output: c+=self.edge[tmp[i]] if c==[]: return self.output tmp=c def dfs(self,root):#类似也弄好dfs这次可以递归了. #跟树的遍历不同,图需要去重,很麻烦. #还是不行,可能必须要实现知道节点的数目才行.不然没法开记忆是否存储的数组 self.tmp=[]#dfs中间变量 #用函数体外的self.tmp来做记忆,用嵌套函数来解决递归函数返回值问题 def min_dfs(root):#这个函数嵌套不用self,可以只是一般函数 b=[] if root not in self.tmp: self.tmp.append(root) for i in self.edge[root]: if i not in self.tmp: b.append(i) c=[] for i in b: #这步体现的递归.和dfs c+=(min_dfs(i)) tmp=[root]+c return tmp min_dfs(root) return self.tmp g=Graph(60) g.addedge(1,2) g.addedge(1,3) g.addedge(2,6) g.addedge(2,5) g.addedge(3,6) g.addedge(4,3) g.addedge(3,4) print (g.dfs(1)) #[1, 2, 6, 5, 3, 4] ''' 下面继续学习图:发现博客上面的比算法导论上面的方法更先进. http://blog.csdn.net/moshenglv/article/details/72954701''' ''' 强连通图（Strongly Connected Graph）是指在有向图G中，如果对 于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径， 则称G是强连通图。''' ''' 1.图的存储结构: 1.邻接矩阵 2.邻接矩阵是一种不错的图存储结构，但是对于边数相对较少的图， 这种结构存在空间上的极大浪费， 因此找到一种数组与链表相结合的存储方法称为邻接表。 3. 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易 找到以v为尾 的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同 的，因此，在有向图应用中，十字链表是非常好的数据结构模型。(相当复杂) ''' ''' 下面先写bfs'''
2.创新了一种求有向图强联通分支的算法(可能别人也早给出过)
''' 图的表示:算法导论22章 图又2中表示方式: 1.是链表:一个节点跟他相连的节点都用一个链表穿起来. 然后n个节点就用n个链表来储存这个图的信息 2.是矩阵:用节点数n,n*n的矩阵来储存,两个点如果有边就存1. 优势和劣势: 1.链表:适用于稀疏图,但是很难判断一个边是否存在 2.矩阵:反之. `''' ''' 拓扑排序 一．定义 对一个有向无环图(Directed Acyclic Graph简称DAG)G进 行拓扑排序(Topological Sort),是将G中所有顶点排成一个线 性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在 线性序列中出现在v之前。通常将这样的线性序 列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。''' ''' 用链表来拓扑排序 入度是图论算法中重要的概念之一。它通常指有向 图中某点作为图中边的终点的次数之和。''' ''' 入度表 对于DAG的拓扑排序，显而易见的办法!!!!!!!! 这是一个好方法： 找出图中0入度的顶点； 依次在图中删除这些顶点，删除后再找出0入度的顶点； 然后再删除……再找出…… 直至删除所有顶点，即完成拓扑排序 为了保存0入度的顶点，我们采用数据结构栈（亦可用队列）；算法的可视化可参看这里。 图用邻接表（adjacency list）表示，用数组inDegreeArray[]记录结点的入度变化情况。C实现：''' class Graph(): def __init__(self,n): self.vertex_num=n self.edge=[] for i in range(n):#2-dim-empty list cannot use *99 self.edge.append([]) self.indegree=[0]*n self.count=0#作为dfs里面的flag self.whether_exist=[0]*self.vertex_num #vertex_index=0,1,2,3,4.... def addedge(self,n,m): self.edge[n].append(m) self.indegree[m]+=1 def Transpose(self): self.edgenew=[] n=self.vertex_num for i in range(n):#2-dim-empty list cannot use *99 self.edgenew.append([]) for i in range(len(self.edge)): if self.edge[i]!=[]: tmp=self.edge[i] for j in tmp: self.edgenew[j].append(i) new=Graph(n)#重新分配一个对象,这样就跟以前不干扰了 new.edge=self.edgenew return new def topological_sort(self): a=[] b=len(self.indegree) while (b): for i in range(len(self.indegree)): if 0 not in self.indegree: return False if self.indegree[i]==0: a.append(i) self.indegree[i]-=1 for j in self.edge[i]: self.indegree[j]-=1 b-=1 break def bfs(self,root):#board first search广度优先遍历 #广度优先遍历,深度优先遍历都是只从一个root点出发,遍历跟他有关系的点. #所以不连通的图需要多次从不同的root出发进行遍历才行.那个后话了. #这个很麻烦,可不可以做一个count让函数第一次被调用时候才跑这句话. #可以给class加一个变量.写在__init__里面 #好像广度搜索不能写递归,一些递归就深度了. self.output=[] if root not in self.output: self.output.append(root) tmp=self.edge[root] tmp2=[] while 1: for i in range(len(tmp)): if tmp[i] not in self.output: self.output.append(tmp[i]) c=[] for i in range(len(tmp)): for j in range(len(self.edge[tmp[i]])): if self.edge[tmp[i]][j] not in self.output: c+=self.edge[tmp[i]] if c==[]: return self.output tmp=c def dfs(self,root):#类似也弄好dfs这次可以递归了. #跟树的遍历不同,图需要去重,很麻烦. #还是不行,可能必须要实现知道节点的数目才行.不然没法开记忆是否存储的数组 self.tmp=[]#dfs中间变量 #用函数体外的self.tmp来做记忆,用嵌套函数来解决递归函数返回值问题 def min_dfs(root):#这个函数嵌套不用self,可以只是一般函数 b=[] if root not in self.tmp: self.tmp.append(root) for i in self.edge[root]: if i not in self.tmp: b.append(i) c=[] for i in b: #这步体现的递归.和dfs c+=(min_dfs(i)) tmp=[root]+c return tmp min_dfs(root) return self.tmp def dfs_all(self):#所有节点都跑一边的dfs算法.为了下面的实用强联通分支,我们把 #返回值写作一个数组 n=self.vertex_num c=[] d=[] head=0 while 1: if len(d)==n: return c tmp=self.dfs(head) k=[] for i in tmp: if i not in d: k.append(i) d+=k c.append(k) for i in range(n): if i not in d: head=i break def strong_connected_components(self): a=self#self指的是对象 b=self.Transpose() list1=self.dfs_all() self=b#类还能这么玩,直接类的方法里面改变这个对象 list2=self.dfs_all() def in_the_same(c,d,L): for i in L: if c in i and d in i: return True return False ## import copy ## listnew=[] ## for i in list1: ## if len(i)==1: ## continue ## for j in range(len(i)): ## if in_the_same(i[j],i[j+1],a) !=in_the_same(i[j],i[j+1],b) #突然发现应该用集合来做这个2个list的求交运算. a_set=[] b_set=[] for i in list1: a_set.append(set(i)) for i in list2: b_set.append(set(i)) #然后直接求交即可. c=[] for i in a_set: for j in b_set: d=(i&j) if len(d)!=0: c.append(d) return c #针对有向图要有一个强联通分支算法. #自己设计了一个算法:首先把G的Transpose记做Gt. '''然后,做dfs在G上做一次,类似无向图的dfs分解连通分支的方法,把定点分类, 然后在Gt上再做一次,又把定点分类了.然后我们取2次分类的交即可,就是要的分支. 这里面交指的是2次划分的更细的子划分.也就是比如第一次把12一类,3一类. 第二次把13一类,2一类,那么交就是1,2,3分成3类. ''' g=Graph(7) g.addedge(1,2) g.addedge(2,6) g.addedge(5,2) g.addedge(3,6) g.addedge(4,3) g.addedge(3,4) g.addedge(6,5) print (g.dfs(3)) #[1, 2, 6, 5, 3, 4] print (g.Transpose().edge[1]) print (g.edge[1]) print (g.dfs_all()) print (g.Transpose().dfs_all()) print (g.strong_connected_components())#成功得到了4个分支,并且还是按照标号 #的顺序进行排列的分支.然后随意修改edge,都成功了. ''' 下面继续学习图:发现博客上面的比算法导论上面的方法更先进. http://blog.csdn.net/moshenglv/article/details/72954701''' ''' 强连通图（Strongly Connected Graph）是指在有向图G中，如果对 于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径， 则称G是强连通图。''' ''' 1.图的存储结构: 1.邻接矩阵 2.邻接矩阵是一种不错的图存储结构，但是对于边数相对较少的图， 这种结构存在空间上的极大浪费， 因此找到一种数组与链表相结合的存储方法称为邻接表。 3. 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易 找到以v为尾 的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同 的，因此，在有向图应用中，十字链表是非常好的数据结构模型。(相当复杂) ''' ''' 下面先写bfs'''
算法的好处是理解简单,证明的画画出全部情况看一眼就显然,缺点没有现成的算法kosaraju的效率高.但是没有慢太多,就是慢在了set操作上.
3.最小生成树算法
''' 把图改成无向图:''' import numpy as np import numpy class Graph(): def __init__(self,n): self.vertex_num=n self.edge=[] for i in range(n):#2-dim-empty list cannot use *99 self.edge.append([]) self.indegree=[0]*n self.count=0#作为dfs里面的flag self.weight=numpy.array([None]*n**2).reshape(n,n) self.whether_exist=[0]*self.vertex_num #vertex_index=0,1,2,3,4.... def addedge(self,n,m): self.edge[n].append(m) self.edge[m].append(n) self.indegree[m]+=1 self.indegree[n]+=1 def Transpose(self): self.edgenew=[] n=self.vertex_num for i in range(n):#2-dim-empty list cannot use *99 self.edgenew.append([]) for i in range(len(self.edge)): if self.edge[i]!=[]: tmp=self.edge[i] for j in tmp: self.edgenew[j].append(i) new=Graph(n)#重新分配一个对象,这样就跟以前不干扰了 new.edge=self.edgenew return new def topological_sort(self): a=[] b=len(self.indegree) while (b): for i in range(len(self.indegree)): if 0 not in self.indegree: return False if self.indegree[i]==0: a.append(i) self.indegree[i]-=1 for j in self.edge[i]: self.indegree[j]-=1 b-=1 break def bfs(self,root):#board first search广度优先遍历 #广度优先遍历,深度优先遍历都是只从一个root点出发,遍历跟他有关系的点. #所以不连通的图需要多次从不同的root出发进行遍历才行.那个后话了. #这个很麻烦,可不可以做一个count让函数第一次被调用时候才跑这句话. #可以给class加一个变量.写在__init__里面 #好像广度搜索不能写递归,一些递归就深度了. self.output=[] if root not in self.output: self.output.append(root) tmp=self.edge[root] tmp2=[] while 1: for i in range(len(tmp)): if tmp[i] not in self.output: self.output.append(tmp[i]) c=[] for i in range(len(tmp)): for j in range(len(self.edge[tmp[i]])): if self.edge[tmp[i]][j] not in self.output: c+=self.edge[tmp[i]] if c==[]: return self.output tmp=c def dfs(self,root):#类似也弄好dfs这次可以递归了. #跟树的遍历不同,图需要去重,很麻烦. #还是不行,可能必须要实现知道节点的数目才行.不然没法开记忆是否存储的数组 self.tmp=[]#dfs中间变量 #用函数体外的self.tmp来做记忆,用嵌套函数来解决递归函数返回值问题 def min_dfs(root):#这个函数嵌套不用self,可以只是一般函数 b=[] if root not in self.tmp: self.tmp.append(root) for i in self.edge[root]: if i not in self.tmp: b.append(i) c=[] for i in b: #这步体现的递归.和dfs c+=(min_dfs(i)) tmp=[root]+c return tmp min_dfs(root) return self.tmp def dfs_all(self):#所有节点都跑一边的dfs算法.为了下面的实用强联通分支,我们把 #返回值写作一个数组 n=self.vertex_num c=[] d=[] head=0 while 1: if len(d)==n: return c tmp=self.dfs(head) k=[] for i in tmp: if i not in d: k.append(i) d+=k c.append(k) for i in range(n): if i not in d: head=i break def strong_connected_components(self): a=self#self指的是对象 b=self.Transpose() list1=self.dfs_all() self=b#类还能这么玩,直接类的方法里面改变这个对象 list2=self.dfs_all() def in_the_same(c,d,L): for i in L: if c in i and d in i: return True return False ## import copy ## listnew=[] ## for i in list1: ## if len(i)==1: ## continue ## for j in range(len(i)): ## if in_the_same(i[j],i[j+1],a) !=in_the_same(i[j],i[j+1],b) #突然发现应该用集合来做这个2个list的求交运算. a_set=[] b_set=[] for i in list1: a_set.append(set(i)) for i in list2: b_set.append(set(i)) #然后直接求交即可. c=[] for i in a_set: for j in b_set: d=(i&j) if len(d)!=0: c.append(d) return c #针对有向图要有一个强联通分支算法. #自己设计了一个算法:首先把G的Transpose记做Gt. '''然后,做dfs在G上做一次,类似无向图的dfs分解连通分支的方法,把定点分类, 然后在Gt上再做一次,又把定点分类了.然后我们取2次分类的交即可,就是要的分支. 这里面交指的是2次划分的更细的子划分.也就是比如第一次把12一类,3一类. 第二次把13一类,2一类,那么交就是1,2,3分成3类. ''' def addweight(self,a,b,weight): self.weight[a][b]=weight self.weight[b][a]=weight return #A wise man changes his mind,a fool never. def minimal_spanning_tree(self): #具体方法就是https://blog.csdn.net/luoshixian099/article/details/51908175 #一个是kruskal加点发,prim加边法. new=Graph(6) c=[] num=1 while 1: d=[] for i in range(6): a=new.dfs_all() if len(a)==1: return c d=(np.argwhere(g.weight==num))#这个很方便,返回下表 for t in range(len(d)): k=d[t] i,j=k[0],k[1] e=new.dfs(i) f=new.dfs(j) print (e) print (f) print (set(e)) print (set(f)) if set(e)&set(f)==set(): c.append((i,j)) new.addedge(i,j) print (c) num+=1 break g=Graph(6) g.addedge(0,1) g.addedge(0,2) g.addedge(0,3) g.addedge(1,2) g.addedge(2,3) g.addedge(1,4) g.addedge(2,4) g.addedge(2,5) g.addedge(3,5) g.addedge(4,5) g.addweight(0,1,6) g.addweight(0,3,5) g.addweight(0,2,1) g.addweight(1,4,3) g.addweight(4,5,6) g.addweight(2,1,5) g.addweight(3,2,5) g.addweight(2,4,6) g.addweight(2,5,4) g.addweight(3,5,2) print (g.dfs_all()) print (g.minimal_spanning_tree()) #[(0, 2), (3, 5), (1, 4), (2, 5), (1, 2)]搞定了,trivial问题. #成功得到了4个分支,并且还是按照标号 #的顺序进行排列的分支.然后随意修改edge,都成功了. ''' 下面继续学习图:发现博客上面的比算法导论上面的方法更先进. http://blog.csdn.net/moshenglv/article/details/72954701''' ''' 强连通图（Strongly Connected Graph）是指在有向图G中，如果对 于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径， 则称G是强连通图。''' ''' 1.图的存储结构: 1.邻接矩阵 2.邻接矩阵是一种不错的图存储结构，但是对于边数相对较少的图， 这种结构存在空间上的极大浪费， 因此找到一种数组与链表相结合的存储方法称为邻接表。 3. 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易 找到以v为尾 的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同 的，因此，在有向图应用中，十字链表是非常好的数据结构模型。(相当复杂) ''' ''' 下面先写bfs'''
理论分析版:
''' 把图改成无向图:''' import numpy as np import numpy class Graph(): def __init__(self,n): self.vertex_num=n self.edge=[] for i in range(n):#2-dim-empty list cannot use *99 self.edge.append([]) self.indegree=[0]*n self.count=0#作为dfs里面的flag self.weight=numpy.array([None]*n**2).reshape(n,n) self.whether_exist=[0]*self.vertex_num #vertex_index=0,1,2,3,4.... def addedge(self,n,m): self.edge[n].append(m) self.edge[m].append(n) self.indegree[m]+=1 self.indegree[n]+=1 def Transpose(self): self.edgenew=[] n=self.vertex_num for i in range(n):#2-dim-empty list cannot use *99 self.edgenew.append([]) for i in range(len(self.edge)): if self.edge[i]!=[]: tmp=self.edge[i] for j in tmp: self.edgenew[j].append(i) new=Graph(n)#重新分配一个对象,这样就跟以前不干扰了 new.edge=self.edgenew return new def topological_sort(self): a=[] b=len(self.indegree) while (b): for i in range(len(self.indegree)): if 0 not in self.indegree: return False if self.indegree[i]==0: a.append(i) self.indegree[i]-=1 for j in self.edge[i]: self.indegree[j]-=1 b-=1 break def bfs(self,root):#board first search广度优先遍历 #广度优先遍历,深度优先遍历都是只从一个root点出发,遍历跟他有关系的点. #所以不连通的图需要多次从不同的root出发进行遍历才行.那个后话了. #这个很麻烦,可不可以做一个count让函数第一次被调用时候才跑这句话. #可以给class加一个变量.写在__init__里面 #好像广度搜索不能写递归,一些递归就深度了. self.output=[] if root not in self.output: self.output.append(root) tmp=self.edge[root] tmp2=[] while 1: for i in range(len(tmp)): if tmp[i] not in self.output: self.output.append(tmp[i]) c=[] for i in range(len(tmp)): for j in range(len(self.edge[tmp[i]])): if self.edge[tmp[i]][j] not in self.output: c+=self.edge[tmp[i]] if c==[]: return self.output tmp=c def dfs(self,root):#类似也弄好dfs这次可以递归了. #跟树的遍历不同,图需要去重,很麻烦. #还是不行,可能必须要实现知道节点的数目才行.不然没法开记忆是否存储的数组 self.tmp=[]#dfs中间变量 #用函数体外的self.tmp来做记忆,用嵌套函数来解决递归函数返回值问题 def min_dfs(root):#这个函数嵌套不用self,可以只是一般函数 b=[] if root not in self.tmp: self.tmp.append(root) for i in self.edge[root]: if i not in self.tmp: b.append(i) c=[] for i in b: #这步体现的递归.和dfs c+=(min_dfs(i)) tmp=[root]+c return tmp min_dfs(root) return self.tmp def dfs_all(self):#所有节点都跑一边的dfs算法.为了下面的实用强联通分支,我们把 #返回值写作一个数组 n=self.vertex_num c=[] d=[] head=0 while 1: if len(d)==n: return c tmp=self.dfs(head) k=[] for i in tmp: if i not in d: k.append(i) d+=k c.append(k) for i in range(n): if i not in d: head=i break def strong_connected_components(self): a=self#self指的是对象 b=self.Transpose() list1=self.dfs_all() self=b#类还能这么玩,直接类的方法里面改变这个对象 list2=self.dfs_all() def in_the_same(c,d,L): for i in L: if c in i and d in i: return True return False ## import copy ## listnew=[] ## for i in list1: ## if len(i)==1: ## continue ## for j in range(len(i)): ## if in_the_same(i[j],i[j+1],a) !=in_the_same(i[j],i[j+1],b) #突然发现应该用集合来做这个2个list的求交运算. a_set=[] b_set=[] for i in list1: a_set.append(set(i)) for i in list2: b_set.append(set(i)) #然后直接求交即可. c=[] for i in a_set: for j in b_set: d=(i&j) if len(d)!=0: c.append(d) return c #针对有向图要有一个强联通分支算法. #自己设计了一个算法:首先把G的Transpose记做Gt. '''然后,做dfs在G上做一次,类似无向图的dfs分解连通分支的方法,把定点分类, 然后在Gt上再做一次,又把定点分类了.然后我们取2次分类的交即可,就是要的分支. 这里面交指的是2次划分的更细的子划分.也就是比如第一次把12一类,3一类. 第二次把13一类,2一类,那么交就是1,2,3分成3类. ''' def addweight(self,a,b,weight): self.weight[a][b]=weight self.weight[b][a]=weight return #A wise man changes his mind,a fool never. def minimal_spanning_tree(self): #具体方法就是https://blog.csdn.net/luoshixian099/article/details/51908175 #一个是kruskal加点发,prim加边法. new=Graph(6) c=[] num=1 while 1: d=[] for i in range(6): a=new.dfs_all() if len(a)==1: return c d=(np.argwhere(g.weight==num))#这个很方便,返回下表 for t in range(len(d)): k=d[t] i,j=k[0],k[1] e=new.dfs(i) f=new.dfs(j) print (e) print (f) print (set(e)) print (set(f)) if set(e)&set(f)==set(): c.append((i,j)) new.addedge(i,j) print (c) num+=1 break ''' 写点,kruskal算法的思想,其实很trivial,就是贪心. 他的贪心原则就是抓住本质,你每一次加一个边就是为了多加点,而少加weight, 所以从weight排序里面找,加入点最多的,也就是生成树之间没有交集的,这样每一次就都加入了 2个点.而不是1个点.因为最后所有的点还是要进行相连接的,所以只需要进行每一次的贪心就可以保证 最后的所有点的数目.这种贪心正确.''' g=Graph(6) g.addedge(0,1) g.addedge(0,2) g.addedge(0,3) g.addedge(1,2) g.addedge(2,3) g.addedge(1,4) g.addedge(2,4) g.addedge(2,5) g.addedge(3,5) g.addedge(4,5) g.addweight(0,1,6) g.addweight(0,3,5) g.addweight(0,2,1) g.addweight(1,4,3) g.addweight(4,5,6) g.addweight(2,1,5) g.addweight(3,2,5) g.addweight(2,4,6) g.addweight(2,5,4) g.addweight(3,5,2) print (g.dfs_all()) print (g.minimal_spanning_tree()) #[(0, 2), (3, 5), (1, 4), (2, 5), (1, 2)]搞定了,trivial问题. #成功得到了4个分支,并且还是按照标号 #的顺序进行排列的分支.然后随意修改edge,都成功了. ''' 下面继续学习图:发现博客上面的比算法导论上面的方法更先进. http://blog.csdn.net/moshenglv/article/details/72954701''' ''' 强连通图（Strongly Connected Graph）是指在有向图G中，如果对 于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径， 则称G是强连通图。''' ''' 1.图的存储结构: 1.邻接矩阵 2.邻接矩阵是一种不错的图存储结构，但是对于边数相对较少的图， 这种结构存在空间上的极大浪费， 因此找到一种数组与链表相结合的存储方法称为邻接表。 3. 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易 找到以v为尾 的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同 的，因此，在有向图应用中，十字链表是非常好的数据结构模型。(相当复杂) ''' ''' 下面先写bfs'''
4.图的单源最小距离的路径的求法.屌丝bellman_ford方法.
''' 把图改成无向图:''' import numpy as np import numpy class Graph(): def __init__(self,n): self.vertex_num=n self.edge=[] for i in range(n):#2-dim-empty list cannot use *99 self.edge.append([]) self.indegree=[0]*n self.count=0#作为dfs里面的flag self.weight=numpy.array([None]*n**2).reshape(n,n) self.whether_exist=[0]*self.vertex_num #vertex_index=0,1,2,3,4.... def addedge(self,n,m): self.edge[n].append(m) self.edge[m].append(n) self.indegree[m]+=1 self.indegree[n]+=1 def Transpose(self): self.edgenew=[] n=self.vertex_num for i in range(n):#2-dim-empty list cannot use *99 self.edgenew.append([]) for i in range(len(self.edge)): if self.edge[i]!=[]: tmp=self.edge[i] for j in tmp: self.edgenew[j].append(i) new=Graph(n)#重新分配一个对象,这样就跟以前不干扰了 new.edge=self.edgenew return new def topological_sort(self): a=[] b=len(self.indegree) while (b): for i in range(len(self.indegree)): if 0 not in self.indegree: return False if self.indegree[i]==0: a.append(i) self.indegree[i]-=1 for j in self.edge[i]: self.indegree[j]-=1 b-=1 break def bfs(self,root):#board first search广度优先遍历 #广度优先遍历,深度优先遍历都是只从一个root点出发,遍历跟他有关系的点. #所以不连通的图需要多次从不同的root出发进行遍历才行.那个后话了. #这个很麻烦,可不可以做一个count让函数第一次被调用时候才跑这句话. #可以给class加一个变量.写在__init__里面 #好像广度搜索不能写递归,一些递归就深度了. self.output=[] if root not in self.output: self.output.append(root) tmp=self.edge[root] tmp2=[] while 1: for i in range(len(tmp)): if tmp[i] not in self.output: self.output.append(tmp[i]) c=[] for i in range(len(tmp)): for j in range(len(self.edge[tmp[i]])): if self.edge[tmp[i]][j] not in self.output: c+=self.edge[tmp[i]] if c==[]: return self.output tmp=c def dfs(self,root):#类似也弄好dfs这次可以递归了. #跟树的遍历不同,图需要去重,很麻烦. #还是不行,可能必须要实现知道节点的数目才行.不然没法开记忆是否存储的数组 self.tmp=[]#dfs中间变量 #用函数体外的self.tmp来做记忆,用嵌套函数来解决递归函数返回值问题 def min_dfs(root):#这个函数嵌套不用self,可以只是一般函数 b=[] if root not in self.tmp: self.tmp.append(root) for i in self.edge[root]: if i not in self.tmp: b.append(i) c=[] for i in b: #这步体现的递归.和dfs c+=(min_dfs(i)) tmp=[root]+c return tmp min_dfs(root) return self.tmp def dfs_all(self):#所有节点都跑一边的dfs算法.为了下面的实用强联通分支,我们把 #返回值写作一个数组 n=self.vertex_num c=[] d=[] head=0 while 1: if len(d)==n: return c tmp=self.dfs(head) k=[] for i in tmp: if i not in d: k.append(i) d+=k c.append(k) for i in range(n): if i not in d: head=i break def strong_connected_components(self): a=self#self指的是对象 b=self.Transpose() list1=self.dfs_all() self=b#类还能这么玩,直接类的方法里面改变这个对象 list2=self.dfs_all() def in_the_same(c,d,L): for i in L: if c in i and d in i: return True return False ## import copy ## listnew=[] ## for i in list1: ## if len(i)==1: ## continue ## for j in range(len(i)): ## if in_the_same(i[j],i[j+1],a) !=in_the_same(i[j],i[j+1],b) #突然发现应该用集合来做这个2个list的求交运算. a_set=[] b_set=[] for i in list1: a_set.append(set(i)) for i in list2: b_set.append(set(i)) #然后直接求交即可. c=[] for i in a_set: for j in b_set: d=(i&j) if len(d)!=0: c.append(d) return c #针对有向图要有一个强联通分支算法. #自己设计了一个算法:首先把G的Transpose记做Gt. '''然后,做dfs在G上做一次,类似无向图的dfs分解连通分支的方法,把定点分类, 然后在Gt上再做一次,又把定点分类了.然后我们取2次分类的交即可,就是要的分支. 这里面交指的是2次划分的更细的子划分.也就是比如第一次把12一类,3一类. 第二次把13一类,2一类,那么交就是1,2,3分成3类. ''' def addweight(self,a,b,weight): self.weight[a][b]=weight self.weight[b][a]=weight return #A wise man changes his mind,a fool never. def function(self): pass def minimal_spanning_tree(self): #具体方法就是https://blog.csdn.net/luoshixian099/article/details/51908175 #一个是kruskal加点发,prim加边法. new=Graph(6) c=[] num=1 while 1: d=[] for i in range(6): a=new.dfs_all() if len(a)==1: return c d=(np.argwhere(self.weight==num))#这个很方便,返回下表 for t in range(len(d)): k=d[t] i,j=k[0],k[1] e=new.dfs(i) f=new.dfs(j) print (e) print (f) print (set(e)) print (set(f)) if set(e)&set(f)==set(): c.append((i,j)) new.addedge(i,j) print (c) num+=1 break return def bellman_ford(self,start_point): b=[None]*self.vertex_num #用来存储前驱节点,来输出最后的最短路径. c=[float('inf')]*self.vertex_num#用来存储start_point到点i的距离给b[i]存储. print (c) b[start_point]=start_point c[start_point]=0 d=np.argwhere(g.weight!=None) print (d) for i in range(len(b)-1): for j in range(len(d)): start=d[j][0] end=d[j][1] if c[start]+self.weight[start][end]<c[end]: c[end]=c[start]+self.weight[start][end] b[end]=start#到这里路径就完事了,松弛技术写起来也挺trivial #b是前驱节点表 #然后通过前驱节点,来做路径表,因为贪心原则.可以做到. #一个最短路径上的任意两点之间的路径也必然是这两点的最短路径. #下面输出路径表k k=[None]*self.vertex_num k[start_point]=start_point tmp=[] for i in range(len(k)): if i !=start_point: tmp=[i] now=b[i] while 1: if now==start_point: tmp.append(now) k[i]=tmp[::-1] break tmp.append(now) now=b[now] return c,b,k #返回的k就是路径.从开始到结尾 g=Graph(6) g.addedge(0,1) g.addedge(0,2) g.addedge(0,3) g.addedge(1,2) g.addedge(2,3) g.addedge(1,4) g.addedge(2,4) g.addedge(2,5) g.addedge(3,5) g.addedge(4,5) g.addweight(0,1,6) g.addweight(0,3,5) g.addweight(0,2,1) g.addweight(1,4,3) g.addweight(4,5,6) g.addweight(2,1,5) g.addweight(3,2,5) g.addweight(2,4,6) g.addweight(2,5,4) g.addweight(3,5,2) print (g.bellman_ford(0)) #成功得到了4个分支,并且还是按照标号 #的顺序进行排列的分支.然后随意修改edge,都成功了. ''' 下面继续学习图:发现博客上面的比算法导论上面的方法更先进. http://blog.csdn.net/moshenglv/article/details/72954701''' ''' 强连通图（Strongly Connected Graph）是指在有向图G中，如果对 于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径， 则称G是强连通图。''' ''' 1.图的存储结构: 1.邻接矩阵 2.邻接矩阵是一种不错的图存储结构，但是对于边数相对较少的图， 这种结构存在空间上的极大浪费， 因此找到一种数组与链表相结合的存储方法称为邻接表。 3. 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易 找到以v为尾 的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。 而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同 的，因此，在有向图应用中，十字链表是非常好的数据结构模型。(相当复杂) ''' ''' 下面先写bfs'''
还有一个djkstra的高速方法.
这个4里面的算法太有用了:比如一个地图里面很多个点之间的距离都有,求一条a到b的最短路径.就可以用这个方法求得.