图论算法 (Graph Algorithms)

graph algorithmsBFSDFSLeetCodealgorithminterview

图论算法 (Graph Algorithms)

图是一种由节点（顶点）和边组成的非线性数据结构，可以表示各种复杂的关系和网络。

基础概念

图的表示

  1. 邻接表
顶点 -> 邻居列表
0 -> [1, 2]
1 -> [0, 2, 3]
2 -> [0, 1]
3 -> [1]
  1. 邻接矩阵
  0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 0
3 0 1 0 0

图的类型

  1. 有向图 vs 无向图
无向图:        有向图:
A --- B        A --→ B
|     |        ↑     |
C --- D        C ←-- D
  1. 带权图
A --3-- B
|       |
4       5
|       |
C --2-- D
  1. 连通性
连通图:        非连通图:
A --- B        A --- B   C
|     |                  |
C --- D                  D

基本算法

1. 深度优先搜索 (DFS)

     1
   /   \
  2     3
 / \   / \
4   5 6   7

访问顺序: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

2. 广度优先搜索 (BFS)

     1
   /   \
  2     3
 / \   / \
4   5 6   7

访问顺序: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

3. 拓扑排序

依赖关系:
A --> B --> D
|           ↑
└--> C -----┘

拓扑序: A -> B -> C -> D

经典问题

1. 岛屿数量

LeetCode 200 - Number of Islands

使用DFS标记连通区域:

输入网格:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

DFS访问过程:
# # 0 0 0  (#表示已访问)
# # 0 0 0
0 0 1 0 0
0 0 0 1 1

发现岛屿数: 3
def numIslands(grid):
    if not grid:
        return 0
        
    def dfs(i, j):
        if (i < 0 or i >= len(grid) or 
            j < 0 or j >= len(grid[0]) or
            grid[i][j] != '1'):
            return
        
        grid[i][j] = '#'  # 标记已访问
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

2. 课程表 (拓扑排序)

LeetCode 207 - Course Schedule

检测课程依赖中是否有环:

课程依赖:
0 <- 1 <- 3
     ↓    ↑
     2 ---┘

入度统计:
课程 0: 1
课程 1: 1
课程 2: 1
课程 3: 1

拓扑排序:
3 -> 1 -> 2 -> 0
def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    
    # 建图并统计入度
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
    
    # 将所有入度为0的课程加入队列
    from collections import deque
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    
    count = 0
    while queue:
        prereq = queue.popleft()
        count += 1
        
        for course in graph[prereq]:
            indegree[course] -= 1
            if indegree[course] == 0:
                queue.append(course)
    
    return count == numCourses

3. 网络延迟时间 (Dijkstra算法)

LeetCode 743 - Network Delay Time

使用Dijkstra算法找最短路径:

网络拓扑:
  2
1 --→ 2
| ↗   ↓
4 3 --→ 3
  1

距离更新过程:
节点1: 0
节点2: 2
节点3: 3
节点4: 4
def networkDelayTime(times, n, k):
    from collections import defaultdict
    import heapq
    
    # 建图
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # 距离数组
    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    
    # 优先队列
    pq = [(0, k)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
            
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    max_dist = max(dist[1:])
    return max_dist if max_dist < float('inf') else -1

4. 冗余连接 (并查集)

LeetCode 684 - Redundant Connection

使用并查集检测环:

输入边:
1 -- 2
|    |
4 -- 3

添加边 4-1 时检测到环:
1 -- 2
|    |
4 -- 3
def findRedundantConnection(edges):
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    n = len(edges)
    parent = list(range(n + 1))
    
    for x, y in edges:
        if find(x) == find(y):
            return [x, y]
        union(x, y)
    
    return []

高级算法

1. 最小生成树

  • Kruskal算法：按边权重排序，使用并查集
  • Prim算法：从点出发，使用优先队列

2. 最短路径

  • Dijkstra：单源最短路径（无负权）
  • Bellman-Ford：单源最短路径（可负权）
  • Floyd-Warshall：多源最短路径

3. 强连通分量

  • Kosaraju算法
  • Tarjan算法

常见技巧

  1. DFS解决连通性问题
  2. BFS解决最短路径问题
  3. 拓扑排序解决依赖问题
  4. 并查集处理动态连通性
  5. 双向BFS优化搜索

相关题目