算法_图

╰半夏微凉° 2023-02-20 10:41 25阅读 0赞

## 图Graph ##

### 术语 ###

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

![赋权图述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]

*  顶点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，圈是首尾顶点相同的路径，如果有向图中不存在任何图，则称作“有向无圈图 directed acyclic graph: DAG“

## ADT Graph ##

ADT Graph的实现方式有两种主要形式：

*  邻接矩阵 adjacency matrix
 *  邻接表 adjacency list

### 邻接矩阵 ###

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

![邻接矩阵][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]

*  优点：简单容易理解，很容易得到顶点是如何连接的
 *  但如果图中边数很少则效率低下，成为稀疏sparse矩阵。而大多数问题所对应的图都是稀疏的，边远远少于|V|^2这个量级

### 邻接列表 ###

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

### 实现 ###

在Python中，通过字典可以轻松地实现邻接表

需要创建两个类：

*  Graph类存储包含所有顶点的主列表
    
    其中包含一个将顶点名映射到顶点对象的字典
    
        class Graph:
            def __init__(self):
                self.vertlist = { }
                self.numVertices = 0
        
            def addVertex(self, key):
                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.addVertex(f)
                if t not in self.vertlist:
                    nv = self.addVertex(t)
                # 调用起始点的方法添加邻接边
                # {1：{2:3}} self.vertlist[f]==>{2:3}
                # self.connectedTo[nbr]==> 2 weight==> 3
                self.vertlist[f].addNeighbor(self.vertlist[t], cost)
        
            def getVertices(self):
                return self.vertlist.keys()
        
            def __iter__(self):
                return iter(self.vertlist.values())
 *  Vertex类表示图中的每一个顶点
    
    使用字典connectedTo来记录与其相连接的点，以及每一条边的权重
    
        class Vertex:
            def __init__(self, key):
                self.id = key
                self.connectedTo = { }
        
            def addNeighbor(self, nbr, weight=0):
                # nbr是顶点对象的key
                self.connectedTo[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]
 *  测试
    
        g = Graph()
        for i in range(6):
            g.addVertex(i)
        g.addEdge(0, 1, 5)
        g.addEdge(0, 5, 2)
        g.addEdge(1, 2, 4)
        g.addEdge(2, 3, 9)
        g.addEdge(3, 4, 7)
        g.addEdge(3, 5, 3)
        g.addEdge(4, 0, 1)
        g.addEdge(5, 4, 8)
        g.addEdge(5, 2, 1)
        for v in g:
            for w in v.getConnections():
                print(f'{v.getId()} {w.getId()}')
        # 0 1
        # 0 5
        # 1 2
        # 2 3
        # 3 4
        # 3 5
        # 4 0
        # 5 4
        # 5 2

## 图的应用 ##

### 词梯Word Ladder问题 ###

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

**构建单词关系图：**

*  首先是如何将大量的单词集放到图中
    
    将单词作为顶点的标识key
    
    如果两个单词之间相差1个字母，就在它们之间设一条边
 *  下图是从FOOL到SAGE的词梯解，所用的图是无向图，边没有权重，FOOL到SAGE的每条路径都是一个解
    
    ![词梯图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 3]
 *  单词关系图可以通过不同的算法来构建（以4个字母的单词表为例）
    
    首先是将所有单词作为顶点加入图中，再设法建立顶点之间的边
 *  建立边的最直接算法，是对每个顶点（单词），与其所有单词进行比较，如果相差仅1个字母，则建立一条边
    
    时间复杂度是0(n^2)，对于所有4个字母的5110个单词，需要超过2600万次比较
 *  改进的算法是创建大量的桶，每个桶可以放若干单词
    
    桶标记是去掉1个字，通配符“\_”占空的单词
 *  所有匹配标记的单词都放到这个桶里
    
    所有单词就位后，再在同一个桶的单词之间建立边即可
    
    ![桶][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 4]
    
     *  单词关系图是一个非常稀疏的图
    
        from pythonds.basic import Queue
        from pythonds.graphs import Graph,Vertex
        
        def buildGraph(wordFile):
            d = { }
            g = Graph()
            wfile = open(wordFile, 'r')
            for line in wfile:
                # 相当于 line.strip()
                word = line[:-1]
                # 4字母单词可属于4个桶
                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
        
        
        wordFile = 'fourletterwords.txt'
        buildGraph(wordFile)

### 实现广度优先搜索 ###

*  在单词关系图建立完成以后，需要继续在图中寻找词梯问题的最短序列
 *  需要用到“广度优先搜索Breadth First Search”算法对单词关系图进行搜索
 *  给定图G，以及开始搜索的起始顶点s
    
    BFS搜索所有从s可到顶点的边
    
    而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点
    
    可以想象以s为根，构建一棵树的过程，从顶部向下逐步增加层次
    
    广度优先搜索能保证在增加层次之间，添加了所有兄弟节点到树种
 *  为了跟踪顶点的加入过程，并避免重复项顶点，要为顶点增加3个属性
    
    距离 distance：从起始顶点到次此顶点路径长度
    
    前驱顶点 predecessor：可方向追溯到起点
    
    颜色 color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成搜索（黑色）
 *  还需要用一个队列Queue来对已经发现的顶点进行排列
    
    决定下一个要探索的顶点（队首顶点）

**执行步骤：**

从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程：

*  从队首取出一个顶点作为当前顶点
 *  遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中，遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点  
    ![1][]  
    ![2][]![3][]  
    ![4][]
    
        def bfs(g, start):
            # class Vertex: self.dist = d
            start.setDistance(0)
            # class Vertex: self.pred = p
            start.setPred(None)
            vertQueue = Queue()
            vertQueue.enqueue(start)
            while vertQueue.size() > 0:
                # 取队首作为当前顶点
                currentVert = vertQueue.dequeue()
                # 遍历邻接顶点
                # class Vertex: return self.connectedTo.keys()
                for nbr in currentVert.getConnections():
                    # class Vertex: return self.color
                    if nbr.getColor() == 'white':
                        # class Vertex: self.color = color
                        nbr.setColor('gray')
                        # class Vertex: return self.dist
                        nbr.setDistance(currentVert.getDistance()+1)
                        nbr.setPred(currentVert)
                        vertQueue.enqueue(nbr)
                    # 当前顶点设黑色
                    currentVert.setColor('black')
 *  在以FOOL为起始顶点，遍历了所有顶点，并为每个顶点着色、赋距离和前驱之后
 *  即可以通过一个回途追溯函数来确定FOOL到任何单词顶点的最短词梯
    
        def traverse(y):
            x = y
            while x.getPred():
                print(x.getId())
                x = x.getPred()
            print(x.getId())

**总代码**

import sys
    from pythonds.basic import Queue
    from pythonds.graphs import Graph, Vertex
    
    
    def buildGraph(wordFile):
        d = { }
        g = Graph()
        wfile = open(wordFile, 'r')
        for line in wfile:
            # 相当于 line.strip()
            word = line[:-1]
            # 4字母单词可属于4个桶
            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
    
    
    def bfs(g, start):
        # class Vertex: self.dist = d
        start.setDistance(0)
        # class Vertex: self.pred = p
        start.setPred(None)
        vertQueue = Queue()
        vertQueue.enqueue(start)
        while vertQueue.size() > 0:
            # 取队首作为当前顶点
            currentVert = vertQueue.dequeue()
            # 遍历邻接顶点
            # class Vertex: return self.connectedTo.keys()
            for nbr in currentVert.getConnections():
                # class Vertex: return self.color
                if nbr.getColor() == 'white':
                    # class Vertex: self.color = color
                    nbr.setColor('gray')
                    # class Vertex: return self.dist
                    nbr.setDistance(currentVert.getDistance()+1)
                    nbr.setPred(currentVert)
                    vertQueue.enqueue(nbr)
                # 当前顶点设黑色
                currentVert.setColor('black')
    
    
    def traverse(y):
        x = y
        while x.getPred():
            print(x.getId())
            x = x.getPred()
        print(x.getId())
    
    
    wordgraph = buildGraph('fourletterwords.txt')
    bfs(wordgraph, wordgraph.getVertex('FOOL'))
    traverse(wordgraph.getVertex('SAGE'))
    # SAGE
    # SALE
    # SALL
    # MALL
    # MOLL
    # MOOL
    # FOOL

**算法分析**

*  BFS算法主体是两个循环的嵌套
    
    while循环每个顶点访问一次，所以是O(|V|)
    
    而嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，而每个顶点最多出队1次，所以边最多被检查1次，一共是O(|E|)
    
    综合起来BFS的时间复杂度是O(|V|+|E|)
 *  词梯问题还包括两个部分算法
    
    建立BFS树之后，回溯顶点到起始顶点的过程，最多O(|V|)
    
    创建单词关系图也需要时间，最多为O(|V|²)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200626002651804.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200626142412794.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200626143419399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200627153603396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200627154404383.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/20200627233118517.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200627233143865.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[3]: https://img-blog.csdnimg.cn/20200627233200695.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[4]: https://img-blog.csdnimg.cn/20200627233226787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70