Java 图形终极指南：适合各个级别开发人员的深入探讨-java教程-PHP中文网

首页

Java

java教程

Java 图形终极指南：适合各个级别开发人员的深入探讨

Patricia Arquette

Nov 23, 2024 am 06:29 AM

The Ultimate Guide to Graphs in Java: A Deep Dive for Developers of All Levels

欢迎来到全面的图表世界！如果您是一名开发人员，并且术语“图表”只会让人想起饼图和条形图的图像，那么请准备好扩展您的视野。从数据结构的角度来看，图是许多复杂的计算机科学问题和现实世界应用背后的无名英雄。从社交网络和推荐引擎到寻找从 A 点到 B 点的最短路径，图表可以做到这一切。本指南将涵盖从基础知识到高级图形算法的所有内容。系好安全带；这将是一次充满知识、幽默和代码片段的疯狂之旅，让您成为 Java 图形大师！

1. 到底什么是图？

其核心，图是由边连接的节点（顶点）的集合。与可能是线性的平均数据结构（如数组或链表）不同，图表允许更复杂的关系。

正式定义：

图 GGG 定义为 G=(V,E)G = (V, E)G=(V,E) 其中：

VVV 是一组顶点（节点）。
EEE 是一组连接顶点对的边。

例子：

考虑一个代表友谊的简单图表：

节点：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)

代码示例：

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.3. 边缘列表

所有边的简单列表。每条边都表示为一对（或加权图的三元组）。

优点：

对于稀疏图来说非常紧凑。

缺点：

缓慢的边缘存在检查。

代码示例：

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);

登录后复制

4.图的目的和实际应用

社交网络：用户是节点，友谊是边。
网络爬行：页面是节点，超链接是边。
路线算法：Google 地图，有人知道吗？以城市为节点，道路为边缘。
推荐系统：产品是节点； “购买 X 的顾客也购买了 Y”形成边。
网络分析：识别集群、寻找影响者等

5.图算法

5.1. 图遍历算法

广度优先搜索 (BFS):
- 层序遍历。
- 非常适合在未加权图中查找最短路径。
- 时间复杂度：O(V E)。
  
  O(V E)O(V E)
```
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(1, 2, 10)); // Edge from 1 to 2 with weight 10
```
登录后复制
深度优先搜索 (DFS):
- 回溯之前尽可能深入。
- 对于寻路和循环检测很有用。
- 时间复杂度：O(V E)。
  
  O(V E)O(V E)
```
int[][] adjMatrix = new int[n][n]; // n is the number of vertices
// Add an edge between vertex 1 and 2
adjMatrix[1][2] = 1;
```
登录后复制
登录后复制
登录后复制