本章内容
- 图的定义与基本概念
- 图抽象数据类型定义
- 实现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|2这个量级。
邻接表：
可以成为稀疏图 的更高效实现方案，维护一个包含所有顶点的主列表（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(n2)，对于所有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|)。
网友评论