一個(gè)圖(graph)G=(V,E)是由頂點(diǎn)集V和邊集E組成。每一條邊就是一個(gè)頂點(diǎn)對(duì)(v,w)，其中v,w∈V。如果點(diǎn)對(duì)是有序的，那么圖就是有向圖。
圖中的一條路徑path是一個(gè)頂點(diǎn)序列w1,w2,w3，...，wk，使得(wi，wi+1)∈E，1<=i<=k。路徑的長(zhǎng)是該路徑上的邊數(shù)。
如果在一個(gè)無(wú)向圖中從每一個(gè)頂點(diǎn)到其它頂點(diǎn)都存在一條路徑，則稱(chēng)該路徑是連通的。具有這種性質(zhì)的有向圖是強(qiáng)連通的。有向圖的弧上去掉方向所形成
的圖是連通的，則該有向圖為弱連通的。
用鄰接矩陣表示，對(duì)于每條邊(u，v)，設(shè)置A[u][v]=1，否則為0.如果邊有個(gè)權(quán)，則設(shè)置數(shù)組元素為權(quán)?？臻g需求為Θ(V2)。
若圖很稠密(邊很多)，則鄰接矩陣是合適的表示方法。如果很稀疏，更好的解決方法是鄰接表。
對(duì)于每一個(gè)頂點(diǎn)，用一個(gè)表存放所有鄰接的頂點(diǎn)，此時(shí)的空間需求為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())
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
