引言

图是复杂的数据结构。本文介绍图的核心算法和应用。

一、图的表示

1.1 邻接矩阵

1
2
3
4
5
6
int[][] graph = {
    {0, 1, 1, 0},
    {1, 0, 1, 1},
    {1, 1, 0, 1},
    {0, 1, 1, 0}
};

1.2 邻接表

1
2
3
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 2, 3));

二、图遍历

2.1 DFS（深度优先）

1
2
3
4
5
6
7
8
9
10
public void dfs(int node, boolean[] visited, Map<Integer, List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

2.2 BFS（广度优先）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void bfs(int start, Map<Integer, List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

三、最短路径

3.1 Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] dijkstra(int[][] graph, int start) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0];
        
        for (int i = 0; i < n; i++) {
            if (graph[node][i] > 0) {
                int newDist = dist[node] + graph[node][i];
                if (newDist < dist[i]) {
                    dist[i] = newDist;
                    pq.offer(new int[]{i, newDist});
                }
            }
        }
    }
    
    return dist;
}

总结

图算法核心：

  1. 遍历：DFS、BFS
  2. 最短路径：Dijkstra、Floyd
  3. 拓扑排序：AOV网
  4. 最小生成树：Kruskal、Prim

参考资料

  • 《算法导论》