图算法入门：BFS、DFS、最短路径

图算法是计算机科学的核心。本文介绍图的基本算法。

图的表示

邻接矩阵

int[][] graph = new int[n][n];
graph[0][1] = 1; // 0→1 有边

邻接表

List<List<Integer>> graph = new ArrayList<>();
graph.get(0).add(1); // 0→1 有边

BFS（广度优先搜索）

void bfs(List<List<Integer>> graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                queue.offer(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

应用： 最短路径、层序遍历

DFS（深度优先搜索）

void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
    System.out.println(node);
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

应用： 连通分量、拓扑排序

最短路径（Dijkstra）

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 u = curr[0], d = curr[1];
        
        if (d > dist[u]) continue;
        
        for (int v = 0; v < n; v++) {
            if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    
    return dist;
}

总结

BFS 和 DFS 是图算法的基础。掌握这两种遍历方式，可以解决大部分图相关问题。