一、图存储有权图通用存储ListListEdge// 边结构体 class Edge { int to; int weight; Edge(int to, int weight) { this.to to; this.weight weight; } }二、DFS 深度优先遍历原理递归深度遍历回溯访问所有节点。复杂度O(VE)import java.util.*; public class GraphDFS { static boolean[] visited; public static void dfs(ListListInteger graph, int cur) { visited[cur] true; System.out.print(cur ); for (int next : graph.get(cur)) { if (!visited[next]) { dfs(graph, next); } } } public static void main(String[] args) { // 无向无权图邻接表 ListListInteger graph new ArrayList(); for (int i 0; i 6; i) graph.add(new ArrayList()); graph.get(0).addAll(Arrays.asList(1, 2)); graph.get(1).addAll(Arrays.asList(0, 3, 4)); graph.get(2).addAll(Arrays.asList(0, 5)); graph.get(3).addAll(Arrays.asList(1)); graph.get(4).addAll(Arrays.asList(1, 5)); graph.get(5).addAll(Arrays.asList(2, 4)); visited new boolean[6]; dfs(graph, 0); } }三、BFS 广度优先遍历无权最短路径原理队列分层遍历天然求解无权图最短路径。复杂度O(VE)import java.util.*; public class GraphBFS { public static void bfs(ListListInteger graph, int start) { boolean[] visited new boolean[graph.size()]; QueueInteger queue new LinkedList(); queue.offer(start); visited[start] true; while (!queue.isEmpty()) { int cur queue.poll(); System.out.print(cur ); for (int next : graph.get(cur)) { if (!visited[next]) { visited[next] true; queue.offer(next); } } } } public static void main(String[] args) { ListListInteger graph new ArrayList(); for (int i 0; i 6; i) graph.add(new ArrayList()); graph.get(0).addAll(Arrays.asList(1, 2)); graph.get(1).addAll(Arrays.asList(0, 3, 4)); graph.get(2).addAll(Arrays.asList(0, 5)); graph.get(3).addAll(Arrays.asList(1)); graph.get(4).addAll(Arrays.asList(1, 5)); graph.get(5).addAll(Arrays.asList(2, 4)); bfs(graph, 0); } }四、Dijkstra 最短路径无负权、单源原理贪心 小根堆松弛约束不支持负权边复杂度O(E log V)import java.util.*; class Edge { int to, weight; Edge(int t, int w) { to t; weight w; } } public class Dijkstra { // 堆优化版 public static int[] dijkstra(ListListEdge graph, int start, int n) { int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] 0; // 小根堆: [距离, 节点] PriorityQueueint[] heap new PriorityQueue(Comparator.comparingInt(a - a[0])); heap.offer(new int[]{0, start}); boolean[] vis new boolean[n]; while (!heap.isEmpty()) { int[] cur heap.poll(); int curDist cur[0]; int u cur[1]; if (vis[u]) continue; vis[u] true; for (Edge e : graph.get(u)) { int v e.to; int w e.weight; if (dist[u] ! Integer.MAX_VALUE dist[v] dist[u] w) { dist[v] dist[u] w; heap.offer(new int[]{dist[v], v}); } } } return dist; } public static void main(String[] args) { int n 5; ListListEdge graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); graph.get(0).add(new Edge(1, 2)); graph.get(0).add(new Edge(2, 5)); graph.get(1).add(new Edge(0, 2)); graph.get(1).add(new Edge(3, 1)); graph.get(2).add(new Edge(0, 5)); graph.get(2).add(new Edge(4, 3)); graph.get(3).add(new Edge(1, 1)); graph.get(3).add(new Edge(4, 2)); graph.get(4).add(new Edge(2, 3)); graph.get(4).add(new Edge(3, 2)); int[] res dijkstra(graph, 0, n); System.out.println(Arrays.toString(res)); } }五、Bellman-Ford支持负权、判负环原理V-1 轮全局松弛特性可检测负权环复杂度O(VE)import java.util.*; class BellEdge { int u, v, w; BellEdge(int u, int v, int w) { this.u u; this.v v; this.w w; } } public class BellmanFord { // 返回是否存在负环 public static boolean bellmanFord(ListBellEdge edges, int n, int start, int[] dist) { Arrays.fill(dist, Integer.MAX_VALUE); dist[start] 0; // V-1轮松弛 for (int i 0; i n - 1; i) { boolean update false; for (BellEdge e : edges) { if (dist[e.u] ! Integer.MAX_VALUE dist[e.v] dist[e.u] e.w) { dist[e.v] dist[e.u] e.w; update true; } } if (!update) break; } // 第V轮检测负环 for (BellEdge e : edges) { if (dist[e.u] ! Integer.MAX_VALUE dist[e.v] dist[e.u] e.w) { return true; } } return false; } public static void main(String[] args) { ListBellEdge edges new ArrayList(); edges.add(new BellEdge(0,1,2)); edges.add(new BellEdge(0,2,5)); edges.add(new BellEdge(1,3,1)); int[] dist new int[5]; boolean hasCircle bellmanFord(edges, 5, 0, dist); System.out.println(存在负环 hasCircle); System.out.println(Arrays.toString(dist)); } }六、Floyd 多源最短路径原理动态规划中转松弛特性一次计算任意两点最短路复杂度O(V³)import java.util.*; public class Floyd { public static void floyd(int[][] dist, int 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][j] Math.min(dist[i][j], dist[i][k] dist[k][j]); } } } } } public static void main(String[] args) { int n 4; int[][] dist new int[n][n]; for (int i 0; i n; i) { Arrays.fill(dist[i], Integer.MAX_VALUE); dist[i][i] 0; } dist[0][1] 2; dist[0][2] 5; dist[1][3] 1; floyd(dist, n); for (int[] row : dist) { System.out.println(Arrays.toString(row)); } } }七、Kruskal 最小生成树稀疏图原理边排序 并查集判环复杂度O(E log E)import java.util.*; class KrusEdge implements ComparableKrusEdge{ int u, v, w; KrusEdge(int u, int v, int w){ this.u u; this.v v; this.w w; } Override public int compareTo(KrusEdge o) { return this.w - o.w; } } // 并查集 class UnionFind { int[] parent; public UnionFind(int n) { parent new int[n]; for (int i 0; i n; i) parent[i] i; } public int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } public boolean union(int x, int y) { int fx find(x), fy find(y); if (fx fy) return false; parent[fx] fy; return true; } } public class Kruskal { public static int kruskal(ListKrusEdge edges, int n) { Collections.sort(edges); UnionFind uf new UnionFind(n); int res 0; int cnt 0; for (KrusEdge e : edges) { if (uf.union(e.u, e.v)) { res e.w; cnt; if (cnt n - 1) break; } } return cnt n - 1 ? res : -1; } public static void main(String[] args) { ListKrusEdge edges new ArrayList(); edges.add(new KrusEdge(0,1,2)); edges.add(new KrusEdge(0,2,5)); edges.add(new KrusEdge(1,2,1)); System.out.println(kruskal(edges, 3)); } }八、Prim 最小生成树稠密图原理贪心迭代扩展最小边复杂度O(V²) / 堆优化 O(E log V)import java.util.*; class EdgeP { int to, w; EdgeP(int t, int w) { to t; this.w w; } } public class Prim { public static int prim(ListListEdgeP graph, int n) { int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); boolean[] vis new boolean[n]; dist[0] 0; int res 0; for (int i 0; i n; i) { // 找当前最短边节点 int cur -1; int minVal Integer.MAX_VALUE; for (int j 0; j n; j) { if (!vis[j] dist[j] minVal) { minVal dist[j]; cur j; } } if (cur -1) return -1; vis[cur] true; res minVal; // 更新邻边 for (EdgeP e : graph.get(cur)) { if (!vis[e.to] e.w dist[e.to]) { dist[e.to] e.w; } } } return res; } public static void main(String[] args) { int n 3; ListListEdgeP graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); graph.get(0).add(new EdgeP(1,2)); graph.get(0).add(new EdgeP(2,5)); graph.get(1).add(new EdgeP(0,2)); graph.get(1).add(new EdgeP(2,1)); graph.get(2).add(new EdgeP(0,5)); graph.get(2).add(new EdgeP(1,1)); System.out.println(prim(graph, n)); } }九、拓扑排序Java 入度法适用有向无环图 DAG可判环复杂度O(VE)import java.util.*; public class TopSort { public static ListInteger topSort(ListListInteger graph, int n) { int[] inDegree new int[n]; // 统计入度 for (ListInteger nexts : graph) { for (int v : nexts) inDegree[v]; } QueueInteger q new LinkedList(); for (int i 0; i n; i) { if (inDegree[i] 0) q.offer(i); } ListInteger res new ArrayList(); while (!q.isEmpty()) { int cur q.poll(); res.add(cur); for (int next : graph.get(cur)) { if (--inDegree[next] 0) { q.offer(next); } } } // res.size() ! n 代表有环 return res; } public static void main(String[] args) { int n 4; ListListInteger graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); graph.get(0).add(1); graph.get(0).add(2); graph.get(1).add(3); graph.get(2).add(3); System.out.println(topSort(graph, n)); } }十、算法速查表算法核心条件时间复杂度DFS/BFS通用遍历O(VE)Dijkstra单源、无负权O(E log V)Bellman-Ford单源、可负权、可判环O(VE)Floyd多源、小规模O(V³)Kruskal最小生成树、稀疏图O(E log E)Prim最小生成树、稠密图O(V²)拓扑排序DAG 有向无环图O(VE)