图的表示
1、稀疏图
稀疏图使用邻接表表示。
优点：节约空间。
缺点：访问一个结点的相邻结点的时候，需要遍历。
2、稠密图
稠密图使用邻接矩阵表示。
优点：访问快。
缺点：占用空间多。
我们这一节的例子都是“无向图”。
稀疏图表示
class SparseGraph:
def __init__(self, n, directed):
assert n > 0
# 结点数
self.n = n
# 边数
self.m = 0
# 是否是有向图
self.directed = directed
# 图的具体数据
self.g = [[] for _ in range(n)]
def add_edge(self, v, w):
assert 0 <= v < self.n
assert 0 <= w < self.n
# 在邻接表的实现中，has_edge 方法要进行遍历
# 这一步的时间复杂度是比较高的
# 我们在学习的时候，可以不进行判断，即允许平行边
# 我们这里暂时保留
if self.has_edge(v, w):
return
v_neighbours = self.g[v]
v_neighbours.append(w)
# 如果是无向图，维护无向图的对称性
# v != w 不允许自环边
if v != w and not self.directed:
w_neighbours = self.g[w]
w_neighbours.append(v)
self.m += 1
def has_edge(self, v, w):
assert 0 <= v < self.n
assert 0 <= w < self.n
# v 的所有相邻结点的集合
v_neighbours = self.g[v]
for neighbour in v_neighbours:
if neighbour == w:
return True
return False
def show(self):
for v in range(self.n):
print("顶点", v, end=": ")
for neighbour in self.g[v]:
print(neighbour, end=',')
print()
def iterator(self, v):
return SparseGraphIterator(self, v)
稠密图表示
class DenseGraph:
def __init__(self, n, directed):
assert n > 0
# 结点数
self.n = n
# 边数
self.m = 0
# 是否是有向图
self.directed = directed
# 图的具体数据
self.g = [[False for _ in range(n)] for _ in range(n)]
def add_edge(self, v, w):
assert 0 <= v < self.n
assert 0 <= w < self.n
# 如果已经有了结点 v 到结点 w 的边
# 就直接返回，不再添加邻边，和 m + 1
if self.has_edge(v, w):
return
self.g[v][w] = True
# 如果是无向图，维护无向图的对称性
if not self.directed:
self.g[w][v] = True
self.m += 1
def has_edge(self, v, w):
assert 0 <= v < self.n
assert 0 <= w < self.n
return self.g[v][w]
def show(self):
for i in range(self.n):
for j in range(self.n):
if self.g[i][j]:
print('1', end=' ')
else:
print('0', end=' ')
print()
def iterator(self, v):
return DenseGraphIterator(self, v)
邻边迭代器
# 稀疏图迭代器
class SparseGraphIterator:
def __init__(self, graph, v):
self.graph = graph
self.neighbours = self.graph.g[v]
# print(self.neighbours)
self.index = 0
def __iter__(self):
return self
def __next__(self):
if self.index < len(self.neighbours):
item = self.neighbours[self.index]
self.index += 1
return item
else:
raise StopIteration
# 稠密图迭代器
class DenseGraphIterator:
def __init__(self, graph, v):
self.graph = graph
self.neighbours = self.graph.g[v]
self.index = -1
self.l = len(self.neighbours)
def __iter__(self):
return self
def __next__(self):
self.index += 1
if self.index == self.l:
raise StopIteration
while not self.neighbours[self.index]:
self.index += 1
if self.index == self.l:
raise StopIteration
return self.index
读图工具
class ReadGraph:
def __init__(self, graph, filename):
self.g = graph
with open(filename, 'r') as fr:
V, E = fr.readline().split(',')
print('图的顶点数和边数：', V, E, end='')
for line in fr.readlines():
v, w = line.split(',')
# print(v, w, end='')
self.g.add_edge(int(v), int(w))
有了图的数据结构表示和从一个文件中读取图，我们就可以编写如下测试方法了。
读文件，并打印图的信息
“graph1.txt” 文件如下图左边表示，是一个文本文件，第 1 行是“图的顶点数和边数”，后面的所有行表示边的信息，每一行存储的是边的两个顶点。
image假设该图是一张无向图。下面是它的邻接矩阵和邻接表表示：
image.png image.png
图的深度优先遍历、计算图的连通分量
# 使用深度优先遍历计算连通分量
class Component:
def __init__(self, graph):
self.graph = graph
# 记录深度优先遍历的过程中结点是否被访问过
self.vistied = [False for _ in range(self.graph.n)]
# 每个结点对应的连通分量的标记，一开始设置为 -1 ，从 0 开始编号，设置成 0 是不正确的
self.id = [-1] * self.graph.n
# 一开始连通分量设置为 0
self.ccount = 0
# 下面是深度优先遍历的模板代码
# 求图的连通分量
for i in range(self.graph.n):
if not self.vistied[i]:
self.__dfs(i)
# 一次深度优先遍历完成以后，连通分量 + 1
self.ccount += 1
def __dfs(self, v):
self.vistied[v] = True
self.id[v] = self.ccount
for neighbour_index in self.graph.iterator(v):
# print(v, neighbour_index, self.vistied)
if not self.vistied[neighbour_index]:
self.__dfs(neighbour_index)
def is_connected(self, v, w):
assert 0 <= v < self.graph.n
assert 0 <= w < self.graph.n
return self.id[v] == self.id[w]
寻路算法
找到从一个点（源点）出发，到另一点的一条路径。
class Path:
def __init__(self, graph, source):
self.graph = graph
assert 0 <= source < self.graph.n
self.visited = [False] * self.graph.n
self.from_ = [-1] * self.graph.n
self.source = source
self.__dfs(source)
def __dfs(self, v):
self.visited[v] = True
for v_neighbour in self.graph.iterator(v):
if not self.visited[v_neighbour]:
self.from_[v_neighbour] = v
self.__dfs(v_neighbour)
def has_path(self, w):
assert 0 <= w < self.graph.n
return self.visited[w]
def path(self, w):
assert self.has_path(w)
stack = []
p = w
while p != -1:
stack.append(p)
p = self.from_[p]
path = []
while stack:
path.append(stack.pop())
return path
def show_path(self, w):
assert self.has_path(w)
path = self.path(w)
# print('路径',path)
print(" -> ".join(map(lambda x: str(x), path)))