当前位置：首页 > article >正文

从零开始的数据结构教程（四）图论基础与算法实战

article 2025/8/30 9:09:58

🌐 标题一：图的表示——六度空间理论如何用代码实现？

核心需求

图（Graph）是用于表达实体间关系的强大数据结构，比如社交网络中的好友关系，或者城市路网的交叉路口连接。关键在于如何高效存储和遍历这些关系。

两种主流表示法

邻接矩阵（Adjacency Matrix）：
- 适用场景：适合稠密图（边的数量接近节点数量的平方），可以快速判断两个节点之间是否存在边。
- 实现方式：使用二维数组 graph[i][j] 表示节点 i 到 j 是否有边（0 表示无边，1 表示有边；带权图则存储权重）。
```
# 示例：一个包含3个节点的无向图
# 节点0连接节点1和2
# 节点1连接节点0
# 节点2连接节点0
graph = [[0, 1, 1],[1, 0, 0],[1, 0, 0]
]
```

邻接表（Adjacency List）：

适用场景：适合稀疏图（边的数量远小于节点数量的平方），更节省空间。
实现方式：使用哈希表（或数组）存储每个节点，每个节点的值是一个列表，包含其所有邻居节点。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;// 示例：一个包含3个节点的无向图
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2)); // 节点0的邻居是1和2
graph.put(1, Arrays.asList(0));     // 节点1的邻居是0
graph.put(2, Arrays.asList(0));     // 节点2的邻居是0

复杂度对比

操作	邻接矩阵	邻接表
检查两节点边	$O (1)$	$O (k)$
遍历所有邻居	$O (n)$	$O (k)$

$n$ 为节点数，k 为目标节点的邻居数。

🔍 标题二：图的遍历——社交网络的“共同好友”如何找？

图的遍历是探索节点和边关系的基础。主要有两种核心策略。

BFS vs DFS 核心区别

BFS (广度优先搜索)：

策略：像水波一样，从起始点开始，按层级向外扩散，先访问所有直接邻居，再访问它们的邻居，以此类推。
适用场景：查找最短路径（因为它是按层级扩展的，最先找到的路径就是最短的），例如在社交网络中查找“最近的共同联系人”。

from collections import dequedef bfs(graph, start):visited = set()         # 记录已访问的节点，避免重复访问queue = deque([start])  # 使用队列存储待访问的节点visited.add(start)      # 标记起点已访问while queue:node = queue.popleft() # 取出队头节点# print(node)          # 访问当前节点（根据需求打印或处理）for neighbor in graph.get(node, []): # 遍历当前节点的所有邻居if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)

DFS (深度优先搜索)：

策略：像探险家一样，从起始点开始，沿着一条路径尽可能深地探索，直到无路可走或遇到已访问节点，然后回溯，尝试其他路径。
适用场景：拓扑排序、查找连通分量（如在社交网络中挖掘完整的“关系链”或社群）。

def dfs(graph, start):visited = set()stack = [start] # 使用栈模拟递归，存储待访问节点visited.add(start)while stack:node = stack.pop() # 取出栈顶节点# print(node)        # 访问当前节点for neighbor in graph.get(node, []):if neighbor not in visited:visited.add(neighbor)stack.append(neighbor)

高频变形题

双向 BFS：

优化场景：当需要查找两个节点之间的最短路径时，可以从起点和终点同时进行 BFS。当两个搜索队列相遇时，就找到了最短路径，这通常比单向 BFS 效率更高，尤其是在图较大时。

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;// 假设 Node 类包含 ID 和邻居列表
class Node {int id;List<Node> neighbors;Node(int id) { this.id = id; this.neighbors = new ArrayList<>(); }
}int bidirectionalBFS(Node start, Node end) {if (start == null || end == null) return -1;if (start == end) return 0; // 起点终点相同，路径长度为0Queue<Node> queue1 = new LinkedList<>();Queue<Node> queue2 = new LinkedList<>();Set<Node> visited1 = new HashSet<>();Set<Node> visited2 = new HashSet<>();queue1.offer(start);visited1.add(start);queue2.offer(end);visited2.add(end);int level = 0; // 记录路径长度while (!queue1.isEmpty() && !queue2.isEmpty()) {level++; // 每扩展一层，路径长度增加1// 优先扩展较小的队列，减少搜索空间if (queue1.size() > queue2.size()) {Queue<Node> tempQ = queue1;queue1 = queue2;queue2 = tempQ;Set<Node> tempV = visited1;visited1 = visited2;visited2 = tempV;}int size = queue1.size();for (int i = 0; i < size; i++) {Node current = queue1.poll();for (Node neighbor : current.neighbors) {if (visited2.contains(neighbor)) {return level; // 相遇，找到最短路径}if (!visited1.contains(neighbor)) {visited1.add(neighbor);queue1.offer(neighbor);}}}}return -1; // 无路径
}

🛣️ 标题三：最短路径算法——快递配送路线如何规划？

在带有权重的图中，我们常常需要找到连接两点的“最短”路径，这里的“短”可能指时间、距离或成本。

Dijkstra 算法

特点：适用于没有负权边的加权图，采用贪心思想。
核心步骤：
1. 维护一个优先队列（通常是小顶堆），其中存储 (当前距离, 节点) 对，按距离从小到大排序。
2. 每次从堆中取出距离最小的未访问节点 u。
3. 松弛其所有邻居 v：如果从 u 到 v 的路径比之前已知从起点到 v 的路径更短，则更新 v 的距离并将其加入优先队列。

import heapq # 引入 heapq 模块实现最小堆def dijkstra(graph, start):# graph 示例: {node1: {neighbor1: weight1, neighbor2: weight2}, ...}# dist 字典用于存储从起点到各个节点的最短距离dist = {node: float('inf') for node in graph}dist[start] = 0# 优先队列 (min-heap), 存储 (距离, 节点) 对# 堆中存储的是元组，会根据元组的第一个元素（距离）进行排序heap = [(0, start)]while heap:current_dist, u = heapq.heappop(heap) # 取出距离最小的节点# 如果已经找到更短的路径，则跳过if current_dist > dist[u]:continue# 遍历当前节点 u 的所有邻居 vfor v, weight in graph.get(u, {}).items():if dist[v] > current_dist + weight: # 松弛操作dist[v] = current_dist + weightheapq.heappush(heap, (dist[v], v)) # 更新距离并加入堆return dist

时间复杂度： $\log V)$ （ $E$ 边数， $V$ 节点数），使用优先队列优化后。

Bellman-Ford 算法

特点：适用于包含负权边的加权图，并且能够检测负权环（如果图中有负权环，则某些节点的最短路径将无限小）。
核心步骤：对所有边进行 n-1 轮松弛操作。如果在第 n 轮还能进行松弛，则说明存在负权环。

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;// 边类定义
class Edge {int from, to, weight;Edge(int from, int to, int weight) {this.from = from;this.to = to;this.weight = weight;}
}class BellmanFord {// n: 节点数量，edges: 边的列表public int[] bellmanFord(int n, List<Edge> edges, int startNode) {int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[startNode] = 0;// 进行 n-1 轮松弛操作for (int i = 0; i < n - 1; i++) {boolean updated = false; // 标记本轮是否有更新for (Edge edge : edges) {if (dist[edge.from] != Integer.MAX_VALUE && // 确保起始点可达dist[edge.to] > dist[edge.from] + edge.weight) {dist[edge.to] = dist[edge.from] + edge.weight;updated = true;}}if (!updated) { // 如果一轮下来没有更新，说明已经达到最短路径，可以提前结束break;}}// 检测负权环：再进行一轮松弛for (Edge edge : edges) {if (dist[edge.from] != Integer.MAX_VALUE &&dist[edge.to] > dist[edge.from] + edge.weight) {// System.out.println("检测到负权环！");return null; // 或者返回特殊值表示存在负环}}return dist;}
}

🌉 标题四：高频面试题——岛屿数量问题（连通分量计数）

场景

在一个二维网格中，计算“岛屿”的数量，其中 ‘1’ 代表陆地，‘0’ 代表水。一个岛屿是由水平或垂直相连的陆地组成。这个问题本质上是图的连通分量计数。

def numIslands(grid):if not grid or not grid[0]:return 0rows, cols = len(grid), len(grid[0])count = 0def dfs(r, c):# 边界条件或已访问过的水域/陆地if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':returngrid[r][c] = '#' # 标记为已访问，避免重复计数# 向四个方向探索dfs(r + 1, c)dfs(r - 1, c)dfs(r, c + 1)dfs(r, c - 1)for i in range(rows):for j in range(cols):if grid[i][j] == '1': # 发现新的岛屿count += 1dfs(i, j) # 从当前陆地开始，把整个岛屿都标记为已访问return count

时间复杂度： $O (mn)$ ，其中 $m$ 是行数， $n$ 是列数，因为每个单元格最多被访问一次。

📊 总结表：图算法对比

算法	适用场景	时间复杂度	空间复杂度
BFS	无权图最短路径、层级遍历	$O (V + E)$	$O (V)$
DFS	拓扑排序、连通分量、路径查找	$O (V + E)$	$O (V)$
Dijkstra	无负权边的加权图最短路径	$\log V)$	$O (V)$
Bellman-Ford	含负权边的加权图最短路径、检测负环	$O (V E)$	$O (V)$