首页 > 文章 > java教程

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

来源：dev.to

时间：2024-11-30 18:09:59 366浏览收藏

一分耕耘，一分收获！既然都打开这篇《Java 图形终极指南：适合各个级别开发人员的深入研究》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新文章相关的内容，希望对大家都有所帮助！

欢迎来到全面的图表世界！如果您是一名开发人员，并且术语“图表”只会让人想起饼图和条形图的图像，那么请准备好扩展您的视野。从数据结构的角度来看，图是许多复杂的计算机科学问题和现实世界应用背后的无名英雄。从社交网络和推荐引擎到寻找从 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)

代码示例：

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