python数据结构教程 Day15

本章内容

图的定义与基本概念
图抽象数据类型定义
实现ADT Graph
应用：解决词梯问题

一、图的定义与基本概念

图Graph是比树更为一般的结构，也是由节点和边构成实际上树是一种具有特殊性质的图。

顶点vertex（节点Node）：

图的基本组成部分，顶点具有名称标识Key，也可以携带数据项payload。

边Edge（弧Arc）：

作为2个顶点之间关系的表示，边连接两个顶点；边可以是无向或者有向的，相应的图称作“无向图”和“有向图”。

权重Weight：

为了表达从一个顶点到另一个顶点的“代价”，可以给边赋权。

图的定义：

图G可以定义为G=(V, E)，其中V是顶点的集合，E是边的集合，E中的每条边e=(v, w)，v和w都是V中的顶点；如果是赋权图，则可以在e中添加权重分量

子图：

V和E的子集

路径Path：

图中的路径，是由边依次连接起来的顶点序列；无权路径的长度为边的数量；带权路径的长度为所有边权重的和。

圈Cycle：

圈是首尾顶点相同的路径，如上图中 (v5,v2,v3,v5)是一个圈。如果有向图中不存在任何圈，则称作“有向无圈图directed acyclic graph: DAG” ，后面我们可以看到如果一个问题能表示成DAG，就可以用图算法很好地解决。

二、图抽象数据类型

定义并实现ADT Graph

1、定义其操作：

Graph()：创建一个空的图；
addVertex(vert)：将顶点vert加入图中
addEdge(fromVert, toVert)：添加有向边
addEdge(fromVert, toVert, weight)：添加带权的有向边
getVertex(vKey)：查找名称为vKey的顶点
getVertices()：返回图中所有顶点列表
in：按照vert in graph的语句形式，返回顶点是否存在图中True/False

ADT Graph的实现方法主要有两种形式，邻接矩阵与邻接表，两种方法各有优劣，需要在不同应用中加以选择。

邻接矩阵：

矩阵的每行和每列都代表图中的顶点，如果两个顶点之间有边相连，设定行列值，无权边则将矩阵分量标注为1，或者0，带权边则将权重保存为矩阵分量值。

如果图中的边数很少则效率低下，成为“稀疏sparse”矩阵而大多数问题所对应的图都是稀疏的，边远远少于|V|²这个量级。

邻接表：

可以成为稀疏图的更高效实现方案，维护一个包含所有顶点的主列表（master list）主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表。

邻接列表法的存储空间紧凑高效，很容易获得顶点所连接的所有顶点，以及连接边的信息。

三、实现ADT Graph

需要实现Vertex与Graph两个类

实现Vertex类：

class Vertex:
    '''
    节点类数据结构定义，包含顶点信息，包含边信息。
    采用字典描述临界列表
    '''
    def __init__(self, key):
        '''
        connectedTo字典中的键值对类型为'vertex:weight'
        '''
        self.id = key
        self.connectedTo = {}
        
        # 以下为BFS染色使用
        self.distance = sys.maxsize
        self.color = 'White'
        self.pred = None
        
        # 以下为DFS遍历使用：发现时间与结束时间
        self.discovery = sys.maxsize
        self.finish = sys.maxsize

    def addNeighbour(self,nbr,weight = 0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        '''
        v = Vertex(2)
        print(v)
        '''
        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]
    
    # 以下是BFS染色使用的函数
    def getColor(self):
        return self.color

    def getDistance(self):
        return self.distance

    def getPred(self):
        if self.pred:
            return self.pred
        else:
            return None

    def setDistance(self, distance):
        if distance > 0:
            self.distance = distance
    
    def setPred(self,pred):
        self.pred = pred

    def setColor(self, color):
        self.color = color

    # 以下为DFS遍历使用
    def setDiscovery(self, value):
        self.discovery = value

    def setFinish(self, value):
        self.finish = value

图Graph类的实现：

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, target):
        '''
        查找key为target的顶点
        '''
        if target in self.vertList:
            return self.vertList[target]
        else:
            return None

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

    def addEdge(self,head,tail,weight):
        '''
        添加带权的有向边
        '''
        if head not in self.vertList:
            newVertex = self.addVertex(head)
        if tail not in self.vertList:
            newVertex = self.addVertex(tail)
        self.vertList[head].addNeighbour(self.vertList[tail], weight)
    
    def getVertices(self):
        '''
        返回所有的顶点列表
        '''
        return self.vertList.keys()

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

四、解决词梯问题

词梯问题：

从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。要求是相邻两个单词之间差异只能是1个字母，如FOOL变SAGE： FOOL >> POOL >> POLL >> POLE >> PALE >> SALE >> SAGE，我们的目标是找到最短的单词变换序列。

解决步骤：

将可能的单词之间的演变关系表达为图
采用“广度优先搜索 BFS”，来搜寻从开始单词到结束单词之间的所有有效路径
选择其中最快到达目标单词的路径

step1：构建单词关系图

首先是将所有单词作为顶点加入图中，再设法建立顶点之间的边，建立边的最直接算法，是对每个顶点（单词），与其它所有单词进行比较，如果相差仅1个字母，则建立一条边时间复杂度是O(n²)，对于所有4个字母的5110 个单词，需要超过2600万次比较。

改进的算法是创建大量的桶，每个桶可以存放若干单词，桶标记是去掉1个字母，通配符“_”占空的单词，所有单词就位后，再在同一个桶的单词之间建立边即可

构建单词关系图代码：

def buildGraph(wordFile):
    '''
    建立关系图
    '''
    d = {} # 桶字典，key为字符串类型，value为列表
    g = Graph()
    wfile = open(wordFile,'r')
    
    #按照文件中单词构建桶 
    for line in wfile:
        word = line[:-1] #去掉末尾最后一个元素(换行符)
        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 word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)
    return g

step2：采用广度优先搜索BFS

BFS思想：

给定图G，以及开始搜索的起始顶点s。BFS搜索所有从s可到达顶点的边，而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次。广度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中。

准备工作：

为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加3个属性：

距离distance：从起始顶点到此顶点路径长度；
前驱顶点predecessor：可反向追溯到起点；
颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）

还需要用一个队列Queue来对已发现的顶点进行排列，决定下一个要探索的顶点（队首顶点）

BFS工作过程：

从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列
接下来是个循环迭代过程：
    从队首取出一个顶点作为当前顶点；
    遍历当前顶点的邻接顶点
        如果是尚未发现的白色顶点：
            将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中
    遍历完成后
    将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

代码实现：

def BTS(graph,start):
    '''
    BFS工作过程
    '''
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while(vertQueue.size() > 0):
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getconnections():
            if nbr.getColor() == 'White':
                nbr.setColor('Gray')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('Black')

以某个单词为起点，遍历了所有顶点，并为每个顶点着色、赋距离和前驱之后，即可以通过一个回溯函数来确定起点到任何单词顶点的最短词梯。

回溯：

def traverse(y):
    '''
    回溯找到广度优先所指的路径
    y为终点
    x.getPred()为None表示到达起点
    '''
    x = y
    while(x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())

BFS算法分析：

while循环对每个顶点访问一次，所以是O(|V|)，而嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次。而每个顶点最多出队1次，所以边最多被检查1次，一共是O(|E|) 综合起来BFS的时间复杂度为O(|V|+|E|)。