7.2Graph的实现

Python 中，通过字典可以轻松地实现邻接表。我们要创建两个类：Graph 类存储包含所
有顶点的主列表，Vertex 类表示图中的每一个顶点。
Vertex 使用字典 connectedTo 来记录与其相连的顶点，以及每一条边的权重。
addNeighbor 方法添加从一个顶点到另一个的连接。getConnections 方法返
回邻接表中的所有顶点，由 connectedTo 来表示。getWeight 方法返回从当前顶点到以参数
传入的顶点之间的边的权重。

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        self.connevtedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + 'connectedTo:' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return  self.connectedTo[nbr]

Graph 类中包含一个将顶点名映射到顶点对象的字典。Graph 类也提供了向图中添加顶点和连接不同顶点的方法。getVertices 方法返回图中所有顶点的名字。iter方法，使遍历图中的所有顶点对象更加方便。

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

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

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

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

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

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

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

图的应用：词梯问题

词梯Word Ladder问题
由 “ 爱丽丝漫游奇境 ” 的作者 LewisCarroll在1878年所发明的单词游戏
从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。要求是相邻两个单词之间差异只能是1个字母， 如FOOL变SAGE：
FOOL >> POOL >> POLL >> POLE >> PALE >> SALE >> SAGE
目标是找到最短的单词变换序列
采用图来解决这个问题的步骤如下：
将可能的单词之间的演变关系表达为图，采用“广度优先搜索 BFS”，来搜寻从开始单词
到结束单词之间的所有有效路径，选择其中最快到达目标单词的路径

构建单词关系图
❖首先是如何将大量的单词集放到图中
将单词作为顶点的标识Key，如果两个单词之间仅相差1个字母，就在它们之间设一条边
❖从FOOL到SAGE的词梯解，所用的图是无向图，边没有权重
FOOL到SAGE的每条路径都是一个解

image.png

❖单词关系图可以通过不同的算法来构建（以4个字母的单词表为例）
首先是将所有单词作为顶点加入图中，再设法建立顶点之间的边
❖建立边的最直接算法，是对每个顶点（单 词），与其它所有单词进行比较，如果相差仅1个字母，则建立一条边
时间复杂度是O(n^2)，对于所有4个字母的5110个单词，需要超过2600万次比较
❖改进的算法是创建大量的桶，每个桶可以存放若干单词
桶标记是去掉1个字母，通配符“_”占空的单词
❖所有匹配标记的单词都放到这个桶里
所有单词就位后，再在同一个桶的单词之间建立边即可

image.png
采用字典建立桶

def buildGraph(file):
    d = {}
    g = Graph()

    #创建词桶
    f = open(file)
    for line in f:
        word = line[:-1]
        # bird
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    #构建图
    for bucket in d.keys():
        for v1 in d[bucket]:
            for v2 in d[bucket]:
                if v1 != v2:
                    g.addEdge(v1,v2)
    return g
if __name__ == '__main__':
    g = buildGraph('ds_tree/fourletterwords.txt')
    for item in g.verList.values():
        print(item)