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

用Java手搓图结构：从邻接矩阵到经典算法的实战指南

很多Java开发者面对图算法时总感到无从下手——明明看懂了DFS、BFS的理论，遇到实际问题却不知如何用代码实现。本文将带你从零构建图结构，通过可运行的完整代码示例，直观理解这些算法的实际运行逻辑。不同于单纯的理论讲解，我们会采用"实现优先"的方式，让你在编码过程中自然掌握算法精髓。

1. 图结构的基石：邻接矩阵实现

我们先从最基础的邻接矩阵开始构建图结构。邻接矩阵用二维数组表示顶点间的连接关系，适合表示稠密图。下面是一个完整的无向图实现：

public class Graph { private List<String> 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) { Stack<Integer> 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) { Queue<Integer> 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的典型应用包括：

• 最短路径问题（无权图）
• 社交网络中的好友推荐
• 网络爬虫的页面抓取策略
• 广播消息的传播

对比两种遍历方式：

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]; PriorityQueue<Node> 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 Comparable<Node> { 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. 图算法的实战应用与性能考量

在实际项目中，选择图算法时需要综合考虑以下因素：

时间复杂度对比：

内存优化技巧：

1. 稀疏图使用邻接表代替邻接矩阵
2. 对于大规模图，考虑使用压缩稀疏行(CSR)格式
3. 并行化处理：如将图分区后并行执行BFS
4. 使用位图代替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算法在不同权重分布下的性能表现。