在上一章中，你了解了树形结构。然而，你知道这样的数据结构也属于图吗？那么，什么是图，你如何在你的应用程序中使用它呢？你将在本章找到这些问题以及其他许多问题的答案！

首先，将介绍关于图的基本信息，包括节点和边的解释。由于图是实践中常用的数据结构，你还将看到它们的一些应用，例如用于存储社交媒体上的朋友数据或在城市中找到一条道路。然后，将介绍图的表示方法，即使用邻接表和矩阵。

在这简短的介绍之后，你将学习如何用C#语言实现图。此外，你还将了解两种图遍历模式，即深度优先搜索（DFS）和广度优先搜索（BFS）。对于这两种方法，都将展示代码和详细描述。

接下来，你将学习关于最小生成树（MST）的主题，以及创建它们的两种算法，即克鲁斯卡尔算法和普里姆算法。这些算法将以描述、代码片段和插图的形式呈现。此外，还将提供一个实际应用的例子。

另一个有趣的与图相关的主题是节点着色问题，这将在本章的后续部分中考虑。最后，将使用迪杰斯特拉算法分析在图中寻找最短路径的问题。

正如你所看到的，图的主题涉及许多有趣的问题，而本书只提到了其中的一些。然而，所选的主题适合在C#语言的上下文中展示各种与图相关的特点。你准备好深入研究图的主题了吗？如果是的话，开始阅读本章吧！

在本章中，将涵盖以下主题：

? 图的概念

? 应用

? 表示方法

? 实现

? 遍历

? 最小生成树

? 着色

? 最短路径

图的概念

让我们从问题开始：什么是图？广义上讲，图是一种数据结构，它由节点（也称为顶点）和边组成。每条边连接两个节点。图数据结构不要求节点之间连接的任何特定规则，如下图所示:

这个概念看起来非常简单，不是吗？让我们尝试分析前面的图表来消除任何疑问。它包含9个节点，节点的值在1到9之间。这些节点通过11条边连接，例如节点2和节点4之间。此外，一个图表可以包含循环——例如，由节点2、3和4指示的——以及不相连的节点的独立组。但是，关于父节点和子节点的话题呢，这些是你在学习树时所了解的？由于图表中没有关于连接的具体规则，这样的概念在这种情况下并不适用。

想象一下一个图表

如果你想更好地可视化一个图表，暂时把目光从这本书上移开，看看显示你国家最重要道路的地图，比如高速公路或快速路。这样的道路的每一段连接两个城镇，并且有一定的长度。一旦你在纸上画出这样的结构，你会看到，借助它，你可以找到两个城镇之间的路线，以及整个路线的总距离。你知道吗，你刚刚创建了一个图表？各个城镇是节点，连接它们的线是边。两个城镇之间的距离是边的权重。当你能把理论与实践联系起来时，是不是很简单？现在是时候把地图放在一边，专注于学习本书将要介绍的最后一种数据结构，即图表。

对于图表中的边，还需要一些额外的说明。在前面的图表中，你可以看到一个所有节点都用无向边连接的图表——也就是说，双向边。它们表明可以在两个方向之间旅行——例如，从节点2到3，以及从节点3到2。这样的边在图形上以直线表示。当一个图表包含无向边时，它是一个无向图。

然而，如果你需要表明节点之间的旅行只可能在一个方向上进行，情况会怎样呢？在这种情况下，你可以使用有向边——也就是说，单向边——它们在图形上以带箭头的直线表示，指示边的方向。如果一个图表包含有向边，它可以被称为有向图。

自环又是怎么回事？

图表也可以包含自环。每一个都是连接给定节点自身的边。然而，这个话题超出了本书的范围，在本章展示的例子中不会考虑。

下面的图表中，右边展示了一个有向图的例子，而左边展示了一个无向图：

简短解释一下，如前图所示的有向图包含8个节点，通过15条单向边相连。例如，它们表明可以从节点1到节点2双向通行，但从节点1到节点3只能单向通行，因此无法直接从节点3到达节点1。

有向边和无向边之间的区别并不是唯一的。你还可以为特定的边指定权重（也称为成本），以表示节点间旅行的成本。当然，这样的权重可以分配给无向边和有向边。如果提供了权重，边就被称为加权边，整个图就被称为加权图。同样，如果没有提供权重，图中使用的是无权重边。这样的图就被称为无权重图。

以下图中展示了带有无向边（左）和有向边（右）的加权图示例:

这种加权边的图形表示显示了边旁边的权重。例如，在无向图中，从节点1到节点2的旅行成本，以及从节点2到节点1的成本，都等于3，如前一个图表左侧所示。在有向图的情况下（右图），情况稍微复杂一些。在这里，你可以以等于9的成本从节点1旅行到节点2，而相反方向（从节点2到节点1）的旅行成本要便宜得多，只需3。

应用

此时，你已经了解了一些关于图的基本信息，特别是关于节点和各种类型的边。然而，为什么图的话题如此重要，以至于在本书中占据了一整章？你能在你的应用中使用这种数据结构吗？答案是显而易见的：是的！图在解决算法问题时经常使用，并且在现实世界中有许多应用。

首先，让我们思考一下社交媒体上可用的朋友结构。每个用户都有许多联系人，但他们也有许多朋友，以此类推。你应该选择哪种数据结构来存储这些数据？图是最简单的答案。在这种情况下，节点代表联系人，而边表示人与人之间的关系。例如，让我们看看下面的无向和无权图的图表：

正如你所见，Jimmy Gold有五个联系人，分别是John Smith、Andy Wood、Eric Green、Ashley Lopez和Paula Scott。与此同时，Paula Scott还有另外两个朋友：Marcin Jamro和Tommy Butler。通过使用图作为数据结构，你可以轻松检查两个人是否是朋友，或者他们是否有共同的联系人。

图的另一个常见应用涉及寻找最短路径的问题。想象一个程序需要在城市中找到两点之间的路径，同时考虑到驾驶特定道路所需的时间。在这种情况下，你可以使用图来表示城市的地图，其中节点表示交叉路口，边代表道路。当然，你应该给边赋予权重，以表示驾驶特定道路所需的时间。寻找最短路径的主题可以理解为找到从源节点到目标节点的边的列表，总成本最小。基于图的城市地图示意图如下所示:

如你所见，选择了有向加权图。有向边使得支持双向和单向道路成为可能，而加权边允许你指定在两个交叉点之间旅行所需的时间。

表示方法

此时，你已经知道什么是图以及何时可以使用它，但如何在计算机的内存中表示它呢？有两种流行的方法可以解决这个问题，即使用邻接表和邻接矩阵。

邻接表

第一种方法要求你扩展节点的数据，通过指定其邻居的列表。因此，你可以通过遍历给定节点的邻接表来轻松获取给定节点的所有邻居。这样的解决方案在空间上是高效的，因为你只存储相邻边的数据。让我们来看看图表：

这个示例图包含8个节点和10条边。对于每个节点，创建一个相邻节点（即邻居）的列表，如图右侧所示。例如，节点1有两个邻居，即节点2和3，而节点5有四个邻居，即节点4、6、7和8。如你所见，基于邻接表表示无向且无权图是直接的，同时也易于使用、理解和实现。

但在有向图的情况下，邻接表是如何工作的呢？答案很明显，因为分配给每个节点的列表仅显示可以从给定节点到达的相邻节点。这里有一个示例图:

让我们来看看节点3。在这里，邻接表只包含一个元素——即节点4。节点1没有被包括在内，因为它不能直接从节点3到达。

在加权图的情况下，可能需要更多的澄清。在这种情况下，还需要存储特定边的权重。你可以通过扩展邻接表中存储的数据来实现这一点，如下图所示：

例如，节点7的邻接表包含两个元素，即关于一条连接到节点5（权重等于4）和节点8（权重等于6）的边。

邻接矩阵

另一种图表示方法涉及邻接矩阵，它使用二维数组来显示哪些节点通过边连接。矩阵包含与节点数量相同的行和列。主要思想是在矩阵的给定行和列的元素中存储关于特定边的信息。行和列的索引取决于与边相连的节点。例如，如果你想获取关于索引为1和5的节点之间边的信息，你必须检查行索引设置为1的行和列索引设置为5的列中的元素。

这样的解决方案为你提供了一种快速检查两个特定节点是否通过边连接的方法。然而，它可能需要你存储比邻接表多得多的数据，特别是如果图中节点之间没有很多边的话。

首先，让我们分析一个无向且无权图的基本情况。在这种情况下，邻接矩阵可能只存储布尔值。在i行和j列的元素中放置的真值表示索引等于i的节点与索引设置为j的节点之间存在连接。如果这听起来很复杂，请看下面的图：

在这里，邻接矩阵包含64个元素（8行和8列），因为图中有8个节点。数组中许多元素的值被设置为假，这用缺失的指示符表示。其余的用叉号标记，代表真值。例如，位于第四行第三列的元素中的这样一个值意味着节点4和节点3之间存在一条边，如前一个图表所示。

对称邻接矩阵

由于前面的图是无向的，邻接矩阵是对称的。如果节点i和节点j之间存在一条边，那么节点j和节点i之间也存在一条边。

以下示例涉及一个有向且无权的图。在这种情况下，可以使用相同的规则，但邻接矩阵不需要是对称的。让我们来看看与邻接矩阵一起呈现的图的示例图解:

在所示的邻接矩阵中，你可以找到15条边的数据，由15个带有真实值的元素表示，在矩阵中标记为叉号。例如，从节点5到节点4的单向边显示为第五行和第四列的交叉点。

在前面的两个例子中，你学会了如何使用邻接矩阵来表示一个无权图。然而，你如何存储无向或有向加权图的数据呢？答案非常简单——你只需要将邻接矩阵中特定元素存储的数据类型从布尔型更改为数值型。这样，你就可以指定边的权重，如下图所示:

为了消除任何疑问，让我们来看看节点5和节点6之间的边缘，其权重设置为2。

这样的边缘由第五行和第六列的元素表示。该元素的值等于节点之间旅行的成本。

实现

你已经知道关于图的一些基本信息，包括节点、边以及两种表示方法，即使用邻接表和矩阵。然而，你如何在你的应用程序中使用这样的数据结构呢？在本节中，你将学习如何使用C#语言实现图。为了使你对这部分内容的理解更容易，将提供两个示例。

节点

首先，让我们来看看代表图中单个节点的泛型类的代码。这样的类被命名为Node，其代码如下：

该类包含四个属性。由于本章中展示的代码片段中所有这些元素都扮演着重要的角色，让我们详细分析它们：

? 第一个属性（Index）存储了图中节点集合中某个特定节点的索引，以简化访问特定元素的过程。因此，可以通过使用索引轻松获取Node类的实例。

? 接下来的属性名为Data，仅在节点中存储一些数据。值得注意的是，此类数据的类型与创建泛型类实例时指定的类型一致。

? Neighbors属性代表了特定节点的邻接表。因此，它包含了指向代表相邻节点的Node实例的引用。

? 最后一个属性名为Weights，存储分配给相邻边的权重。在加权图的情况下，Weights列表中的元素数量与邻居（Neighbors）的数量相同。如果图是无权的，Weights列表为空。

除了上述属性，该类还包含了重写的ToString方法，它返回对象的文本表示。在这里，字符串以"Index: [index]. Data: [data]. Neighbors: [count]."的格式返回。

边

如在对图主题的简短介绍中提到的，图由节点和边组成。由于节点由Node类的实例表示，因此可以使用泛型Edge类来表示边。相应的代码部分如下：

该类包含三个属性，分别代表与边相邻的节点（From和To），以及边的权重（Weight）。此外，还重写了ToString方法，以展示关于边的一些基本信息。

图形

下一个类名为Graph，它代表了一个完整的图形，可以是有向或无向的边，也可以是有权或无权的边。

实现包括各种属性和方法。这些在下面详细描述。

让我们来看看Graph类的基本版本：

该类包含两个属性，指示边是否是有向的（IsDirected）和是否是有权的（IsWeighted）。此外，还声明了Nodes属性，用于存储图中存在的一系列节点。

Graph类的下一个有趣的成员是索引器，它接受两个索引，即两个节点的索引，以返回表示这些节点之间边的Edge类的实例。实现如下所示：

在索引器中，你会得到两个节点（nodeFrom和nodeTo）的Node类实例，根据索引。由于你想找到从第一个节点（nodeFrom）到第二个节点（nodeTo）的边，你需要尝试使用IndexOf方法在第一个节点的邻居节点集合中找到第二个节点。如果不存在这样的连接，IndexOf方法会返回一个负值，索引器会返回null。否则，你会创建一个新的Edge类实例，并设置其属性的值，包括From和To。如果提供了关于特定边的权重数据，Edge类的Weight属性值也会被设置。

在这个阶段，你知道如何存储图中节点的数据，但如何添加一个新节点呢？

为此，你可以实现一个AddNode方法，如下所示：

在这个方法中，你创建了一个Node类的新实例，并根据参数的值设置了Data属性的值。然后，新创建的实例被添加到Nodes集合中，并调用UpdateIndices方法（稍后描述）来更新集合中存储的所有节点的索引。最后，返回代表新添加节点的Node实例。

你也可以移除现有的节点。这个操作是通过RemoveNode方法执行的，如下所示的代码片段所示：

这种方法接受一个参数，即应该被移除的节点实例。首先，你从节点集合中移除它。然后，你更新剩余节点的索引。最后，你遍历图中的所有节点，移除所有与已移除节点相连的边。

正如你所知，图由节点和边组成。因此，Graph类的实现应该为开发者提供一个添加新边的方法。当然，它应该支持边的各种变体，无论是有向的、无向的、加权的还是未加权的。提出的实现如下：

AddEdge方法接受三个参数，即两个Node类的实例，它们代表由边连接的节点（from和to），以及连接的权重（w），默认设置为0。

在方法内的第一行，你将代表第二个节点的Node实例添加到第一个节点的邻居节点列表中。如果考虑加权图，还需要添加上述边的权重。

只有在图是无向图时，代码的以下部分才会被考虑。在这种情况下，你需要自动添加一个反向的边。为此，你将代表第一个节点的Node实例添加到第二个节点的邻居节点列表中。如果边是加权的，上述边的权重也会被添加到Weights列表中。

从图中移除边的过程由RemoveEdge方法支持。代码如下：

这种方法接受两个参数，即两个节点（起始节点和目标节点），这两个节点之间存在一条应该被移除的边。首先，你尝试在第一个节点的邻居节点列表中找到第二个节点。如果找到了，就将其移除。如果考虑的是带权图，还应该移除权重数据。在无向图的情况下，你会自动移除相反方向的节点，即在目标节点和起始节点之间。

最后一个公共方法命名为GetEdges，它使得能够获取图中所有可用边的集合。提出的实现如下：

首先，初始化一个新的边列表。然后，使用foreach循环遍历图中的所有节点。在循环内部，使用for循环创建Edge类的实例。实例的数量应等于当前节点的邻居数量（foreach循环中的from变量）。在for循环中，新创建的Edge类实例通过设置其属性值进行配置，即第一个节点（from变量——即foreach循环中的当前节点）、第二个节点（到当前正在分析的邻居）和权重。然后，新创建的实例被添加到由edges变量表示的边集合中。最后，返回结果。

在各种方法中，你使用了UpdateIndices方法。其代码如下：

这种方法遍历图中的所有节点，并将Index属性的值更新为从0开始的连续数字。值得注意的是，迭代是使用ForEach方法进行的，而不是使用foreach或for循环。

现在，你知道如何创建图的基本实现。下一步是将其应用于表示一些示例图。