注：参考书籍《Python数据结构与算法》

1.图的抽象数据类型定义

Graph()新建一个空图；

addVertex(vert)向图中添加一个顶点(vert)实例;

addEdge(fromVert,toVert)向图中添加一条有向边，用于连接顶点fromVert，toVert

addEdge(fromVert,toVert,weight)向图中添加一条带权重(weight)的有向边

getVertex(vertKey)在图中找到名为vertKey的顶点

getVertices()以列表形式返回图中所有顶点

in通过vertex in graph，在顶点存在时返回True，不存在时返回False

2.图的存储

2.1 邻接矩阵

使用二维矩阵实现图的存储。在矩阵实现中，每一行每一列都表示图中的一个顶点。行列交叉处的数字表示这条边的权重。如图所示：

优点：简单，可以清晰的展示那些顶点是相连的；适用于稠密图；

2.2 邻接表

为图对象的所有顶点保存一个主列表，同时为没一个顶点对象都维护一个列表，记录与它相连的对象。如图所示：

优点：能够紧凑的表示稀疏图；方便找到某一个顶点相连的其他顶点

3.Python实现Vertex、Graph类

Vertex类：

#Vertex使用字典connectedTo来记录与其相连的顶点，以及每一条边的权重
class Vertex:
    #初始化id(通常是一个字符串)，以及字典connectedTo
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}
    #addNeighbor方法天剑一个顶点到另一个顶点的连接
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight
    
    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
    #getConnections方法返回邻接表中的所有顶点，由connectedTo来表示
    def getConnections(self):
        return self.connectedTo.keys()
    
    def getId(self):
        return self.id
    #返回当前顶点到以参数传入的顶点之间的边的权重
    def getWeight(self,nbr):
        return self.connectedTo[nbr]

Graph类： 

class Graph:
    def __init__(self):
        self.verList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.verList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.verList:
            return self.verList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.verList

    def addEdge(self,f,t,cost = 0):
        if f not in self.verList:
            nv = self.addVertex(f)
        if t not in self.verList:
            nv = self.addVertex(t)
        self.verList[f].addNeighbor(self.verList[t],cost)

    def getVertices(self):
        return self.verList.keys()

    def __iter__(self):
        return iter(self.verList.values())

4.广度优先搜索（BFS）

词梯问题：将单词FOOL转换成SAGE。要求：每次只替换一个字母，并且每一步的结果都是一个单词（必须是存在的单词）。

求解：用图的BFS找到从起始单词到结束单词的最短路径。

具体一个解的例子：

 BFS思路：给定图G和起点s，BFS通过边来访问在G中与s之间存在路径的顶点。它会在访问完所有与S相距为k的顶点之后再去访问与s相距为k+1的顶点。为了记录进度，用白色表示该顶点还未被访问；灰色表示该顶点访问了，但是与它直接相连的其他顶点还未访问完；黑色表示该顶点已经访问完。

代码实现：

def BFS(g,start):
    #当前顶点与下一顶点的路径长度
    start.setDistance(0)
    #当前顶点的前驱节点
    start.setPred(None)
    #顶点队列
    vertQueue = Queue()
    #起始开始顶点入队列
    vertQueue.enqueue(start)
    #当队列不为空时
    while(vertQueue.size()>0):
        #当前顶点为队列出列元素（先进先出）
        currentVert = vertQueue.dequeue()
        #遍历与当前顶点相连的所有邻居（其他顶点）
        for nbr in currentVert.getConnections():
            #nbr顶点的颜色为白色表示还未被访问
            if (nbr.getColor() == 'white'):
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistence() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        #遍历当前顶点的所有相连顶点之后，改为黑色
        currentVert.setColor('black')

应用实例：

 

 

分析BFS：while循环对于|V|中的任一顶点最多执行一次。因为只有白色顶点才能被方位并添加到队列中。使得while循环的时间复杂度为O(V)。内部的for循环，对每一条边都最多只会执行一次。因为每一个顶点最多只会出列一次，并且只有在顶点u出列时才会访问从u到v的边。使得for循环的时间复杂度为O(E)。所以总时间复杂度为O(V+E)。