JAVA:实现Matrix Graphs矩阵图算法（附带源码）
一、项目背景详细介绍
在图论里，图的底层存储主要有两类：邻接表与邻接矩阵。
-
邻接表：适合稀疏图（边远少于 V^2 量级），空间更省，遍历相邻更快。
-
邻接矩阵：用一个 V×V 的二维数组存边，优点是查询两点是否相连 O(1)、实现许多经典算法（如 Floyd-Warshall）更自然，也更便于教学展示。
在工程实践里，若顶点规模中等、图较稠密或需要大量“是否相连”的查询，邻接矩阵常常是更简洁直接的方案。本文实现一个功能完善、易扩展的邻接矩阵图，同时把常见图算法逐一落地。
二、项目需求详细介绍
目标：实现一个泛型的 MatrixGraph<T>，提供以下能力：
-
图结构：
-
支持有向/无向切换；
-
支持带权/无权（无权默认权重 1）；
-
支持泛型顶点标签（如
String、Integer、自定义类型，需实现equals/hashCode）； -
支持动态添加顶点、自动扩容矩阵；
-
INF表示“无边”。
-
-
基本操作：
-
addVertex(T)、addEdge(u,v,w)、removeEdge(u,v)、hasEdge(u,v)、getWeight(u,v)； -
outDegree/inDegree/degree、neighbors(u)；
-
-
图算法：
-
BFS（层次遍历/最短跳数路径）、DFS（递归/迭代两种风格）；
-
Dijkstra（单源最短路，非负权）；
-
Floyd-Warshall（任意两点最短路 + 路径还原）；
-
Prim（最小生成树，假定无向连通，带权）；
-
拓扑排序（Kahn）（仅对有向无环图 DAG）。
-
-
可运行 Demo：
-
构造小图，演示上述算法的输出。
-
三、相关技术详细介绍
-
邻接矩阵：
-
令
matrix[i][j]表示从顶点i到j的边权； -
无边记为
INF（双精度的一个大数）； -
无向图需保持
matrix[i][j] == matrix[j][i]。
-
动态扩容：
-
顶点增加时，如数组满了，就创建新矩阵（容量翻倍），把旧内容复制过去；
-
顶点索引与标签通过
ArrayList<T> vertices+HashMap<T,Integer> indexOf管理。
-
BFS/DFS：
-
BFS 使用队列，按层推进；
-
DFS 可递归或用栈迭代。矩阵上获取相邻点是
O(V)的行扫描。
-
Dijkstra：
-
在矩阵上使用朴素实现：每轮挑选未确定的最小距离点，更新其余点（复杂度 O(V^2)）。非负权前提。
-
Floyd-Warshall：
-
三重循环，典型 O(V^3)。支持任意两点最短路，路径还原通过
next[i][j]记录中转。
-
Prim MST：
-
适用于无向连通带权图，朴素实现 O(V^2)：每次把“未选集合”里与“已选集合”连边最小的一点接入。
-
拓扑排序 Kahn：
-
对有向图计算入度，入度为 0 的入队，反复“删边降度”。若最后序列长度 < V，则有环。
四、实现思路详细介绍
-
以
double[][] matrix存权；INF表示无边，0表示自环（默认不加自环）。 -
用
ArrayList<T> vertices存标签，HashMap<T,Integer> indexOf把顶点映射到行列索引。 -
统一入口：无论有/无权，
addEdge(u,v,w)均可用；若无权，可传1.0。 -
算法对矩阵行进行扫描，辅助数组统一在
MatrixGraph内部生成； -
Floyd 返回
(dist,next)，附带reconstructPath(u,v)。
五、完整实现代码
// 文件：MatrixGraph.java
import java.util.*;
import java.util.stream.Collectors;
public class MatrixGraph<T> {
public static final double INF = 1e18; // 表示无边
private boolean directed;
private double[][] matrix;
private int capacity;
private int n; // 顶点数量
private final ArrayList<T> vertices; // 索引 -> 顶点标签
private final HashMap<T, Integer> indexOf; // 顶点标签 -> 索引
// ===== 构造与初始化 =====
public MatrixGraph(boolean directed, int initialCapacity) {
this.directed = directed;
this.capacity = Math.max(2, initialCapacity);
this.matrix = new double[capacity][capacity];
this.vertices = new ArrayList<>(capacity);
this.indexOf = new HashMap<>(capacity * 2);
this.n = 0;
// 初始化为 INF；对角线 0
for (int i = 0; i < capacity; i++) {
Arrays.fill(matrix[i], INF);
matrix[i][i] = 0.0;
vertices.add(null); // 先占位
}
}
public MatrixGraph(boolean directed) {
this(directed, 8);
}
// ===== 顶点与索引 =====
public boolean containsVertex(T v) {
return indexOf.containsKey(v);
}
public int addVertex(T v) {
Integer idx = indexOf.get(v);
if (idx != null) return idx;
ensureCapacity(n + 1);
vertices.set(n, v);
indexOf.put(v, n);
n++;
return n - 1;
}
public int index(T v) {
Integer idx = indexOf.get(v);
if (idx == null) throw new IllegalArgumentException("顶点不存在: " + v);
return idx;
}
public T vertex(int idx) {
checkIndex(idx);
return vertices.get(idx);
}
public int vertexCount() { return n; }
public boolean isDirected() { return directed; }
private void checkIndex(int i) {
if (i < 0 || i >= n) throw new IndexOutOfBoundsException("非法顶点下标: " + i);
}
// ===== 扩容矩阵 =====
private void ensureCapacity(int need) {
if (need <= capacity) return;
int newCap = Math.max(capacity << 1, need);
double[][] newM = new double[newCap][newCap];
for (int i = 0; i < newCap; i++) {
Arrays.fill(newM[i], INF);
newM[i][i] = 0.0;
}
for (int i = 0; i < n; i++) {
System.arraycopy(matrix[i], 0, newM[i], 0, n);
}
matrix = newM;
// 扩容顶点列表占位
for (int i = vertices.size(); i < newCap; i++) {
vertices.add(null);
}
capacity = newCap;
}
// ===== 边操作 =====
public void addEdge(T u, T v, double w) {
if (w < 0 && directed == false) {
// 允许负边权，但 Dijkstra 不适用；仅提示
}
int iu = containsVertex(u) ? indexOf.get(u) : addVertex(u);
int iv = containsVertex(v) ? indexOf.get(v) : addVertex(v);
matrix[iu][iv] = w;
if (!directed) matrix[iv][iu] = w;
}
public void addEdge(T u, T v) { addEdge(u, v, 1.0); }
public boolean hasEdge(T u, T v) {
int iu = index(u), iv = index(v);
return matrix[iu][iv] < INF / 2;
}
public double getWeight(T u, T v) {
int iu = index(u), iv = index(v);
return matrix[iu][iv];
}
public void removeEdge(T u, T v) {
int iu = index(u), iv = index(v);
matrix[iu][iv] = (iu == iv ? 0.0 : INF);
if (!directed) matrix[iv][iu] = (iu == iv ? 0.0 : INF);
}
// 邻接点（出邻接）
public List<T> neighbors(T u) {
int iu = index(u);
ArrayList<T> res = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (iu != j && matrix[iu][j] < INF / 2) {
res.add(vertices.get(j));
}
}
return res;
}
// 度数
public int outDegree(T u) {
int iu = index(u), deg = 0;
for (int j = 0; j < n; j++) {
if (iu != j && matrix[iu][j] < INF / 2) deg++;
}
return deg;
}
public int inDegree(T u) {
int iu = index(u), deg = 0;
for (int i = 0; i < n; i++) {
if (iu != i && matrix[i][iu] < INF / 2) deg++;
}
return deg;
}
public int degree(T u) {
if (directed) throw new IllegalStateException("有向图没有无向度的定义，请使用 in/outDegree");
return outDegree(u); // 无向图出度=度
}
// ===== BFS（层序遍历 & 最短跳数）=====
public List<T> bfs(T start) {
int s = index(start);
boolean[] vis = new boolean[n];
ArrayDeque<Integer> q = new ArrayDeque<>();
ArrayList<T> order = new ArrayList<>();
vis[s] = true; q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
order.add(vertices.get(u));
for (int v = 0; v < n; v++) {
if (u != v && matrix[u][v] < INF / 2 && !vis[v]) {
vis[v] = true; q.add(v);
}
}
}
return order;
}
// BFS 返回最短跳数距离与前驱（无权图最短路径）
public Map<T, Integer> bfsHops(T start, Map<T, T> parentOut) {
int s = index(start);
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
int[] parent = new int[n]; Arrays.fill(parent, -1);
ArrayDeque<Integer> q = new ArrayDeque<>();
dist[s] = 0; q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v = 0; v < n; v++) {
if (u != v && matrix[u][v] < INF / 2 && dist[v] == Integer.MAX_VALUE) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.add(v);
}
}
}
HashMap<T,Integer> ans = new HashMap<>();
for (int i = 0; i < n; i++) {
ans.put(vertices.get(i), dist[i]);
}
if (parentOut != null) {
parentOut.clear();
for (int i = 0; i < n; i++) if (parent[i] != -1) {
parentOut.put(vertices.get(i), vertices.get(parent[i]));
}
}
return ans;
}
// ===== DFS（递归）=====
public List<T> dfsRecursive(T start) {
int s = index(start);
boolean[] vis = new boolean[n];
ArrayList<T> order = new ArrayList<>();
dfsRecCore(s, vis, order);
return order;
}
private void dfsRecCore(int u, boolean[] vis, List<T> order) {
vis[u] = true;
order.add(vertices.get(u));
for (int v = 0; v < n; v++) {
if (u != v && matrix[u][v] < INF / 2 && !vis[v]) {
dfsRecCore(v, vis, order);
}
}
}
// ===== DFS（迭代）=====
public List<T> dfsIterative(T start) {
int s = index(start);
boolean[] vis = new boolean[n];
ArrayDeque<Integer> st = new ArrayDeque<>();
ArrayList<T> order = new ArrayList<>();
st.push(s);
while (!st.isEmpty()) {
int u = st.pop();
if (vis[u]) continue;
vis[u] = true;
order.add(vertices.get(u));
// 为了与递归结果接近，逆序压栈
for (int v = n - 1; v >= 0; v--) {
if (u != v && matrix[u][v] < INF / 2 && !vis[v]) {
st.push(v);
}
}
}
return order;
}
// ===== Dijkstra（单源最短路，非负权）=====
public Map<T, Double> dijkstra(T src, Map<T, T> parentOut) {
int s = index(src);
double[] dist = new double[n];
boolean[] used = new boolean[n];
int[] parent = new int[n];
Arrays.fill(dist, INF);
Arrays.fill(parent, -1);
dist[s] = 0.0;
for (int i = 0; i < n; i++) {
int u = -1;
double best = INF;
for (int v = 0; v < n; v++) {
if (!used[v] && dist[v] < best) { best = dist[v]; u = v; }
}
if (u == -1) break;
used[u] = true;
for (int v = 0; v < n; v++) {
if (matrix[u][v] < INF / 2 && dist[u] + matrix[u][v] < dist[v]) {
dist[v] = dist[u] + matrix[u][v];
parent[v] = u;
}
}
}
HashMap<T, Double> ans = new HashMap<>();
for (int i = 0; i < n; i++) ans.put(vertices.get(i), dist[i]);
if (parentOut != null) {
parentOut.clear();
for (int i = 0; i < n; i++) if (parent[i] != -1) {
parentOut.put(vertices.get(i), vertices.get(parent[i]));
}
}
return ans;
}
// 根据 parentOut 重建从 s 到 t 的路径（适用于 BFS/Dijkstra 等）
public List<T> reconstructPath(T s, T t, Map<T, T> parent) {
if (parent == null) return Collections.emptyList();
ArrayDeque<T> stack = new ArrayDeque<>();
T cur = t;
stack.push(cur);
while (parent.containsKey(cur)) {
cur = parent.get(cur);
stack.push(cur);
}
if (!stack.peek().equals(s)) return Collections.emptyList();
ArrayList<T> path = new ArrayList<>();
while (!stack.isEmpty()) path.add(stack.pop());
return path;
}
// ===== Floyd-Warshall（全源最短路）=====
public static class FloydResult<T> {
public final double[][] dist;
public final int[][] next; // next[i][j] = i->j 最短路上 i 的后继索引；-1 表示不可达
public final List<T> vertices;
FloydResult(double[][] d, int[][] n, List<T> vs) {
this.dist = d; this.next = n; this.vertices = vs;
}
}
public FloydResult<T> floydWarshall() {
double[][] dist = new double[n][n];
int[][] next = new int[n][n];
for (int i = 0; i < n; i++) {
System.arraycopy(matrix[i], 0, dist[i], 0, n);
for (int j = 0; j < n; j++) {
next[i][j] = (dist[i][j] < INF / 2 && i != j) ? j : -1;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (dist[i][k] >= INF / 2) continue;
for (int j = 0; j < n; j++) {
if (dist[k][j] >= INF / 2) continue;
double nd = dist[i][k] + dist[k][j];
if (nd < dist[i][j]) {
dist[i][j] = nd;
next[i][j] = next[i][k];
}
}
}
}
return new FloydResult<>(dist, next, new ArrayList<>(vertices.subList(0, n)));
}
// 利用 Floyd 的 next 表还原任意两点路径
public List<T> floydPath(FloydResult<T> fr, T from, T to) {
int i = index(from), j = index(to);
if (fr.next[i][j] == -1) return Collections.emptyList();
ArrayList<T> path = new ArrayList<>();
int cur = i;
path.add(fr.vertices.get(cur));
while (cur != j) {
cur = fr.next[cur][j];
path.add(fr.vertices.get(cur));
}
return path;
}
// ===== Prim（MST，仅无向图）=====
public static class MSTResult<T> {
public final Map<T, T> parent;
public final double totalWeight;
MSTResult(Map<T,T> parent, double total) { this.parent = parent; this.totalWeight = total; }
}
public MSTResult<T> prim(T start) {
if (directed) throw new IllegalStateException("Prim 适用于无向图");
int s = index(start);
boolean[] in = new boolean[n];
double[] key = new double[n];
int[] parent = new int[n];
Arrays.fill(key, INF); Arrays.fill(parent, -1);
key[s] = 0.0;
for (int it = 0; it < n; it++) {
int u = -1; double best = INF;
for (int i = 0; i < n; i++) if (!in[i] && key[i] < best) { best = key[i]; u = i; }
if (u == -1) break; // 非连通则提前结束
in[u] = true;
for (int v = 0; v < n; v++) {
if (!in[v] && matrix[u][v] < key[v]) {
key[v] = matrix[u][v];
parent[v] = u;
}
}
}
double total = 0.0;
HashMap<T,T> p = new HashMap<>();
for (int v = 0; v < n; v++) {
if (parent[v] != -1) {
total += matrix[v][parent[v]];
p.put(vertices.get(v), vertices.get(parent[v]));
}
}
return new MSTResult<>(p, total);
}
// ===== 拓扑排序（Kahn，仅有向图）=====
public List<T> topoSort() {
if (!directed) throw new IllegalStateException("拓扑排序仅适用于有向图");
int[] indeg = new int[n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (i != j && matrix[i][j] < INF / 2) indeg[j]++;
}
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
ArrayList<T> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(vertices.get(u));
for (int v = 0; v < n; v++) {
if (u != v && matrix[u][v] < INF / 2) {
if (--indeg[v] == 0) q.add(v);
}
}
}
if (order.size() != n) throw new IllegalStateException("图中存在环，无法拓扑排序");
return order;
}
// ===== 打印/可视化辅助 =====
public String toMatrixString() {
StringBuilder sb = new StringBuilder();
sb.append("Vertices: ").append(vertices.subList(0, n)).append("\n");
sb.append("Adjacency Matrix (INF=.).\n ");
for (int j = 0; j < n; j++) sb.append(String.format("%8s", shortName(vertices.get(j))));
sb.append("\n");
for (int i = 0; i < n; i++) {
sb.append(String.format("%4s", shortName(vertices.get(i))));
for (int j = 0; j < n; j++) {
double w = matrix[i][j];
sb.append(String.format("%8s", w >= INF/2 ? "." : (Math.abs(w - Math.rint(w))<1e-9 ? String.valueOf((int)Math.rint(w)) : String.format("%.2f", w))));
}
sb.append("\n");
}
return sb.toString();
}
private String shortName(T v) {
String s = String.valueOf(v);
return s.length() <= 3 ? s : s.substring(0, 3);
}
// ===== Demo =====
public static void main(String[] args) {
// 无向带权图（用于 Prim / Dijkstra）
MatrixGraph<String> g = new MatrixGraph<>(false);
g.addEdge("A", "B", 4);
g.addEdge("A", "C", 2);
g.addEdge("B", "C", 5);
g.addEdge("B", "D", 10);
g.addEdge("C", "E", 3);
g.addEdge("E", "D", 4);
g.addEdge("D", "F", 11);
System.out.println("== 无向图矩阵 ==");
System.out.println(g.toMatrixString());
System.out.println("BFS from A: " + g.bfs("A"));
System.out.println("DFS(rec) from A: " + g.dfsRecursive("A"));
System.out.println("DFS(iter) from A: " + g.dfsIterative("A"));
Map<String, String> parent = new HashMap<>();
Map<String, Double> dist = g.dijkstra("A", parent);
System.out.println("Dijkstra dist from A: " + dist);
System.out.println("Path A->F: " + g.reconstructPath("A", "F", parent));
MatrixGraph.MSTResult<String> mst = g.prim("A");
System.out.println("Prim MST totalWeight = " + mst.totalWeight);
System.out.println("MST parent map (child -> parent): " + mst.parent);
// 有向无权图（用于 BFS 跳数/拓扑）
MatrixGraph<Integer> dag = new MatrixGraph<>(true);
dag.addEdge(1, 2); dag.addEdge(1, 3);
dag.addEdge(2, 4); dag.addEdge(3, 4);
dag.addEdge(4, 5);
System.out.println("\n== 有向图矩阵 ==");
System.out.println(dag.toMatrixString());
System.out.println("Topo Sort: " + dag.topoSort());
Map<Integer,Integer> p2 = new HashMap<>();
System.out.println("BFS hops from 1: " + dag.bfsHops(1, p2));
System.out.println("Path 1->5 (hops): " + dag.reconstructPath(1, 5, p2));
// Floyd-Warshall（在无向图 g 上）
MatrixGraph.FloydResult<String> fr = g.floydWarshall();
System.out.println("\nFloyd dist(A->F) = " +
fr.dist[g.index("A")][g.index("F")] + ", path: " + g.floydPath(fr, "A", "F"));
}
}
六、代码逐方法解读
1) 结构与存储
-
double[][] matrix：邻接矩阵，INF表示无边；对角线初始化为 0。 -
vertices/indexOf：维护标签↔索引的双向映射，保证顶点泛型化。 -
ensureCapacity：当新增顶点超出容量时，容量翻倍并整体复制旧矩阵，摊还开销可控。
2) 顶点与边基础
-
addVertex(T)：返回新增点的索引，重复添加直接复用旧索引。 -
addEdge(u,v,w)：若不存在顶点，自动补齐；无向图写双向。无权可用默认1.0。 -
neighbors(u)：扫描u行，凡matrix[u][v] < INF即为邻接点。
3) BFS / BFS 跳数
-
bfs(start)：常规层序遍历，给出访问顺序。 -
bfsHops(start,parentOut)：返回最短跳数（无权图最短路径），并把parentOut中记录前驱，可用于reconstructPath还原路径。
4) DFS（递归 / 迭代）
-
递归版结构清晰；
-
迭代版用栈模拟，为了输出更接近递归，逆序压栈。
5) Dijkstra
-
朴素 O(V2)O(V^2)O(V2) 版本，适合矩阵；
-
parentOut记录前驱，路径还原调用reconstructPath； -
注意：需非负权。若存在负权边，改用 Bellman-Ford 或 Johnson。
6) Floyd-Warshall
-
dist初始化为矩阵；next[i][j]初始为j（有边时）或-1； -
三重循环松弛，若
dist[i][k] + dist[k][j] < dist[i][j]则更新，同时next[i][j] = next[i][k]； -
floydPath(fr, from, to)根据next逐步推进重建整条路径。
7) Prim（MST）
-
仅对无向连通图；
-
key[v]维护“v 接入生成树的最小代价”，每轮选取key最小且未选的点接入； -
结束后
parent[v]构成生成树，totalWeight累加边权。
8) 拓扑排序（Kahn）
-
仅用于有向无环图；
-
统计入度，入度 0 入队，循环弹出并“删边降度”；
-
若输出数量
< V，则图中存在环。
9) 打印辅助
-
toMatrixString()：直观打印矩阵，INF用.表示； -
shortName：列宽友好显示。
七、项目详细总结
本文实现了一个可扩容、支持泛型标签的邻接矩阵图：
-
统一封装有/无向、带/不带权；
-
基本增删查、度与邻接；
-
常见算法全齐：BFS、DFS、Dijkstra、Floyd-Warshall、Prim MST、拓扑排序；
-
自带路径还原、矩阵打印 Demo。
在教学与竞赛场景中，邻接矩阵特别适合：
-
需要频繁的 O(1) 连通性查询；
-
Floyd-Warshall、Prim、朴素 Dijkstra 的实现更直观；
-
顶点规模中等（如 V≤1000V \leq 1000V≤1000 以内）时效果良好。
八、常见问题（FAQ）
Q1：为何用 double 存权？能否用 int？
A：为兼容小数权重与统一 INF 判定选了 double。若业务保证整权且更关注精度，使用 long/int 更合适，同时把 INF 替换为一个足够大的整数。
Q2：Dijkstra 报路径为空？
A：可能存在负边权或不可达。Dijkstra 需要非负权；不可达时距离为 INF、路径为空。
Q3：Prim 只能用于无向图吗？
A：是。MST 的经典定义面向无向连通带权图。若图是有向，需要求 最小支配树（最小有向生成树 / Edmonds 算法），不再是 Prim。
Q4：拓扑排序失败提示有环？
A：Kahn 过程中输出数 < V 即存在环；请检查输入是否 DAG。
Q5：Floyd 路径与 Dijkstra 路径为何不同？
A：若权重相同的最短路不唯一，next/parent 的选择差异会导致输出路径不同，但总距离相同。
Q6：矩阵会很占内存吗？
A：空间 O(V2)O(V^2)O(V2)。若 VVV 上千到上万且图稀疏，建议改用邻接表。
九、扩展方向与性能优化
-
稀疏图切换邻接表：提供
ListGraph<T>互操作接口，自动根据密度选择存储。 -
优先队列优化 Dijkstra / Prim：将复杂度降到 O(ElogV)O(E\log V)O(ElogV)。
-
负权最短路：加入 Bellman-Ford 与 Johnson。
-
图连通性/桥/割点/强连通：Tarjan、Kosaraju 等算法模块化接入。
-
持久化与导入导出：支持从 CSV/JSON 读取图，或导出 Graphviz DOT 便于可视化。
-
并行化 Floyd：在多核/并行流或 GPU 上加速 O(V3)O(V^3)O(V3)。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
42
0- 0
已为社区贡献220条内容
所有评论(0)