⚡ 图数据结构Java:核心概念与工程价值
图(Graph)是一种非线性数据结构,由**顶点**(Vertex)和**边**(Edge)构成,用于建模实体间的复杂关系。在Java中,图结构广泛应用于社交网络分析、推荐系统、路径规划、编译器设计、电路模拟、知识图谱构建等领域。相较于树结构仅支持层级关系,图支持任意拓扑连接,使其成为表达多对多关系的首选模型。
Java标准库并未内置图类,开发者需自主实现。主流实现方式包括:邻接矩阵(Adjacency Matrix)与邻接表(Adjacency List)。二者在时间与空间复杂度上各有优劣,选择取决于图的稠密程度与操作频率。
一个图可形式化定义为 G = (V, E),其中 V 为顶点集合,E 为边集合。若边无方向,则为无向图;若边有方向,则为有向图。边可带权重(Weight),形成加权图,用于最短路径计算。
图的遍历是图算法的基础。深度优先搜索(DFS)与广度优先搜索(BFS)是两种基本遍历策略:DFS使用栈(递归隐式调用栈)深入探索分支,适合连通性检测、环检测;BFS使用队列逐层扩展,适合最短路径(无权图)、层次遍历。
在Java中,图的实现需兼顾封装性、可扩展性与性能。常见设计模式包括:使用`Map
实际工程中,图算法常与集合框架(`HashSet`、`PriorityQueue`)及泛型结合使用,以提升复用性。例如,Dijkstra算法依赖最小堆(`PriorityQueue`)优化松弛操作;拓扑排序需结合`Queue`实现Kahn算法,或使用递归栈实现DFS版本。
值得注意的是,图的存储结构直接影响算法效率。邻接矩阵访问任意边为O(1),但空间复杂度为O(V²),稀疏图中浪费严重;邻接表空间为O(V+E),但查询边是否存在需O(degree(v))。因此,稀疏图(E << V²)推荐邻接表,稠密图(E ≈ V²)可考虑邻接矩阵。
⚙️ 图的存储结构:邻接矩阵 vs 邻接表
在Java中,图的实现核心在于选择合适的存储结构。以下对比两种主流方式,并提供完整代码示例。
邻接矩阵实现
适用于顶点数固定、图较稠密的场景。矩阵中`matrix[i][j]`表示顶点i到j的边权重(无边时为∞或特殊标记)。
public class AdjacencyMatrixGraph<V> {
private V[] vertices;
private double[][] adjMatrix;
private int vertexCount;
public AdjacencyMatrixGraph(int capacity) {
vertices = (V[]) new Object[capacity];
adjMatrix = new double[capacity][capacity];
vertexCount = 0;
}
public void addVertex(V vertex) {
vertices[vertexCount++] = vertex;
}
public void addEdge(int src, int dest, double weight) {
adjMatrix[src][dest] = weight;
// 无向图需:adjMatrix[dest][src] = weight;
}
public double getWeight(int src, int dest) {
return adjMatrix[src][dest];
}
}
优势:边查询O(1),适合频繁查询边存在性;空间固定,实现简单。
劣势:稀疏图空间浪费大;增删顶点需重构数组;不支持动态扩展。
邻接表实现
适用于稀疏图,空间效率高,支持动态添加顶点。
import java.util.*;
public class AdjacencyListGraph<V> {
private static class Edge {
V dest;
double weight;
Edge(V dest, double weight) {
this.dest = dest;
this.weight = weight;
}
}
private Map<V, List<Edge>> adjList;
private int edgeCount;
public AdjacencyListGraph() {
adjList = new HashMap<>();
edgeCount = 0;
}
public void addVertex(V vertex) {
adjList.putIfAbsent(vertex, new ArrayList<>());
}
public void addEdge(V src, V dest, double weight) {
addVertex(src);
addVertex(dest);
adjList.get(src).add(new Edge(dest, weight));
// 无向图:adjList.get(dest).add(new Edge(src, weight));
edgeCount++;
}
public List<Edge> getNeighbors(V vertex) {
return adjList.getOrDefault(vertex, Collections.emptyList());
}
public int getVertexCount() { return adjList.size(); }
public int getEdgeCount() { return edgeCount; }
}
优势:空间O(V+E);增删顶点灵活;迭代邻居高效。
劣势:边存在性查询O(degree(v));无法直接获取边数(需计数)。
混合方案:使用枚举顶点索引
对顶点使用`Enum`或预分配ID,可结合二者优势:顶点用数组索引,邻接表用`List<List<Integer>>`存储。例如:
public enum Station { BEIJING, SHANGHAI, GUANGZHOU, SHENZHEN }
List<List<Pair<Integer,Double>>> graph = new ArrayList<>();
for (int i=0; i<4; i++) graph.add(new ArrayList<>());
// 添加边:graph.get(0).add(new Pair(1, 1200.0)); // 北京→上海,1200公里
此方案兼顾性能与可读性,是工程中推荐实践。
🔄 图遍历算法:DFS与BFS深度实现
图遍历是图算法的基石,决定后续分析路径。以下提供标准Java实现,含环检测与路径回溯。
深度优先搜索(DFS)
DFS通过递归或显式栈深入探索,常用于:
- 连通分量计数
- 拓扑排序(结合后序)
- 强连通分量(Tarjan算法)
- 路径存在性判断
以下为递归DFS模板,支持路径记录:
public class DFS<V> {
private Map<V, Boolean> visited;
private Map<V, V> parent; // 记录路径
public List<V> dfs(AdjacencyListGraph<V> graph, V start) {
visited = new HashMap<>();
parent = new HashMap<>();
List<V> result = new ArrayList<>();
for (V v : graph.adjList.keySet()) visited.put(v, false);
dfsUtil(graph, start, result);
return result;
}
private void dfsUtil(AdjacencyListGraph<V> graph, V vertex, List<V> result) {
visited.put(vertex, true);
result.add(vertex);
for (var edge : graph.getNeighbors(vertex)) {
if (!visited.get(edge.dest)) {
parent.put(edge.dest, vertex);
dfsUtil(graph, edge.dest, result);
}
}
}
public List<V> getPath(V start, V end) {
if (!visited.containsKey(end) || !visited.get(end)) return null;
List<V> path = new ArrayList<>();
for (V v = end; v != null; v = parent.get(v))
path.add(v);
Collections.reverse(path);
return path;
}
}
广度优先搜索(BFS)
BFS逐层扩展,适用于:
- 无权图最短路径(边数最少)
- 二分图检测
- 社交网络中“几度人脉”
以下为BFS模板,返回最短路径(无权图):
public class BFS<V> {
private Map<V, Boolean> visited;
private Map<V, V> parent;
public List<V> bfs(AdjacencyListGraph<V> graph, V start, V end) {
visited = new HashMap<>();
parent = new HashMap<>();
Queue<V> queue = new LinkedList<>();
for (V v : graph.adjList.keySet()) visited.put(v, false);
visited.put(start, true);
queue.offer(start);
while (!queue.isEmpty()) {
V v = queue.poll();
if (v.equals(end)) break;
for (var edge : graph.getNeighbors(v)) {
if (!visited.get(edge.dest)) {
visited.put(edge.dest, true);
parent.put(edge.dest, v);
queue.offer(edge.dest);
}
}
}
return reconstructPath(start, end);
}
private List<V> reconstructPath(V start, V end) {
if (!visited.get(end)) return Collections.emptyList();
List<V> path = new ArrayList<>();
for (V v = end; v != null; v = parent.get(v))
path.add(v);
Collections.reverse(path);
return path;
}
}
环检测:有向图 vs 无向图
无向图:DFS中若访问到已访问的非父节点,则存在环。
private boolean hasCycle(AdjacencyListGraph<V> graph, V v, V parent) {
visited.put(v, true);
for (var edge : graph.getNeighbors(v)) {
if (!visited.get(edge.dest)) {
if (hasCycle(graph, edge.dest, v)) return true;
} else if (!edge.dest.equals(parent)) {
return true; // 发现回边
}
}
return false;
}
有向图:需三色标记(0=未访问,1=当前路径中,2=已完成),若访问到状态1的节点,则存在环。
private boolean hasCycleDirected(AdjacencyListGraph<V> graph, V v, Map<V, Integer> color) {
color.put(v, 1);
for (var edge : graph.getNeighbors(v)) {
int c = color.getOrDefault(edge.dest, 0);
if (c == 1) return true; // 回边
if (c == 0 && hasCycleDirected(graph, edge.dest, color)) return true;
}
color.put(v, 2);
return false;
}
🛣️ 最短路径算法:Dijkstra与Floyd-Warshall
最短路径是图论核心问题,广泛应用于导航、网络路由、物流规划。
Dijkstra算法:单源最短路径(非负权)
使用优先队列优化,时间复杂度O((V+E)logV)。
public class Dijkstra<V> {
public Map<V, Double> shortestPaths(AdjacencyListGraph<V> graph, V start) {
Map<V, Double> dist = new HashMap<>();
Map<V, V> prev = new HashMap<>();
PriorityQueue<Pair<V,Double>> pq = new PriorityQueue<>(Comparator.comparingDouble(Pair::getValue));
for (V v : graph.adjList.keySet()) {
dist.put(v, Double.POSITIVE_INFINITY);
prev.put(v, null);
}
dist.put(start, 0.0);
pq.offer(new Pair<>(start, 0.0));
while (!pq.isEmpty()) {
var cur = pq.poll();
V u = cur.getKey();
if (cur.getValue() > dist.get(u)) continue;
for (var edge : graph.getNeighbors(u)) {
double alt = dist.get(u) + edge.weight;
if (alt < dist.get(edge.dest)) {
dist.put(edge.dest, alt);
prev.put(edge.dest, u);
pq.offer(new Pair<>(edge.dest, alt));
}
}
}
return dist;
}
}
适用场景:道路导航(非负距离)、网络延迟优化。
局限:不支持负权边;若存在负权环,结果无效。
Floyd-Warshall算法:所有对最短路径
动态规划实现,时间复杂度O(V³),适合小规模图或需全对路径的场景。
public class FloydWarshall<V> {
private Map<V, Integer> indexMap;
private double[][] dist;
private int[][] next;
public FloydWarshall(List<V> vertices) {
indexMap = new HashMap<>();
for (int i = 0; i < vertices.size(); i++) indexMap.put(vertices.get(i), i);
int n = vertices.size();
dist = new double[n][n];
next = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Double.POSITIVE_INFINITY);
next[i][i] = i;
}
}
public void addEdge(V src, V dest, double weight) {
int i = indexMap.get(src), j = indexMap.get(dest);
dist[i][j] = weight;
next[i][j] = j;
}
public void compute() {
int n = indexMap.size();
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] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
public List<V> getPath(V src, V dest) {
int i = indexMap.get(src), j = indexMap.get(dest);
if (dist[i][j] == Double.POSITIVE_INFINITY) return Collections.emptyList();
List<V> path = new ArrayList<>();
path.add(src);
while (i != j) {
i = next[i][j];
path.add((V) indexMap.keySet().stream().filter(k -> indexMap.get(k) == i).findFirst().orElse(null));
}
return path;
}
}
优势:支持负权边(无负环);可直接获取任意两点路径。
🕸️ 最小生成树:Kruskal与Prim算法
最小生成树(MST)适用于连通无向图,目标是选择n-1条边使总权重最小,且无环。常用于网络布线、聚类分析。
Kruskal算法:基于并查集
贪心策略:按边权排序,依次加入不形成环的边。
public class KruskalMST<V> {
public List<Edge> mst(AdjacencyListGraph<V> graph) {
List<Edge> edges = new ArrayList<>();
for (var entry : graph.adjList.entrySet()) {
V src = entry.getKey();
for (var e : entry.getValue()) {
edges.add(new Edge(src, e.dest, e.weight));
}
}
edges.sort(Comparator.comparingDouble(e -> e.weight));
UnionFind<V> uf = new UnionFind<>();
List<Edge> mst = new ArrayList<>();
for (Edge e : edges) {
if (!uf.connected(e.src, e.dest)) {
uf.union(e.src, e.dest);
mst.add(e);
}
}
return mst;
}
static class Edge { V src, dest; double weight; ... }
}
class UnionFind<V> {
private Map<V, V> parent = new HashMap<>();
private Map<V, Integer> rank = new HashMap<>();
public void add(V x) {
parent.putIfAbsent(x, x);
rank.putIfAbsent(x, 0);
}
public V find(V x) {
if (!parent.get(x).equals(x))
parent.put(x, find(parent.get(x)));
return parent.get(x);
}
public boolean connected(V x, V y) {
return find(x).equals(find(y));
}
public void union(V x, V y) {
V rx = find(x), ry = find(y);
if (rx.equals(ry)) return;
if (rank.get(rx) < rank.get(ry)) parent.put(rx, ry);
else {
parent.put(ry, rx);
if (rank.get(rx).equals(rank.get(ry)))
rank.put(rx, rank.get(rx) + 1);
}
}
}
时间复杂度:O(E log E),主导在排序。
Prim算法:基于优先队列
从单点出发,每次加入最近顶点,适合稠密图。
public class PrimMST<V> {
public List<Edge> mst(AdjacencyListGraph<V> graph, V start) {
Set<V> inMST = new HashSet<>();
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingDouble(e -> e.weight));
List<Edge> mst = new ArrayList<>();
inMST.add(start);
for (var e : graph.getNeighbors(start)) pq.offer(e);
while (!pq.isEmpty() && inMST.size() < graph.adjList.size()) {
Edge e = pq.poll();
if (inMST.contains(e.dest)) continue;
inMST.add(e.dest);
mst.add(e);
for (var next : graph.getNeighbors(e.dest))
if (!inMST.contains(next.dest)) pq.offer(next);
}
return mst;
}
}
时间复杂度:O(E log V)(使用二叉堆)。
📜 拓扑排序:依赖解析与任务调度
拓扑排序仅适用于有向无环图(DAG),将顶点线性排列使所有边方向一致(u→v表示u在v前)。应用于课程依赖、构建系统、任务调度。
Kahn算法(基于入度)
public class TopologicalSort<V> {
public List<V> sort(AdjacencyListGraph<V> graph) {
Map<V, Integer> inDegree = new HashMap<>();
for (V v : graph.adjList.keySet()) inDegree.put(v, 0);
for (var entry : graph.adjList.entrySet())
for (var e : entry.getValue())
inDegree.put(e.dest, inDegree.get(e.dest) + 1);
Queue<V> queue = new LinkedList<>();
for (V v : inDegree.keySet()) if (inDegree.get(v) == 0) queue.offer(v);
List<V> result = new ArrayList<>();
while (!queue.isEmpty()) {
V v = queue.poll();
result.add(v);
for (var e : graph.getNeighbors(v)) {
inDegree.put(e.dest, inDegree.get(e.dest) - 1);
if (inDegree.get(e.dest) == 0) queue.offer(e.dest);
}
}
return result.size() == graph.adjList.size() ? result : Collections.emptyList();
}
}
关键点:若结果长度 < V,则存在环,无法拓扑排序。
DFS后序反转法
public List<V> dfsSort(AdjacencyListGraph<V> graph) {
List<V> result = new ArrayList<>();
Set<V> visited = new HashSet<>();
Set<V> recStack = new HashSet<>(); // 检测环
for (V v : graph.adjList.keySet()) {
if (!visited.contains(v))
if (!dfsVisit(graph, v, visited, recStack, result))
return Collections.emptyList(); // 存在环
}
Collections.reverse(result);
return result;
}
private boolean dfsVisit(AdjacencyListGraph<V> graph, V v, Set<V> visited, Set<V> recStack, List<V> result) {
visited.add(v);
recStack.add(v);
for (var e : graph.getNeighbors(v)) {
if (!visited.contains(e.dest)) {
if (!dfsVisit(graph, e.dest, visited, recStack, result)) return false;
} else if (recStack.contains(e.dest)) return false; // 回边 → 环
}
recStack.remove(v);
result.add(v);
return true;
}
两种方法时间复杂度均为O(V+E),Kahn更直观,DFS版代码更简洁。
🎓 高频面试题:图算法实战解析
以下为Java图算法常见面试题,覆盖核心算法理解与编码能力。
1. 课程表问题(LeetCode 207)
判断是否可完成所有课程(即DAG拓扑排序存在)。
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
int[] inDegree = new int[numCourses];
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
int completed = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
completed++;
for (int next : graph.get(cur))
if (--inDegree[next] == 0) queue.offer(next);
}
return completed == numCourses;
}
考点:拓扑排序建模、入度计算、环检测。
2. 课程表 II(LeetCode 210)
返回任意一种修课顺序,无解返回空数组。
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 构建图与入度(同上)
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
order[idx++] = cur;
// ...(同上)
}
return idx == numCourses ? order : new int[0];
}
3. 朋友圈(LeetCode 547)
无向图中连通分量计数(DFS/BFS)。
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(isConnected, i, visited);
count++;
}
}
return count;
}
private void dfs(int[][] grid, int i, boolean[] visited) {
for (int j = 0; j < grid.length; j++) {
if (grid[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(grid, j, visited);
}
}
}
4. 单词接龙(LeetCode 127)
转为图:单词为顶点,相差1字母为边,BFS求最短路径。
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) return 0;
Map<String, List<String>> graph = new HashMap<>();
wordList.add(0, beginWord);
// 预处理:通配符映射
Map<String, List<String>> patternMap = new HashMap<>();
for (String word : wordList) {
for (int i = 0; i < word.length(); i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i+1);
patternMap.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
}
}
// 构建图
for (var list : patternMap.values())
for (String w1 : list)
for (String w2 : list)
if (!w1.equals(w2)) {
graph.computeIfAbsent(w1, k -> new ArrayList<>()).add(w2);
}
// BFS
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (cur.equals(endWord)) return steps;
for (String next : graph.getOrDefault(cur, Collections.emptyList()))
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
steps++;
}
return 0;
}
优化:双向BFS、预处理通配符避免O(n²)建图。