一个图(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.如果边有个权，则设置数组元素为权。空间需求为Θ(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())
新闻热点
疑难解答
