数据结构与算法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 gword_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 = keyself.connected_to = {}self.distance = distanceself.pred = predself.color = colordef __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] = weightdef get_connections(self):return self.connected_to.keys()def get_key(self):return self.keydef get_weight(self, nbr):return self.connected_to.get(nbr, None)def set_distance(self, distance):self.distance = distancedef get_distance(self):return self.distancedef set_pred(self, pred):self.pred = preddef get_pred(self):return self.preddef set_color(self, color):self.color = colordef get_color(self):return self.colorclass Graph:"""图"""def __init__(self):self.vertexes = {}self.num_vertexes = 0def __contains__(self, key):return key in self.vertexesdef __iter__(self):return iter(self.vertexes.values())def add_vertex(self, key):"""加入顶点：以key为键，以Vertex对象为值"""self.num_vertexes += 1new_vertex = Vertex(key)self.vertexes[key] = new_vertexreturn new_vertexdef get_vertex(self, key):if key in self.vertexes:return self.vertexes[key]else:return Nonedef 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 = 0for i in self.vertexes.values():count += len(i.connected_to)return count

广度优先搜索-算法实现

from pathlib import Path
from my_queue import Queuedef 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 = targetwhile 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版》专栏！关注不迷路~