别再死记硬背了！用Java手搓图算法（DFS/BFS/Dijkstra/Prim/Kruskal），从邻接矩阵到完整实现
·
用Java手搓图算法：从邻接矩阵到完整实现
在计算机科学的世界里，图算法就像是一把瑞士军刀，能解决从社交网络分析到路径规划的各种问题。但很多学习者在掌握了理论后，面对实际编码时却常常手足无措。本文将带你用Java从零开始实现五种核心图算法，通过"手搓代码"的方式深入理解算法本质，告别死记硬背。
1. 图的表示：邻接矩阵实现
邻接矩阵是图最直观的表示方式之一。让我们先构建这个基础结构：
public class Graph {
private List<Integer> vertexList; // 顶点集合
private int[][] adjacencyMatrix; // 邻接矩阵
private int edgeCount; // 边数统计
public Graph(int vertexCount) {
this.vertexList = new ArrayList<>(vertexCount);
this.adjacencyMatrix = new int[vertexCount][vertexCount];
this.edgeCount = 0;
}
// 添加顶点
public void addVertex(int vertex) {
vertexList.add(vertex);
}
// 添加边（无向图）
public void addEdge(int v1, int v2, int weight) {
adjacencyMatrix[v1][v2] = weight;
adjacencyMatrix[v2][v1] = weight; // 无向图需要对称设置
edgeCount++;
}
// 可视化邻接矩阵
public void printMatrix() {
for (int[] row : adjacencyMatrix) {
System.out.println(Arrays.toString(row));
}
}
}
关键点说明 ：
- 使用二维数组存储顶点间的连接关系
- 无向图的矩阵是对称的
- 权值为0表示顶点间没有直接连接
提示：在实际应用中，可以考虑使用稀疏矩阵优化存储空间，特别是对于边数远小于完全图的场景。
2. 图的遍历：DFS与BFS实现
2.1 深度优先搜索(DFS)
DFS像探险家一样深入图的每个分支：
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertexList.size()];
dfsRecursive(startVertex, visited);
}
private void dfsRecursive(int current, boolean[] visited) {
visited[current] = true;
System.out.print(current + " ");
for (int neighbor = 0; neighbor < vertexList.size(); neighbor++) {
if (adjacencyMatrix[current][neighbor] != 0 && !visited[neighbor]) {
dfsRecursive(neighbor, visited);
}
}
}
非递归实现（使用栈） ：
public void dfsIterative(int startVertex) {
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[vertexList.size()];
stack.push(startVertex);
visited[startVertex] = true;
while (!stack.isEmpty()) {
int current = stack.pop();
System.out.print(current + " ");
for (int neighbor = vertexList.size()-1; neighbor >= 0; neighbor--) {
if (adjacencyMatrix[current][neighbor] != 0 && !visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
}
2.2 广度优先搜索(BFS)
BFS像水波纹一样逐层扩展：
public void bfs(int startVertex) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[vertexList.size()];
queue.offer(startVertex);
visited[startVertex] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int neighbor = 0; neighbor < vertexList.size(); neighbor++) {
if (adjacencyMatrix[current][neighbor] != 0 && !visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
性能对比 ：
| 算法 | 数据结构 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| DFS | 栈 | O(V+E) | O(V) | 拓扑排序、连通分量 |
| BFS | 队列 | O(V+E) | O(V) | 最短路径(无权图)、层级遍历 |
3. 最短路径：Dijkstra算法
Dijkstra算法解决单源最短路径问题：
public void dijkstra(int source) {
int[] distances = new int[vertexList.size()];
boolean[] visited = new boolean[vertexList.size()];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
for (int i = 0; i < vertexList.size(); i++) {
int u = minDistance(distances, visited);
visited[u] = true;
for (int v = 0; v < vertexList.size(); v++) {
if (!visited[v] && adjacencyMatrix[u][v] != 0 &&
distances[u] != Integer.MAX_VALUE &&
distances[u] + adjacencyMatrix[u][v] < distances[v]) {
distances[v] = distances[u] + adjacencyMatrix[u][v];
}
}
}
printDistances(distances, source);
}
private int minDistance(int[] dist, boolean[] visited) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < vertexList.size(); v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
算法特点 ：
- 只适用于非负权图
- 使用贪心策略，每次选择当前最短路径
- 时间复杂度：O(V²)，可用优先队列优化到O(E + VlogV)
注意：当图中存在负权边时，需要使用Bellman-Ford算法替代Dijkstra算法。
4. 最小生成树：Prim和Kruskal算法
4.1 Prim算法
Prim算法从顶点出发构建最小生成树：
public void primMST() {
int[] parent = new int[vertexList.size()];
int[] key = new int[vertexList.size()];
boolean[] mstSet = new boolean[vertexList.size()];
Arrays.fill(key, Integer.MAX_VALUE);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < vertexList.size() - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < vertexList.size(); v++) {
if (adjacencyMatrix[u][v] != 0 && !mstSet[v] &&
adjacencyMatrix[u][v] < key[v]) {
parent[v] = u;
key[v] = adjacencyMatrix[u][v];
}
}
}
printMST(parent);
}
4.2 Kruskal算法
Kruskal算法按边权排序构建最小生成树：
public void kruskalMST() {
Edge[] edges = getAllEdges();
Arrays.sort(edges);
int[] parent = new int[vertexList.size()];
Arrays.fill(parent, -1);
List<Edge> result = new ArrayList<>();
for (Edge edge : edges) {
int x = find(parent, edge.src);
int y = find(parent, edge.dest);
if (x != y) {
result.add(edge);
union(parent, x, y);
}
}
printEdges(result);
}
// 并查集相关方法
private int find(int[] parent, int i) {
if (parent[i] == -1) return i;
return find(parent, parent[i]);
}
private void union(int[] parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
两种算法对比 ：
| 特性 | Prim算法 | Kruskal算法 |
|---|---|---|
| 适用图类型 | 稠密图更优 | 稀疏图更优 |
| 时间复杂度 | O(V²) | O(ElogE) |
| 数据结构 | 优先队列 | 并查集 |
| 选择策略 | 顶点优先 | 边优先 |
5. 算法优化与工程实践
5.1 性能优化技巧
- 优先队列优化Dijkstra ：
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
- 邻接表存储稀疏图 ：
List<List<Edge>> adjList = new ArrayList<>();
- 记忆化搜索减少重复计算
5.2 常见陷阱与解决方案
- 非连通图处理 ：
for (int i = 0; i < vertexList.size(); i++) {
if (!visited[i]) {
dfs(i, visited);
}
}
- 负权环检测 ：
// Bellman-Ford算法中可以检测负权环
if (distances[u] != Integer.MAX_VALUE &&
distances[u] + weight < distances[v]) {
// 第V次迭代仍能松弛则存在负权环
}
- 堆优化Prim的边界条件 ：
while (!pq.isEmpty() && mstSet.size() < vertexList.size()) {
// ...
}
5.3 测试用例设计
设计全面的测试场景：
- 空图
- 单顶点图
- 完全图
- 带负权边的图(对Dijkstra)
- 非连通图
- 存在环的图
@Test
public void testDijkstraWithDisconnectedGraph() {
Graph graph = new Graph(4);
graph.addEdge(0, 1, 1);
graph.addEdge(2, 3, 2);
// 断言0到3不可达
}
通过从零实现这些图算法，你会发现算法不再是一堆需要死记硬背的规则，而是解决实际问题的有力工具。记住，理解算法的最好方式就是亲手实现它，遇到问题时通过调试和可视化来加深理解。
更多推荐
7
0- 0
已为社区贡献33条内容
所有评论(0)