算法: 图论 (1) - Ming's Blog

引入#

图论 (Graph Theory) 是数学和计算机科学中的一个重要分支, 主要研究 图(Graph) 这种数学结构。

图的存储方式#

在计算机中存储图（Graph）主要有三种常见的方式。选择哪种方式取决于你的图是稀疏的还是稠密的，以及你主要需要执行哪些操作（比如是频繁查询两点是否有边，还是频繁遍历某个点的所有邻居）。

邻接矩阵 (Adjacency Matrix)#

这是最直观的方式, 使用一个二维数组来表示。假设图有 $N$ 个顶点, 我们创建一个 $N \times N$ 的矩阵, 如果顶点 $i$ 和顶点 $j$ 之间有边, 则matrix[i][j] = 1(或者存储权重); 如果没有边, 则matrix[i][j] = 0(或无穷大)。

优点	缺点
查询快: 判断两个点之间是否有边，时间复杂度是 $O(1)$ 。	空间浪费: 即使图里只有几条边，也要开辟 $N \times N$ 的空间。对于稀疏图（点很多，边很少），浪费极其严重。空间复杂度为 $O(N^2)$ 。
实现简单: 代码非常容易写。	遍历慢: 想要找出一个点的所有邻居，必须遍历整行，时间复杂度 $O(N)$ 。
适合稠密图: 当边非常多（接近 $N^2$ ）时，空间利用率较高。

代码示例#

1
class Graph:
2
    def __init__(self, num_vertices):
3
        self.V = num_vertices
4
        self.matrix = [[0] * self.V for _ in range(self.V)]
5

6
    def add_edge(self, u, v, weight=1):
7
        self.matrix[u][v] = weight
8
        self.matrix[v][u] = weight # 如果是无向图
9

10
    def has_edge(self, u, v):
11
        return self.matrix[u][v] != 0

邻接表 (Adjacency List)#

这是最常用的存储方式, 特别是对于稀疏图。创建一个大小为 $N$ 的数组，数组的每个元素对应一个顶点。每个顶点后面挂着一个链表 (或动态数组)，链表中存储了与该顶点直接相连的所有邻居。

优点	缺点
节省空间: 只存储存在的边。空间复杂度为 $O(V+E)$ ( $V$ 是点数， $E$ 是边数)。非常适合稀疏图。	查询慢: 判断两个点之间是否有边，需要遍历链表，时间复杂度 $O(degree)$ ，最坏情况 $O(V)$
遍历快: 找出一个点的所有邻居非常高效，时间复杂度与邻居数量成正比 $O(degree)$	实现稍复杂: 比矩阵稍微麻烦一点。

代码示例#

1
class Graph:
2
    def __init__(self, num_vertices):
3
        self.V = num_vertices
4
        # 初始化列表的列表
5
        self.adj = [[] for _ in range(self.V)]
6

7
    def add_edge(self, u, v, weight=1):
8
        # 存储邻居和权重 (v, weight)
9
        self.adj[u].append((v, weight))
10
        self.adj[v].append((u, weight)) # 如果是无向图
11

12
    def get_neighbors(self, u):
13
        return self.adj[u]

边集数组 (Edge List)#

将所有的边 (Edge) 以数组的形式存起来, 每条边是一个对象或元组(起点, 终点, 权重)。

优点	缺点
极其节省空间：只需要 $O(E)$ 。	查询极慢：想要知道点A的邻居是谁，或者A和B是否相连，必须遍历整个边列表，效率很低。
便于排序: 如果算法需要对边按权重排序 (如 Kruskal 最小生成树算法)，这种方式最方便。	适用场景窄: 通常只用于特定的算法，不作为通用的图存储结构。

深度优先搜索 (DFS)#

深度优先搜索 dfs 一般会递归调用自身, 同时会对其访问过的点打上访问标记, 在遍历图时跳过已打过标记的点, 以确保每个点仅访问一次。

dfs 的大致实现如下:

1
def dfs(v):
2
    visited[v] = True
3
    for u in adj[v]:
4
        if not visited[u]:
5
            dfs(u)

Warning

无论是 DFS 还是 BFS，都必须维护一个visited集合，防止在有环的图中无限循环。

广度优先搜索 (BFS)#

广度优先, 就是从起点开始，先访问所有直接相邻的节点 (第一层)，然后再访问这些相邻节点的邻居 (第二层)，像水波扩散一样一层层向外推进。算法过程就像在人群中传播消息。你先告诉你的所有朋友（第一层），然后让你的朋友告诉他们的所有朋友（第二层），以此类推。它的特点是离起点近的先被访问。

bfs 的大致实现如下:

1
from collections import deque
2

3

4
def bfs(s):
5
    q = deque([s])
6
    visited[s] = True
7
    while q: # q 非空
8
        u = q.popleft()
9
        for v in adj[u]:
10
            if not visited[v]:
11
                visited[v] = True
12
                q.append(v)

练习题#

参考#

oi-wiki

引入#

图的存储方式#

邻接矩阵 (Adjacency Matrix)#

代码示例#

邻接表 (Adjacency List)#

代码示例#

边集数组 (Edge List)#

深度优先搜索 (DFS)#

广度优先搜索 (BFS)#

练习题#

参考#

支持与分享

目录