图论(一)------图的表示
一个图(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())
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。