一個圖(graph)G=(V,E)是由頂點集V和邊集E組成。每一條邊就是一個頂點對(v,w)，其中v,w∈V。如果點對是有序的，那么圖就是有向圖。
圖中的一條路徑path是一個頂點序列w1,w2,w3，...，wk，使得(wi，wi+1)∈E，1<=i<=k。路徑的長是該路徑上的邊數。
如果在一個無向圖中從每一個頂點到其它頂點都存在一條路徑，則稱該路徑是連通的。具有這種性質的有向圖是強連通的。有向圖的弧上去掉方向所形成
的圖是連通的，則該有向圖為弱連通的。
用鄰接矩陣表示，對于每條邊(u，v)，設置A[u][v]=1，否則為0.如果邊有個權，則設置數組元素為權?？臻g需求為Θ(V2)。
若圖很稠密(邊很多)，則鄰接矩陣是合適的表示方法。如果很稀疏，更好的解決方法是鄰接表。
對于每一個頂點，用一個表存放所有鄰接的頂點，此時的空間需求為O(E+V)。
class Vertex(object): def __init__(self,key): self.id=key self.adj={} def addNeighbor(self,nbr,weight=0): self.adj[nbr]=weight def getNeighbors(self): return self.adj.keys() def getId(self): return self.id def getWeight(self,key): return self.adj[key]class Graph(object): def __init__(self): self.vertexlist={} self.size=0 def addVertex(self,key): vertex=Vertex(key) self.vertexlist[key]=vertex self.size+=1 return vertex def getVertex(self,key): return self.vertexlist.get(key) def __contains__(self,key): if key in self.vertexlist: return True else: return False def addEdge(self,f,t,weight=0): if f not in self.vertexlist: self.addVertex(f) if t not in self.vertexlist: self.addVertex(t) self.vertexlist[f].addNeighbor(self.vertexlist[t],weight) def getVertices(self): return self.vertexlist.keys() def __iter__(self): return iter(self.vertexlist.values())
新聞熱點
疑難解答
