图论(一)——图的表示

一个图(graph)G=(V,E)是由顶点集V和边集E组成。每一条边就是一个顶点对(v,w)，其中v,w∈V。如果点对是有序的，那么图就是有向图。

图中的一条路径path是一个顶点序列w₁,w₂,w₃，...，w_k，使得(w_i，w_i+1)∈E，1<=i<=k。路径的长是该路径上的边数。

如果在一个无向图中从每一个顶点到其它顶点都存在一条路径，则称该路径是连通的。具有这种性质的有向图是强连通的。有向图的弧上去掉方向所形成

的图是连通的，则该有向图为弱连通的。

图的简单二维数组表示

用邻接矩阵表示，对于每条边(u，v)，设置A[u][v]=1，否则为0.如果边有个权，则设置数组元素为权。空间需求为Θ(V²)。

若图很稠密(边很多)，则邻接矩阵是合适的表示方法。如果很稀疏，更好的解决方法是邻接表。

图的邻接表表示

对于每一个顶点，用一个表存放所有邻接的顶点，此时的空间需求为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())