数据结构中的连通图是什么？

图是一种**非线性**数据结构，具有有限数量的顶点和边，这些边用于连接顶点。需要多次遍历才能完全遍历所有元素。一次遍历不可能遍历整个数据结构。每个元素可以有多个路径到达另一个元素。

• 数据项不是按顺序组织的称为**非线性数据结构**。换句话说，非线性数据结构的元素可以连接到多个元素，以反映它们之间的特殊关系。
• 图本身根据某些属性进行分类；如果我们谈论完全图，它包含顶点集，并且每个顶点都通过边连接到其他顶点。
• 顶点存储数据元素，而边表示顶点之间的关系。
• 图在各个领域都扮演着非常重要的角色；网络系统使用图论及其原理在计算机网络中表示。
• 即使在地图中，我们也认为每个位置是一个顶点，而两个位置之间形成的路径被认为是边。
• 图表示的主要目的是通过最小边权重找到两个顶点之间的最小距离。

连通图的属性

• 我们需要至少**两个顶点**和一条边才能说图是连通的。
• 它用于存储数据元素，当它们不存在于连续内存位置时。
• 这是一种组织和正确存储数据的有效方法。
• 它通过为每个数据元素提供足够的内存来减少内存空间的浪费。
• 与数组不同，我们必须定义数组的大小，然后为该数组分配后续内存空间；如果我们不想存储到数组范围内的元素，那么剩余的内存就会被浪费。
• 因此，为了克服这个因素，我们将使用非线性数据结构，并有多种选择可以从一个节点遍历到另一个节点。
• 数据随机存储在内存中。
• 实现起来相对困难。
• 涉及多个级别。
• 内存利用有效。

关于连通图

• 在图中，一个节点通过边连接到另一个节点。图是一种非线性数据结构，由节点和边组成，用 G ( V, E ) 表示，其中 V 代表顶点的集合，E 代表边的集合。图分为多种类别：有向、无向、加权和无权等。
• 这些数据不像数组那样按顺序连续存储。同类数据元素放置在连续的内存位置，以便检索数据元素更简单。
• 它不像树那样没有根节点或子节点的概念。此外，它不像树那样有特定的数据元素排列顺序，而树有特定的层次顺序来排列数据元素。
• 每棵树都称为图，换句话说，我们称之为生成树，它有 n-1 条边，其中 n 是图中顶点的总数。

图中使用术语

• 顶点：图的顶点表示数据元素。对于一个特定的数据元素，有一个单独的顶点来保存数据元素。
• 边：边是两个顶点节点之间的连接链路；它是从一个顶点节点到另一个节点的遍历路径。
• 无向边：无向边是两个顶点之间的边，没有方向；它对两个顶点都有方向，这意味着它是一条双向边。
• 有向边：有向边是两个顶点之间的边，具有从一个节点到另一个节点的特定方向。
• 加权边：边上有一个特定的值，我们称之为特定边的权重，用于从一个顶点遍历到另一个顶点。加权边对于找到一个节点到另一个节点的最小路径很重要。
• 度：顶点的度定义为连接到该顶点的边的总数。
• 入度：顶点的入度定义为到达该特定顶点的边的总数。
• 出度：顶点的出度定义为从该特定顶点出发的边的总数。

连通图的类型

1. 有向图
2. 无向图
3. 加权图
4. 简单图
5. 多重图
6. 完全图

让我们讨论它的一些类型：

1. 有向图：图包含一组有向边，每条边都有特定的方向。这些方向边指明了从一个顶点到另一个顶点的路径方向。
2. 无向图：图包含一组无向边，其中每条边都连接到顶点，但不指定特定方向。
3. 加权图：加权图是包含带有权重的边的图；这意味着边在从一个顶点到另一个顶点时具有一定的值。
4. 简单图：简单图定义为两个顶点之间只有一条边的图。简单图不包含平行边和自环。
5. 多重图：多重图包含平行边和自环。与简单图相比，它更复杂。
6. 完全图：完全图是每个顶点都连接到所有其他顶点的图。在完全图中，每个顶点的度必须是 n-1，其中 n 是顶点的数量。

图的表示

方法 1：使用邻接矩阵

邻接矩阵始终是 V x V 的方阵，这里 V 代表图的顶点。令 G[i][j]，其中 i 代表行，j 代表列。简单连通图中没有自环和并行边。我们总是定义 G[i][i] = 0，因为它表示没有自连接，并且对于某些顶点，我们没有任何连接。无向图的邻接矩阵始终是对称的。邻接矩阵也用于表示加权图。如果 adj[i][j] = w，则表示从顶点 i 到顶点 j 有一条权重为 w 的边。

• 它是顶点之间连通性的顺序表示。
• 如果我们发现 G [ i, j ] 的顶点有一条边，我们就用 1 表示。
• 否则，我们将 0 放在矩阵 G [ i, j ] 的位置。
• 如果我们有加权图，我们将在相应的位置 G [ i, j ] 写入边权重，而不是 1。
• 但是，如果我们没有任何边，我们将写入 0。
• 在邻接矩阵中，如果我们注意到，我们沿着矩阵对角线有对称性。矩阵中对角线以上的部分与对角线以下的部分相同。
• 通过观察矩阵的上方或下方部分，我们可以轻松地使用邻接矩阵重建图。

方法 2：使用邻接表

这里使用一个链表数组。数组的大小等于顶点的数量。设数组为 array[]。条目 array[i] 代表与第 i 个顶点相邻的顶点的列表。此表示法也可用于表示加权图。边的权重可以表示为对的列表。以上图的邻接表表示如下。

• 邻接表是节点列表的链式表示。
• 节点以单向链表节点的形式表示，节点连通性通过单向链表显示。
• 假设我们有一个图，其中节点 1 连接到节点 2、节点 3 和节点 5，那么以单向链表的形式，头节点表示为节点 1，其他节点在其后面，包含下一个节点的地址。
• 同样，以这种方式，存在每个节点的单向链表，最终显示了节点与其他节点的连通性。
• 邻接表的表示图比邻接矩阵复杂，但邻接矩阵更简单。

图遍历算法

为了遍历图，我们将使用一些图遍历算法。通过使用这些图遍历算法，我们可以轻松地遍历图。在遍历图时，我们的主要目标是访问每个图的顶点而不重复。遍历时出现的顶点顺序取决于我们遵循的遍历过程。

遍历图，我们有两种遍历方法：

1. 广度优先搜索
2. 深度优先搜索

让我们详细讨论以上两种方法：

1. 广度优先遍历

我们必须通过遍历每个顶点来执行广度优先遍历。我们使用队列数据结构来遍历图的顶点。它总是从根顶点或源顶点开始，然后向与该顶点连接的每个顶点移动，遍历直接连接到该根节点的每个子节点。

为了记录每个顶点的遍历，我们使用队列数据结构。在队列中，我们将输入已访问的顶点节点，然后从队列中删除该顶点节点，然后指向下一个节点。在删除下一个节点之前，我们将遍历所有连接的顶点节点，并在并行侧将所有节点录入队列。

使用广度优先搜索遍历的算法

• 考虑一个我们要遍历的随机图。
• 选择任何节点作为源节点，或称为根节点。
• 同时维护一个队列，将该节点输入队列，并写入遍历序列。
• 遍历源顶点连接的所有节点，将该序列写入遍历序列，并在并行中将节点录入队列。
• 在将所有连接的节点写入队列后，从队列中移除源节点，然后移至下一个节点。
• 我们知道队列的工作基于 FIFO 原理。元素的移除是根据先进先出原则进行的。
• 重复以上步骤直到访问完所有图节点。

2. 深度优先遍历

我们必须通过遍历每个顶点来执行深度优先遍历。我们使用堆栈数据结构来遍历图的顶点。它总是从根顶点或任何源顶点开始，然后向任何一个连接的顶点移动。我们将下一个节点视为源顶点，然后我们将到达与新源顶点连接的另一个顶点。通过这种方式，我们遍历整个树和图数据结构。

为了维护每个顶点的遍历记录，我们使用堆栈数据结构；在堆栈中，我们将输入已访问的顶点节点，然后如果到达末尾，我们将进行回溯，访问上一个顶点，然后再次重复相同的过程并深入图，最后也将该节点从堆栈中移除，这个过程一直持续到堆栈变空。

使用深度优先搜索遍历的算法

• 考虑一个我们要遍历的随机图。
• 选择任何节点作为源节点，或称为根节点。
• 同时维护一个堆栈，将该节点输入堆栈，并写入遍历序列。
• 遍历连接到源节点的下一个节点并将其放入堆栈，然后将该节点视为新的源节点。
• 从新的源节点遍历到下一层，同样，维护堆栈并遍历节点，直到我们到达图的深度。
• 一旦我们到达图的深度并且无法再移动到下一个顶点，我们就进行回溯；在回溯时，我们首先从堆栈中移除当前源顶点并指向下一个顶点。
• 尝试以类似的方式深入探索，这样，我们将重复整个过程，直到覆盖图的所有顶点。
• 重复以上步骤，直到堆栈变空。

C 编程语言中的图实现 -

上述程序的输出

C++ 编程语言中的图实现 -

上述程序的输出

Java 编程语言中的图实现 -

上述程序的输出

Python 编程语言中的图实现 -

上述程序的输出

C# 编程语言中的图实现 -

上述程序的输出

Javascript 编程语言中的图实现 -

上述程序的输出