数据结构与算法Python版 图的应用与广度优先搜索

一、图的应用-词梯问题

词梯问题 Word Ladder

• 从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。要求是相邻两个单词之间差异只能是1个字母
• 如FOOL变SAGE：FOOL >> POOL >> POLL >> POLE >> PALE >>SALE >> SAGE
• 采用图来解决这个问题，我们的目标是找到最短的单词变换序列
  • 将可能的单词之间的演变关系表达为图
  • 采用“广度优先搜索 BFS”，来搜寻从开始单词到结束单词之间的所有有效路径
  • 选择其中最快到达目标单词的路径

构建单词关系图

• 将单词作为顶点的标识Key，如果两个单词之间仅相差1个字母，就在它们之间设一条边
• 使用无向图，边没有权重
• 算法一：将所有单词作为顶点加入图中，对每个顶点（单词），与其它所有单词进行比较，如果相差仅1个字母，则建立一条边。时间复杂度是O(n^2)
• 算法二：将所有单词作为顶点加入图中，对于有N个字母的单词，建立N个桶，每个桶可以存放若干单词。单词的其中一个字母使用_通配符，所有匹配的单词放到同一桶中。最后，在同一个桶的单词之间建立边。

单词文件words.txt的内容如下：

fool
cool
pool
poll
pole
pall
fall
fail
foil
foul
pale
page
sage
pope
sale

构建单词关系图

def build_graph(word_file):
    """构建单词关系图"""
    buckets = {}
    g = Graph()
    path = Path(word_file)
    contents = path.read_text()
    words = contents.splitlines()
    # 建立桶
    for word in words:
        for i in range(len(word)):
            bucket_key = word[:i] + "_" + word[i + 1 :]
            # 如果key存在，则把单词加入到桶的列表；否则，创建桶和桶列表的第一个单词
            if bucket_key in buckets:
                buckets[bucket_key].append(word)
            else:
                buckets[bucket_key] = [word]

    # 建立边
    for bucket_key in buckets.keys():
        for word1 in buckets[bucket_key]:
            for word2 in buckets[bucket_key]:
                if word1 != word2:
                    g.add_edge(word1, word2)

    return g


word_file = "words.txt"
word_graph = build_graph(word_file)
for values in word_graph.vertexes.values():
    print(values)
    
    
### 输出结果
fool connected to : ['cool', 'pool', 'foil', 'foul']
cool connected to : ['fool', 'pool']
pool connected to : ['fool', 'cool', 'poll']        
foil connected to : ['fool', 'foul', 'fail']        
foul connected to : ['fool', 'foil']
poll connected to : ['pool', 'pall', 'pole']        
pall connected to : ['poll', 'fall', 'pale']        
pole connected to : ['poll', 'pale', 'pope']        
pale connected to : ['pole', 'pall', 'sale', 'page']
pope connected to : ['pole']
fall connected to : ['pall', 'fail']
fail connected to : ['fall', 'foil']
sale connected to : ['pale', 'sage']
page connected to : ['pale', 'sage']
sage connected to : ['page', 'sale']

二、图的广度优先搜索

广度优先搜索 Breadth First Search

• 给定图G，以及开始搜索的起始顶点s，搜索所有从顶点s可到达顶点的边。在达到更远的距离k+1的顶点之前，找到全部距离为k的顶点
• 就像构建一棵树的过程，从顶部向下逐步增加层次。在增加层次之前，添加了所有兄弟节点到树中

广度优先搜索-算法过程

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

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

• 为决定下一个要探索的顶点，用一个队列Queue来对已发现的顶点进行排列

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

  • 从队首取出一个顶点作为当前顶点；
  • 遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中
  • 遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

更新后的顶点类和图类

class Vertex:
    """顶点类"""

    def __init__(self, key, distance=0, pred=None, color="white"):
        self.key = key
        self.connected_to = {}
        self.distance = distance
        self.pred = pred
        self.color = color

    def __str__(self):
        return f"{self.key} connected to : {[x.key for x in self.connected_to]}"

    def add_neighbor(self, nbr, weight=0):
        """键为nbr顶点对象，值为权重"""
        self.connected_to[nbr] = weight

    def get_connections(self):
        return self.connected_to.keys()

    def get_key(self):
        return self.key

    def get_weight(self, nbr):
        return self.connected_to.get(nbr, None)

    def set_distance(self, distance):
        self.distance = distance

    def get_distance(self):
        return self.distance

    def set_pred(self, pred):
        self.pred = pred

    def get_pred(self):
        return self.pred

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

    def get_color(self):
        return self.color


class Graph:
    """图"""

    def __init__(self):
        self.vertexes = {}
        self.num_vertexes = 0

    def __contains__(self, key):
        return key in self.vertexes

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

    def add_vertex(self, key):
        """加入顶点：以key为键，以Vertex对象为值"""
        self.num_vertexes += 1
        new_vertex = Vertex(key)
        self.vertexes[key] = new_vertex
        return new_vertex

    def get_vertex(self, key):
        if key in self.vertexes:
            return self.vertexes[key]
        else:
            return None

    def add_edge(self, begin, end, cost=0):
        """添加边，如果顶点不存在，先添加顶点再加边"""
        if begin not in self.vertexes:
            self.add_vertex(begin)
        if end not in self.vertexes:
            self.add_vertex(end)
        self.vertexes[begin].add_neighbor(self.vertexes[end], cost)

    def get_vertexes(self):
        """返回所有顶点"""
        return self.vertexes.keys()

    def get_edge_count(self):
        count = 0
        for i in self.vertexes.values():
            count += len(i.connected_to)
        return count

广度优先搜索-算法实现

from pathlib import Path
from my_queue import Queue

def bfs(graph: Graph, start_word):
    """广度优先搜索：以start_word为起点，遍历其它顶点，并为每个顶点着色、赋距离和前驱"""
    start = graph.get_vertex(start_word)
    start.set_distance(0)
    start.set_pred(None)
    v_queue = Queue()
    v_queue.enqueue(start)
    while v_queue.size() > 0:
        current_vert: Vertex = v_queue.dequeue()
        for nbr in current_vert.get_connections():
            if nbr.get_color() == "white":
                nbr.set_color("gray")
                nbr.set_distance(current_vert.get_distance() + 1)
                nbr.set_pred(current_vert)
                v_queue.enqueue(nbr)
        current_vert.set_color("black")

词梯问题求解

def traverse(graph: Graph, target_word):
    """输出目标单词的路径，即词梯问题的解"""
    target = graph.get_vertex(target_word)
    x = target
    while x.get_pred() != None:
        print(x.get_key())
        x = x.get_pred()
    print(x.get_key())


word_file = "words.txt"
word_graph = build_graph(word_file)
bfs(word_graph, "fool")
traverse(word_graph, "sage")


### 输出结果
sage
sale
pale
pall
poll
pool
fool

广度优先搜索BFS- 算法分析

• 广度优先搜索算法主体是两个循环的嵌套。while循环对每个顶点访问一次，所以是O(|V|)；嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，所以边最多被检查1次，一共是O(|E|)。综合起来BFS的时间复杂度为O(|V|+|E|)
• 建立BFS树之后，回溯顶点到起始顶点的过程最差情况为O(|V|)；创建单词关系图最差情况为O(|V|2)。

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~