Java中的图

r囧r小猫 2023-10-04 08:53 6阅读 0赞

### **Java中的图** ###

*通过奥利维拉·波波维奇（OliveraPopović） • [0评论][0]*

#### **介绍** ####

图形是存储某些类型的数据的便捷方法。这个概念是从数学中“窃取”的，适合于计算机科学的需求。

有几种方法可以描述什么是图形。我们将首先以高度简化的方式处理图形，然后，如果读者熟悉较早的经验，然后通过树来处理图形，最后将其作为*数学术语*。

#### **简化图** ####

每个图都由*节点*（也称为顶点）和*edge组成*。我们可以将节点视为“数据块”，将边缘视为“这些数据块之间的关系”。

如果我们想指出两个数据块以某种方式彼此关联，我们将它们与边缘连接起来。节点通常表示为圆形，并在其上带有识别标记，以便我们可以区分节点，并且通过连接两个节点的线（或箭头，如下所述）来表示边缘。

在为城市的公交线路绘制地图时，经常使用一种图形数据结构形式。您会看到一张简化的地图，其中显示了公交车站在哪个车站（节点），连接不同车站的路线就是我们所说的边缘：

![a3ca7139953b690131bf793e29c5db8d.png][]

该图显示了我们拥有哪些不同的公交车站以及它们的连接方式。例如，我们可以看到，使用这条巴士线路，要从*巴士站A*到*达巴士站C，*我们必须经过*巴士站B-*我们无法再通过其他方式到达那里。

**加权图**

图形非常通用，这就是它们如此受欢迎的原因之一。假设我们要添加有关从一个公交车站到另一个公交车站平均需要多长时间（以分钟为单位）的信息。我们将“权重”添加到我们的边缘：

![9f6439d4e9afd1db3542e73c949af909.png][]

现在我们的图表显示了比以前更多的信息，我们看到了从一个停靠点到另一个停靠点需要多长时间。我们可以推断出，从*巴士站A*到*巴士站C*需要23分钟，因为我们需要“遍历”连接*巴士站A*和*巴士站B的边*，*权重*为15，而（*巴士站B-* >*公交车站C*）的边缘，其权重为8。

前面的示例介绍了*加权*图的概念，即，如果需要，可以在边上附加值。

**有向图和无向图**

现在我们来看看另一个图形概念-*定向*和*无向*图。假设我们的公交线路在两个方向上都没有相同的站点。

更确切地说，当我们的巴士从*巴士站A*出发时，它经过*B*，*C*并在*D*处结束；然而，在另一个方向不经过*Ç*但一个完全不同的公交车站*ē*，然后才贯通进入*乙*。我们可以做这样的事情：

![d297907486c99c942c6cc74c7eae7879.png][]

正如图片中的破坏者所暗示的那样-这种方法是不正确的。仅查看此图，我们就无法理解公交车在哪个方向停靠，因为即使我们只能从*E*到*B*，也没有什么阻止我们从*B*到*E的*。

这是有向图起作用的地方。有向图中的边由箭头而不是线表示，从*A*到*B*的箭头表示“我们可以从*A*到*B*，反之亦然”。如果我们想说我们可以从*A*到*B*以及从*B*到*A都可以*，我们将使用双向箭头。

现在，周期不再是模棱两可了：

![93df1ca0531cff4a5ae20af371031b82.png][]

现在很明显，我们不能从*B*到*E*或从*D*到*C*，等等。很明显，我们可以使图尽可能简单或复杂。如果由于某种原因，根据我们要行驶的方向，在某些公交车站之间花费不同的时间来行进，我们可以更进一步。

![819ec87bbe58589e97e41bfaa42e7c73.png][]

#### **图的应用** ####

以下是一些可以使用图形方便地存储/表示的数据示例：

*  **一组人及其从属关系：**可以使用无向图来完成，因为我们假设如果人*A*认识人*B*，则情况相同，反之亦然。不同的人将由节点表示，并且如果人*A*认识人*B*，将存在一条连接这两个节点的边。
 *  **一个网站的结构：**在该网站上不同的网页是节点，并有网页之间的有向边*一个*和页面*乙*，如果到页面的链接*乙*在页面存在*一个*。例如，*主页*通常具有指向“关于我们和联系”页面的链接。
 *  **互相依赖的任务：**我们可以代表任务所需要的任务之前要完成*一个*什么任务不能完成前*一个*已经通过以下方式完成-如果是从向边*乙*到*一个*，然后*一个*无法前完成*乙*完成了; 如果存在从*A*到*C的*有向边，则*C*在*A*完成之前无法完成：

![df8fe85063c132e5f4812ce139178d00.png][]

在这里，我们可以看到我们可以戴眼镜，袜子，裤子和T恤衫，而无需考虑其他衣服。但是我们不能在穿裤子和袜子之前先穿鞋。而且，除了戴上眼镜，我们不能在做其他所有事情之前走出去，因为可能不需要戴眼镜。这些类型的图很容易排序，我们可以使用[拓扑排序][Link 1]看到可行的任务执行顺序。

**注意：**常见的误解是需要连接图形，或者至少每个节点都需要以某种方式连接到另一个节点。这是不正确的，我们在前面的示例中已经证明了这一点。一个图可以很容易地由任意数量的节点组成，而它们之间没有一条边。

#### **与树相比的图** ####

如果您熟悉树，则图很容易理解-树是一种特殊的图，即具有一定限制的图。每棵树都是一棵图，但并非每幅图都是一棵树。

根据定义，树是无向图，它们是：

*  是非循环的，即我们不能回溯到我们选择的任何起始节点而无需回溯
 *  通过将任何边添加到现有树中来创建一个循环
 *  任何两个节点之间的路径都是唯一的
 *  有一个独特的根节点
 *  该图已连接（每两个节点之间都有一条路径）

或者用非常简单的术语来说-树是没有循环的连接图。对于图，我们只是摆脱了所有这些限制，并保留了节点和边的概念。

#### **图形作为数学术语** ####

以上所有内容均源自图的数学术语。图是有序对`G = (V, E)`，其中`V`是一组顶点，`E`是一组边。

无向**图：**对于无向图，`E`具有以下定义`E ⊆ { {x, y} | (x, y) ∈ V^2}`。如果我们想避免具有相同起点和终点（即`x ≠ y`）的边，有时会添加一个额外的条件。

**有向图：** `E ⊆ {(x, y) | (x, y) ∈ V^2}`在这里，我们还可以添加以下条件：`x ≠ y`如果要避免在同一节点/顶点处开始和结束的边。

正如我们在边集的先前定义中所看到的`E`，唯一的区别是在有向图的情况下`(x,y)`是有序对，而在无向图中的对`{x,y}`是无序的。这意味着，在无向图，要紧的是`x`和`y`连接，而不是“为了什么”。因此，我们可以这样写`{y,x}`，而不是`{x,y}`同时我们可以*不*写了`(y,x)`，而不是`(x,y)`用于有向图。

当涉及到Java中的图遍历时，所有这些都将我们引向几个重要的主题-*以代码表示图*，*广度优先搜索*，*深度优先搜索*和*Dijkstra算法*。

#### **用代码表示图** ####

知道什么是图，我们需要一种在代码中表示它们的方法。这通常是通过*邻接列表*和*邻接矩阵*来完成的。在下面的文章中，我们深入介绍了Java中的这些实现：

*  [Java中的图形：用代码表示图形][Java]

#### **深度优先搜索（DFS）** ####

*深度优先搜索*（DFS）沿一个分支尽可能远地搜索，然后回溯以在下一个分支中尽可能地搜索。这意味着在前进的Graph中，它从第一个邻居开始，并一直沿线尽可能远地延伸。

*  [Java中的图形：深度优先搜索][Java 1]

#### **广度优先搜索（BFS）** ####

*广度优先搜索*（BFS）是一种图遍历算法，通常用于查找从起始节点到目标节点的最短路径。

BFS“逐层访问”。这意味着它首先访问起始（根）节点的所有子节点。这些孩子被视为“第二层”，然后以相同的方式访问他们的孩子。

*  [Java中的图形：广度优先搜索][Java 2]

#### **Dijkstra的算法** ####

*Dijkstra的算法*是一种非常著名的图遍历算法，用于查找从给定节点/顶点到另一个节点/顶点的最短路径。

此算法有多种实现，有些甚至使用不同的数据结构，并具有不同的应用程序。

Dijkstra的工作方式与以前的算法不同。它不是从根节点开始，而是从目标节点开始，然后回溯到起始节点。

*  [Java中的图形：Dijkstra的算法][Java_Dijkstra]

#### **DFS与BFS** ####

当您阅读有关DFS和BFS的内容时，最有可能想到的一个问题是：

> “实际的区别是什么？”

理论很明确；BFS首先访问最接近我们起始节点的节点，而DFS则尽可能深入图（离我们起始节点很远），然后再继续接近起始节点的其他节点。

让我们来看一些例子：

*  如果您要做的只是检查图中是否完全连接了两个节点，而这并没有给您明确的理由来偏向于使用图遍历算法中的一种或另一种-**其中一个**
 *  如果您“知道”两个节点之间是否完全相连（例如在相识图中查找家庭成员），则请使用**BFS**
 *  如果您想计算从一个节点到另一节点的所有可能方法**-DFS**
 *  如果您想要从一个节点到另一个节点的最短路径（经过最少节点数的路径）**-BFS**
 *  **DFS**还可以用于一些稍微高级的事情，例如检测图形中的循环或检查**强连接的组件**（数学术语，意思是“每个其他节点都可以到达每个节点”），以后可以用于解决2满足性问题（2-SAT）。

#### **结论** ####

图形是存储某些类型的数据的便捷方法。每个图都由*节点*（也称为顶点）和*edge组成*。我们可以将节点视为“数据块”，将边缘视为“这些数据块之间的关系”。

图遍历算法（例如BFS，DFS，Dijkstra的算法和A \*）在数据科学和机器学习的许多分支中非常常用。

[0]: https://stackabuse.com/graphs-in-java/#disqus_thread
[a3ca7139953b690131bf793e29c5db8d.png]: https://img-blog.csdnimg.cn/img_convert/a3ca7139953b690131bf793e29c5db8d.png
[9f6439d4e9afd1db3542e73c949af909.png]: https://img-blog.csdnimg.cn/img_convert/9f6439d4e9afd1db3542e73c949af909.png
[d297907486c99c942c6cc74c7eae7879.png]: https://img-blog.csdnimg.cn/img_convert/d297907486c99c942c6cc74c7eae7879.png
[93df1ca0531cff4a5ae20af371031b82.png]: https://img-blog.csdnimg.cn/img_convert/93df1ca0531cff4a5ae20af371031b82.png
[819ec87bbe58589e97e41bfaa42e7c73.png]: https://img-blog.csdnimg.cn/img_convert/819ec87bbe58589e97e41bfaa42e7c73.png
[df8fe85063c132e5f4812ce139178d00.png]: https://img-blog.csdnimg.cn/img_convert/df8fe85063c132e5f4812ce139178d00.png
[Link 1]: https://stackabuse.com/topological-sorting-in-java
[Java]: https://stackabuse.com/graphs-in-java-representing-graphs-in-code
[Java 1]: https://stackabuse.com/graphs-in-java-depth-first-search-dfs/
[Java 2]: https://stackabuse.com/graphs-in-java-breadth-first-search-bfs/
[Java_Dijkstra]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/