四、图的算法体系
4.1 最短路径算法全解析
Dijkstra算法（非负权图）
class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Dijkstra {
// 标准实现 - 使用优先队列 O((V+E) log V)
public int[] dijkstra(List<Edge>[] graph, int source) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// 优先队列：按距离排序
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{source, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0];
int d = curr[1];
if (d > dist[u]) continue; // 过时的条目，跳过
for (Edge edge : graph[u]) {
int v = edge.to;
int newDist = dist[u] + edge.weight;
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(new int[]{v, newDist});
}
}
}
return dist;
}
}
Bellman-Ford算法（支持负权边，可检测负环）
public class BellmanFord {
// 时间复杂度 O(VE)
public int[] bellmanFord(List<Edge>[] graph, int source, boolean[] hasNegativeCycle) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// 松弛操作，重复 V-1 次
for (int i = 0; i < n - 1; i++) {
boolean updated = false;
for (int u = 0; u < n; u++) {
if (dist[u] == Integer.MAX_VALUE) continue;
for (Edge edge : graph[u]) {
int v = edge.to;
if (dist[u] + edge.weight < dist[v]) {
dist[v] = dist[u] + edge.weight;
updated = true;
}
}
}
if (!updated) break; // 提前终止
}
// 第V次松弛：检测负环
for (int u = 0; u < n; u++) {
if (dist[u] == Integer.MAX_VALUE) continue;
for (Edge edge : graph[u]) {
int v = edge.to;
if (dist[u] + edge.weight < dist[v]) {
hasNegativeCycle[0] = true;
return dist;
}
}
}
return dist;
}
}
Floyd-Warshall算法（全源最短路径）
public class FloydWarshall {
// 时间复杂度 O(V³)
public int[][] floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
// 初始化
for (int i = 0; i < n; i++) {
System.arraycopy(graph[i], 0, dist[i], 0, n);
}
// 动态规划：k 作为中间节点
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][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
}
4.2 最小生成树
Kruskal算法（贪心 + 并查集）
class UnionFind { /* 前面已实现 */ }
class Edge implements Comparable<Edge> {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public class Kruskal {
// 时间复杂度 O(E log E)
public List<Edge> kruskal(int n, List<Edge> edges) {
List<Edge> mst = new ArrayList<>();
Collections.sort(edges);
UnionFind uf = new UnionFind(n);
for (Edge edge : edges) {
if (uf.find(edge.u) != uf.find(edge.v)) {
uf.union(edge.u, edge.v);
mst.add(edge);
if (mst.size() == n - 1) break;
}
}
return mst;
}
}
Prim算法（优先队列优化）
public class Prim {
// 时间复杂度 O(E log V)
public int prim(List<Edge>[] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
// 从节点0开始
pq.offer(new int[]{0, 0});
int totalWeight = 0;
int edgeCount = 0;
while (!pq.isEmpty() && edgeCount < n) {
int[] curr = pq.poll();
int u = curr[0];
int weight = curr[1];
if (visited[u]) continue;
visited[u] = true;
totalWeight += weight;
edgeCount++;
for (Edge edge : graph[u]) {
if (!visited[edge.to]) {
pq.offer(new int[]{edge.to, edge.weight});
}
}
}
return totalWeight;
}
}
4.3 拓扑排序（有向无环图）
public class TopologicalSort {
// Kahn算法（BFS）
public List<Integer> kahnTopologicalSort(List<Integer>[] graph) {
int n = graph.length;
int[] inDegree = new int[n];
// 计算入度
for (int i = 0; i < n; i++) {
for (int neighbor : graph[i]) {
inDegree[neighbor]++;
}
}
// 队列存储入度为0的节点
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
result.add(u);
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
// 检查环
if (result.size() != n) {
throw new RuntimeException("图中存在环，无法进行拓扑排序");
}
return result;
}
// DFS方法
public List<Integer> dfsTopologicalSort(List<Integer>[] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
boolean[] onStack = new boolean[n]; // 用于检测环
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfs(i, graph, visited, onStack, stack)) {
throw new RuntimeException("图中存在环");
}
}
}
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
private boolean dfs(int v, List<Integer>[] graph, boolean[] visited,
boolean[] onStack, Stack<Integer> stack) {
visited[v] = true;
onStack[v] = true;
for (int neighbor : graph[v]) {
if (!visited[neighbor]) {
if (dfs(neighbor, graph, visited, onStack, stack)) {
return true;
}
} else if (onStack[neighbor]) {
return true; // 发现环
}
}
onStack[v] = false;
stack.push(v);
return false;
}
}
