别再死记硬背了！用Java手搓一个图结构，把DFS、BFS、Dijkstra都跑一遍

用Java手搓图结构从邻接矩阵到经典算法的实战指南很多Java开发者面对图算法时总感到无从下手——明明看懂了DFS、BFS的理论遇到实际问题却不知如何用代码实现。本文将带你从零构建图结构通过可运行的完整代码示例直观理解这些算法的实际运行逻辑。不同于单纯的理论讲解我们会采用实现优先的方式让你在编码过程中自然掌握算法精髓。1. 图结构的基石邻接矩阵实现我们先从最基础的邻接矩阵开始构建图结构。邻接矩阵用二维数组表示顶点间的连接关系适合表示稠密图。下面是一个完整的无向图实现public class Graph { private ListString vertexList; // 存储顶点名称 private int[][] edges; // 邻接矩阵 private int edgeCount; // 边数统计 public Graph(int vertexNum) { this.vertexList new ArrayList(vertexNum); this.edges new int[vertexNum][vertexNum]; this.edgeCount 0; } // 添加顶点 public void addVertex(String vertex) { vertexList.add(vertex); } // 添加边无向图 public void addEdge(int v1, int v2, int weight) { edges[v1][v2] weight; edges[v2][v1] weight; // 无向图需要对称设置 edgeCount; } // 获取顶点数量 public int getVertexCount() { return vertexList.size(); } // 打印邻接矩阵 public void printMatrix() { for (int[] row : edges) { System.out.println(Arrays.toString(row)); } } }测试这个基础图结构public static void main(String[] args) { Graph graph new Graph(5); graph.addVertex(A); graph.addVertex(B); graph.addVertex(C); graph.addVertex(D); graph.addVertex(E); graph.addEdge(0, 1, 1); // A-B graph.addEdge(0, 2, 1); // A-C graph.addEdge(1, 3, 1); // B-D graph.addEdge(2, 4, 1); // C-E System.out.println(邻接矩阵表示); graph.printMatrix(); System.out.println(顶点数 graph.getVertexCount()); System.out.println(边数 graph.edgeCount); }提示邻接矩阵的空间复杂度为O(V²)当边数远小于顶点数的平方时考虑使用邻接表更节省空间2. 深度优先搜索(DFS)的实现与可视化DFS的核心思想是一条路走到黑用递归可以最直观地实现public void dfs(int startIndex) { boolean[] visited new boolean[vertexList.size()]; dfsRecursive(startIndex, visited); } private void dfsRecursive(int current, boolean[] visited) { System.out.print(vertexList.get(current) - ); visited[current] true; for (int i 0; i vertexList.size(); i) { if (edges[current][i] ! 0 !visited[i]) { dfsRecursive(i, visited); } } }非递归实现使用栈模拟递归过程public void dfsWithStack(int startIndex) { StackInteger stack new Stack(); boolean[] visited new boolean[vertexList.size()]; stack.push(startIndex); visited[startIndex] true; while (!stack.isEmpty()) { int current stack.pop(); System.out.print(vertexList.get(current) - ); // 注意邻接点入栈顺序保证遍历顺序一致 for (int i vertexList.size()-1; i 0; i--) { if (edges[current][i] ! 0 !visited[i]) { stack.push(i); visited[i] true; } } } }DFS的应用场景包括拓扑排序检测图中的环寻找连通分量解决迷宫问题3. 广度优先搜索(BFS)的层序遍历实现BFS采用层层推进的策略非常适合用队列实现public void bfs(int startIndex) { QueueInteger queue new LinkedList(); boolean[] visited new boolean[vertexList.size()]; queue.offer(startIndex); visited[startIndex] true; while (!queue.isEmpty()) { int current queue.poll(); System.out.print(vertexList.get(current) - ); for (int i 0; i vertexList.size(); i) { if (edges[current][i] ! 0 !visited[i]) { queue.offer(i); visited[i] true; } } } }BFS的典型应用包括最短路径问题无权图社交网络中的好友推荐网络爬虫的页面抓取策略广播消息的传播对比两种遍历方式特性DFSBFS数据结构栈队列空间复杂度O(h)O(w)适用场景拓扑排序、连通性检测最短路径、层级遍历实现方式递归/显式栈队列4. Dijkstra最短路径算法的Java实现Dijkstra算法解决的是带权图中的单源最短路径问题。以下是完整实现public void dijkstra(int startIndex) { int vertexNum vertexList.size(); int[] distances new int[vertexNum]; boolean[] visited new boolean[vertexNum]; Arrays.fill(distances, Integer.MAX_VALUE); distances[startIndex] 0; for (int i 0; i vertexNum; i) { // 找出当前未访问的最近顶点 int minIndex -1; int minDistance Integer.MAX_VALUE; for (int j 0; j vertexNum; j) { if (!visited[j] distances[j] minDistance) { minDistance distances[j]; minIndex j; } } if (minIndex -1) break; visited[minIndex] true; // 更新邻接顶点的距离 for (int k 0; k vertexNum; k) { if (edges[minIndex][k] ! 0 !visited[k]) { int newDistance distances[minIndex] edges[minIndex][k]; if (newDistance distances[k]) { distances[k] newDistance; } } } } // 输出结果 System.out.println(从 vertexList.get(startIndex) 出发的最短路径); for (int i 0; i vertexNum; i) { System.out.println(到 vertexList.get(i) 的最短距离: (distances[i] Integer.MAX_VALUE ? 不可达 : distances[i])); } }优化版本使用优先队列public void dijkstraWithPQ(int startIndex) { int vertexNum vertexList.size(); int[] distances new int[vertexNum]; boolean[] visited new boolean[vertexNum]; PriorityQueueNode pq new PriorityQueue(); Arrays.fill(distances, Integer.MAX_VALUE); distances[startIndex] 0; pq.offer(new Node(startIndex, 0)); while (!pq.isEmpty()) { Node current pq.poll(); if (visited[current.index]) continue; visited[current.index] true; for (int i 0; i vertexNum; i) { if (edges[current.index][i] ! 0 !visited[i]) { int newDistance distances[current.index] edges[current.index][i]; if (newDistance distances[i]) { distances[i] newDistance; pq.offer(new Node(i, newDistance)); } } } } // 输出结果... } class Node implements ComparableNode { int index; int distance; public Node(int index, int distance) { this.index index; this.distance distance; } Override public int compareTo(Node other) { return Integer.compare(this.distance, other.distance); } }注意Dijkstra算法不能处理负权边遇到负权边应考虑Bellman-Ford算法5. 图算法的实战应用与性能考量在实际项目中选择图算法时需要综合考虑以下因素时间复杂度对比算法时间复杂度适用场景DFS/BFSO(V E)连通性检测、简单路径查找DijkstraO(V²) 或 O(E log V)非负权单源最短路径Floyd-WarshallO(V³)所有顶点对最短路径内存优化技巧稀疏图使用邻接表代替邻接矩阵对于大规模图考虑使用压缩稀疏行(CSR)格式并行化处理如将图分区后并行执行BFS使用位图代替boolean数组标记访问状态常见问题排查栈溢出DFS递归过深时改用显式栈内存不足考虑使用磁盘存储部分图数据性能瓶颈使用Profiler定位热点代码错误结果检查是否有未处理的负权边在真实项目中实现这些算法时我习惯添加详细的日志记录遍历过程这不仅能帮助调试还能直观展示算法执行逻辑。比如在Dijkstra实现中可以记录每次松弛操作的细节System.out.printf(从 %s 到 %s原距离 %d新距离 %d %s%n, vertexList.get(u), vertexList.get(v), oldDist, newDist, newDist oldDist ? (更新) : (保持));这种实现方式让抽象的图算法变得具体可见建议读者在理解基础实现后尝试用不同数据集测试观察算法行为的变化。例如可以创建一个包含20个顶点的随机图比较DFS和BFS的遍历顺序差异或者测试Dijkstra算法在不同权重分布下的性能表现。