欢迎来到全面的图表世界！如果您是一名开发人员，并且术语“图表”只会让人想起饼图和条形图的图像，那么请准备好扩展您的视野。从数据结构的角度来看，图是许多复杂的计算机科学问题和现实世界应用背后的无名英雄。从社交网络和推荐引擎到寻找从 a 点到 b 点的最短路径，图表可以做到这一切。本指南将涵盖从基础知识到高级图形算法的所有内容。系好安全带；这将是一次充满知识、幽默和代码片段的疯狂之旅，让您成为 java 图形大师！
1. 到底什么是图？
其核心，图是由边连接的节点（顶点）的集合。与可能是线性的平均数据结构（如数组或链表）不同，图表允许更复杂的关系。
正式定义：
图 ggg 定义为 g=(v,e)g = (v, e)g=(v,e) 其中：
- vvv 是一组顶点（节点）。
- eee 是一组连接顶点对的边。
例子：
考虑一个代表友谊的简单图表：
立即学习“Java免费学习笔记（深入）”；
- 节点：alice、bob、charlie
- 边缘：爱丽丝-鲍勃，鲍勃-查理
符号幽默：
图可以是有向图或无向图。在有向图中，如果爱丽丝指向鲍勃，请想象爱丽丝说：“嘿鲍勃，我关注你，但你不关注我。”
2. 图的类型
2.1. 无向图与有向图
- 无向图：节点之间的关系是双向的。如果 a 和 b 之间有边，您可以从 a 到 b，再从 b 到 a。
- 有向图（digraph）：边有方向。如果从 a 到 b 有一条边，你可以从 a 到 b，但不一定能返回。
2.2. 加权与未加权图表
- 加权图：每条边都有一个关联的权重（将其视为距离或成本）。
- 未加权图：所有边都被同等对待，没有权重。
2.3. 循环图与非循环图
- 循环图：包含至少一个循环（在同一节点开始和结束的路径）。
- 非循环图：不存在循环。最著名的类型？ dag（有向无环图），它是拓扑排序的支柱。
2.4. 连接图与非连接图
- 连通图：所有节点都可以从任何其他节点到达。
- 断开连接的图：某些节点无法从其他节点到达。
2.5. 特殊图表
- 树：连通的无环无向图。把它想象成一个没有循环的家谱——这里没有人与他们的表弟结婚。
- 二部图：可以分为两个集合，使得同一集合内没有两个图顶点相邻。
- 完全图：每对不同的顶点都由一条边连接。
- 稀疏图与密集图：稀疏图相对于节点数量而言边很少；密集图则相反。
3. 内存中的图形表示
3.1. 邻接矩阵
二维数组 adj[i][j]adj[i][j]adj[i][j] 用于以下位置：
-
如果节点 i 和 j 之间有边，则 adj[i][j]=1adj[i][j] = 1adj[i][j]=1。
ii
jj
adj[i][j]=weightadj[i][j] = weightadj[i][j]=权重（如果图表已加权）。
优点：
-
快速查找：o(1) 检查边是否存在。
o(1)o(1)
非常适合密集图形。
缺点：
- 大型稀疏图的内存密集型。
代码示例：
int[][] adjmatrix = new int[n][n]; // n is the number of vertices // add an edge between vertex 1 and 2 adjmatrix[1][2] = 1;
3.2. 邻接列表
一个数组或列表，其中每个索引 iii 保存连接到顶点 iii 的节点列表。非常适合稀疏图。
优点：
- 节省空间。
- 易于迭代邻居。
缺点：
-
查找边是否存在需要 o(n)。
o(n)o(n)
代码示例：
list<list<integer>> adjlist = new arraylist<>();
for (int i = 0; i < n; i++) {
adjlist.add(new arraylist<>());
}
// add an edge between vertex 1 and 2
adjlist.get(1).add(2);
3.3. 边缘列表
所有边的简单列表。每条边都表示为一对（或加权图的三元组）。
优点：
- 对于稀疏图来说非常紧凑。
缺点：
- 缓慢的边缘存在检查。
代码示例：
list<edge> edges = new arraylist<>(); edges.add(new edge(1, 2, 10)); // edge from 1 to 2 with weight 10
4.图的目的和实际应用
- 社交网络：用户是节点，友谊是边。
- 网络爬行：页面是节点，超链接是边。
- 路线算法：google 地图，有人知道吗？以城市为节点，道路为边缘。
- 推荐系统：产品是节点； “购买 x 的顾客也购买了 y”形成边。
- 网络分析：识别集群、寻找影响者等
5.图算法
5.1. 图遍历算法
-
广度优先搜索 (bfs):
- 层序遍历。
- 非常适合在未加权图中查找最短路径。
-
时间复杂度：o(v+e)。
o(v+e)o(v + e)
void bfs(int start) { queue<integer> queue = new linkedlist<>(); boolean[] visited = new boolean[n]; // n = number of vertices queue.add(start); visited[start] = true; while (!queue.isempty()) { int node = queue.poll(); system.out.println(node); for (int neighbor : adjlist.get(node)) { if (!visited[neighbor]) { queue.add(neighbor); visited[neighbor] = true; } } } } -
深度优先搜索 (dfs):
- 在回溯之前尽可能深入。
- 对于寻路和循环检测很有用。
-
时间复杂度：o(v+e)。
o(v+e)o(v + e)
void dfs(int node, boolean[] visited) { if (visited[node]) return; visited[node] = true; System.out.println(node); for (int neighbor : adjList.get(node)) { if (!visited[neighbor]) { dfs(neighbor, visited); } } }
5.2. 最短路径算法
- dijkstra 算法：适用于具有非负权重的图表。
- 贝尔曼-福特算法：可以处理负权重，但比 dijkstra 慢。
- floyd-warshall 算法：查找所有节点对之间的最短路径；对于密集图很有用。
5.3. 最小生成树 (mst)
- kruskal 算法：使用 union-find 进行循环检测的贪心算法。
- prim 算法：通过添加生长树中最便宜的边来构建 mst。
5.4. 拓扑排序
- 用于有向无环图（dag）。非常适合作业调度等依赖关系解决。
5.5. 检测周期
- 基于 dfs 的方法：跟踪当前 dfs 堆栈中的节点。
- 并查法：有效用于无向图。
6. 图问题的技术和技巧
6.1. 多源 bfs
非常适合像“到特定类型节点的最短距离”这样有多个起点的问题。
6.2. 并查（不相交集）
对于处理无向图中的连通分量和循环检测功能强大。
6.3. 图上的记忆化和 dp
动态规划可以与图遍历相结合，优化重复子问题的解决方案。
6.4. 基于启发式的搜索（一种算法）
用于通过知情猜测（启发式）进行寻路。与 dijkstra 类似，但优先考虑靠近目的地的路径。
7. 如何识别图问题
关键指标：
- 类网络结构：实体之间的关系。
- 寻路：“找到从x到y的最短路线。”
- 连接的组件：“计算孤立的组。”
- 依赖链：“依赖于其他任务的任务。”
- 遍历场景：“访问所有房间”或“探索所有选项。”
8. 微笑结束
如果您已经完成了这一步，那么恭喜您！您不仅在图表的疯狂之旅中幸存下来，而且还为自己配备了解决遇到的任何与图表相关的问题的知识。无论您是编码竞赛迷、算法爱好者，还是只是想通过数据结构课程的人，本指南都涵盖了您所需的一切。
请记住，在图表的世界中，如果您迷路了，只需返回本指南即可！
