圖論算法精解（Java 實現）：從基礎到高頻面試題

一、圖的基礎表示方法

1.1 鄰接矩陣（Adjacency Matrix）

鄰接矩陣是表示圖的一種直觀方式，它使用一個二維數組來存儲節點之間的連接關系。對于一個有 n 個節點的圖，鄰接矩陣是一個 n×n 的矩陣，其中 matrix [i][j] 表示節點 i 到節點 j 的邊的權重。

class GraphMatrix {private int[][] matrix;private int vertexCount;public GraphMatrix(int n) {vertexCount = n;matrix = new int[n][n];}public void addEdge(int from, int to, int weight) {matrix[from][to] = weight;matrix[to][from] = weight; // 無向圖需雙向設置}// 獲取兩個節點之間的邊權重public int getEdgeWeight(int from, int to) {return matrix[from][to];}// 獲取節點的所有鄰接節點public List<Integer> getNeighbors(int node) {List<Integer> neighbors = new ArrayList<>();for (int i = 0; i < vertexCount; i++) {if (matrix[node][i] != 0) {neighbors.add(i);}}return neighbors;}
}

1.2 鄰接表（Adjacency List）

鄰接表是表示稀疏圖的更高效方式，它使用一個列表數組，其中每個元素對應一個節點的所有鄰接節點及其邊的權重。

class GraphList {private List<List<int[]>> adjList; // [鄰接節點, 權重]public GraphList(int n) {adjList = new ArrayList<>();for (int i = 0; i < n; i++) {adjList.add(new ArrayList<>());}}public void addEdge(int from, int to, int weight) {adjList.get(from).add(new int[]{to, weight});adjList.get(to).add(new int[]{from, weight}); // 無向圖需添加反向邊}// 獲取節點的所有鄰接邊public List<int[]> getEdges(int node) {return adjList.get(node);}// 獲取圖的鄰接表表示public List<List<int[]>> getAdjList() {return adjList;}
}

1.3 兩種表示法的對比

特性	鄰接矩陣	鄰接表
空間復雜度	O(V2)	O(V + E)
查詢邊是否存在	O(1)	O(k)
遍歷鄰接節點	O(V)	O(1)~O(k)
適用場景	稠密圖	稀疏圖

鄰接矩陣的優勢在于快速查詢任意兩個節點之間的邊，但空間效率較低，適合節點數量較少的稠密圖。
鄰接表的優勢在于節省空間，適合節點數量較多的稀疏圖，但查詢特定邊的效率較低。

二、基礎圖遍歷算法

2.1 深度優先搜索（DFS）

深度優先搜索是一種遞歸遍歷圖的方法，它沿著一條路徑盡可能深地訪問節點，直到無法繼續，然后回溯。

// 遞歸實現DFS
void dfs(List<List<Integer>> graph, int start) {boolean[] visited = new boolean[graph.size()];dfsHelper(graph, start, visited);
}private void dfsHelper(List<List<Integer>> graph, int node, boolean[] visited) {visited[node] = true;System.out.print(node + " ");for (int neighbor : graph.get(node)) {if (!visited[neighbor]) {dfsHelper(graph, neighbor, visited);}}
}// 迭代實現DFS（使用棧）
void dfsIterative(List<List<Integer>> graph, int start) {boolean[] visited = new boolean[graph.size()];Stack<Integer> stack = new Stack<>();stack.push(start);while (!stack.isEmpty()) {int node = stack.pop();if (!visited[node]) {visited[node] = true;System.out.print(node + " ");// 注意：棧是后進先出，所以先將鄰接節點逆序壓入棧List<Integer> neighbors = graph.get(node);for (int i = neighbors.size() - 1; i >= 0; i--) {if (!visited[neighbors.get(i)]) {stack.push(neighbors.get(i));}}}}
}

2.2 廣度優先搜索（BFS）

廣度優先搜索是一種逐層遍歷圖的方法，它使用隊列來保存待訪問的節點，先訪問距離起始節點最近的所有節點，然后逐層向外擴展。

void bfs(List<List<Integer>> graph, int start) {boolean[] visited = new boolean[graph.size()];Queue<Integer> queue = new LinkedList<>();queue.offer(start);visited[start] = true;while (!queue.isEmpty()) {int node = queue.poll();System.out.print(node + " ");for (int neighbor : graph.get(node)) {if (!visited[neighbor]) {visited[neighbor] = true;queue.offer(neighbor);}}}
}// BFS的應用：計算最短路徑（無權圖）
int[] shortestPath(List<List<Integer>> graph, int start) {int n = graph.size();int[] dist = new int[n];Arrays.fill(dist, -1); // -1表示不可達Queue<Integer> queue = new LinkedList<>();queue.offer(start);dist[start] = 0;while (!queue.isEmpty()) {int node = queue.poll();for (int neighbor : graph.get(node)) {if (dist[neighbor] == -1) {dist[neighbor] = dist[node] + 1;queue.offer(neighbor);}}}return dist;
}

三、最短路徑算法

3.1 Dijkstra 算法（單源最短路徑）

Dijkstra 算法用于計算帶權有向圖或無向圖中，從單個源節點到所有其他節點的最短路徑，要求所有邊的權重非負。

int[] dijkstra(List<List<int[]>> graph, int start) {int n = graph.size();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[] edge : graph.get(u)) {int v = edge[0], w = edge[1];if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.offer(new int[]{v, dist[v]});}}}return dist;
}// 打印最短路徑
List<Integer> getShortestPath(int[] prev, int target) {List<Integer> path = new ArrayList<>();for (int at = target; at != -1; at = prev[at]) {path.add(at);}Collections.reverse(path);return path;
}

3.2 Floyd-Warshall 算法（多源最短路徑）

Floyd-Warshall 算法用于計算帶權圖中所有節點對之間的最短路徑，允許邊的權重為負，但不能包含負權環。

void floydWarshall(int[][] graph) {int n = graph.length;int[][] dist = new int[n][n];// 初始化距離矩陣，將不可達的距離設為無窮大for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {dist[i][j] = 0;} else if (graph[i][j] != 0) {dist[i][j] = graph[i][j];} else {dist[i][j] = Integer.MAX_VALUE;}}}// 三重循環更新距離for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 檢查負權環for (int i = 0; i < n; i++) {if (dist[i][i] < 0) {System.out.println("圖包含負權環");return;}}// 打印最短路徑矩陣for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print((dist[i][j] == Integer.MAX_VALUE ? "INF" : dist[i][j]) + "\t");}System.out.println();}
}

四、最小生成樹算法

4.1 Prim 算法（鄰接矩陣版）

Prim 算法是一種貪心算法，用于在帶權無向圖中找到最小生成樹（MST）。

int primMST(int[][] graph) {int n = graph.length;int[] key = new int[n];       // 存儲最小邊權值boolean[] mstSet = new boolean[n]; // 標記節點是否已加入MSTint[] parent = new int[n];    // 存儲每個節點的父節點Arrays.fill(key, Integer.MAX_VALUE);key[0] = 0;  // 從節點0開始parent[0] = -1; // 根節點的父節點為-1int totalWeight = 0;for (int count = 0; count < n; count++) {// 選擇key值最小且未被加入MST的節點int u = -1;for (int i = 0; i < n; i++) {if (!mstSet[i] && (u == -1 || key[i] < key[u])) {u = i;}}mstSet[u] = true;totalWeight += key[u];// 更新鄰接頂點的key值和parentfor (int v = 0; v < n; v++) {if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {key[v] = graph[u][v];parent[v] = u;}}}// 打印MST的邊System.out.println("Edge \tWeight");for (int i = 1; i < n; i++) {System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);}return totalWeight;
}

4.2 Kruskal 算法（并查集優化）

Kruskal 算法也是一種貪心算法，用于找到帶權無向圖的最小生成樹。

class Kruskal {class UnionFind {private int[] parent;private int[] rank;public UnionFind(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}// 路徑壓縮public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 按秩合并public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) return;if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}public int kruskalMST(int[][] edges, int n) {// 按邊權排序Arrays.sort(edges, (a, b) -> a[2] - b[2]);UnionFind uf = new UnionFind(n);int mstWeight = 0;int edgeCount = 0;for (int[] edge : edges) {int u = edge[0];int v = edge[1];int w = edge[2];// 檢查是否會形成環if (uf.find(u) != uf.find(v)) {uf.union(u, v);mstWeight += w;edgeCount++;// MST的邊數為n-1時結束if (edgeCount == n - 1) break;}}return mstWeight;}
}

五、高頻面試題解析

5.1 課程表 II（LeetCode 210）拓撲排序

題目描述：給定課程總數和先決條件，返回一個有效的課程學習順序。如果不可能，則返回空數組。

public int[] findOrder(int numCourses, int[][] prerequisites) {List<List<Integer>> graph = new ArrayList<>();int[] inDegree = new int[numCourses];// 初始化圖和入度數組for (int i = 0; i < numCourses; i++) {graph.add(new ArrayList<>());}// 構建圖和入度數組for (int[] p : prerequisites) {graph.get(p[1]).add(p[0]);inDegree[p[0]]++;}// 將入度為0的節點加入隊列Queue<Integer> q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) q.offer(i);}// 拓撲排序int[] result = new int[numCourses];int idx = 0;while (!q.isEmpty()) {int u = q.poll();result[idx++] = u;for (int v : graph.get(u)) {if (--inDegree[v] == 0) {q.offer(v);}}}// 檢查是否所有課程都能被安排return idx == numCourses ? result : new int[0];
}

5.2 網絡延遲時間（LeetCode 743）Dijkstra 應用

題目描述：給定一個網絡，計算從給定節點出發，信號到達所有其他節點的最短時間。如果無法到達所有節點，返回 - 1。

public int networkDelayTime(int[][] times, int n, int k) {// 構建鄰接表List<List<int[]>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int[] time : times) {graph.get(time[0]).add(new int[]{time[1], time[2]});}// 初始化距離數組int[] dist = new int[n + 1];Arrays.fill(dist, Integer.MAX_VALUE);dist[k] = 0;// 使用優先隊列實現Dijkstra算法PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);pq.offer(new int[]{k, 0});while (!pq.isEmpty()) {int[] curr = pq.poll();int u = curr[0], d = curr[1];// 如果當前距離大于已記錄的最短距離，跳過if (d > dist[u]) continue;// 遍歷所有鄰接邊for (int[] edge : graph.get(u)) {int v = edge[0], w = edge[1];if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.offer(new int[]{v, dist[v]});}}}// 找到最大延遲時間int max = 0;for (int i = 1; i <= n; i++) {if (dist[i] == Integer.MAX_VALUE) return -1;max = Math.max(max, dist[i]);}return max;
}

六、算法優化技巧

6.1 Dijkstra 算法優化

優先隊列選擇：使用斐波那契堆可將時間復雜度降至 O (E + VlogV)
雙向搜索：同時從起點和終點進行搜索，減少搜索空間
A * 算法：啟發式搜索，利用距離估計函數加速搜索

6.2 并查集路徑壓縮

int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路徑壓縮}return parent[x];
}

6.3 記憶化搜索

// 用于存在性路徑問題
int[][] memo;int dfsMemo(int[][] graph, int u, int target) {if (u == target) return 1;if (memo[u][target] != 0) return memo[u][target];for (int v : graph[u]) {if (dfsMemo(graph, v, target) == 1) {memo[u][target] = 1;return 1;}}memo[u][target] = -1;return -1;
}

七、常見問題及解決方案

問題類型	解決方法	相關算法
負權邊檢測	Bellman-Ford 算法	單源最短路徑
檢測環路	拓撲排序 / DFS 訪問標記	有向無環圖判斷
連通分量	并查集 / BFS/DFS	圖連通性判斷
關鍵路徑	拓撲排序 + 動態規劃	AOE 網絡