如何在 C# 中表示图
你觉得图表容易理解吗？
CXXGraph
2020 年，软件工程师的求职几乎离不开“算法”这个词。如今数据量如此庞大，企业都希望招聘那些真正擅长解决问题、懂得何时使用何种数据结构的人才。然而，无论我花多少时间试图理解所有这些信息，总有一个主题比其他所有主题都更难。那就是“图”。
我理解图是什么，为什么需要它，以及它的用途，甚至还理解基本的遍历算法——广度优先搜索 (BSF) 和深度优先搜索 (DSF)。然而，最难的部分在于理解如何在代码中表示图。在我从事软件工程师工作不久，除了 HackerRank、LeetCode 等网站上的算法挑战之外，我只在实际应用中用到过几次图。因此，在这篇文章中，我打算尝试解释几种在 C# 中表示图的不同方法，希望最终能重新掌握它。毕竟，学习的最佳途径就是教别人。
术语
想象一下你在学习一门外语。如果对方只是毫无背景地抛给你一些词汇，而且这些词汇听起来都很陌生，你很难取得什么进展。但如果你事先学习了一些词汇，哪怕只是基本的词汇量，那么即使你无法完全理解对方的意思，你也能大致明白对方在说什么，甚至尝试回应。所以，让我们把这个概念应用到这里，学习一些新的词汇吧。
图形
如果不介绍一下图是什么，那就太不明智了。简单来说，图就是由点和线连接而成的图形。点也可以称为顶点（单数形式为Vertex）或节点，而线通常称为“边”。
顶点
这听起来可能像是一个糟糕的词典，因为我们已经在“图”部分介绍过它了，但是顶点只是图上可以通过图边连接的点。
边缘
这一点让我困惑了很久，因为在我看来，“边”代表事物的终点，或者像网上说的，是“物体的外部边界”。但在数学图论中并非如此，边只是连接两个节点（顶点）的线段。
无向图
在无向图中，边没有方向，你可以沿着同一条边从节点 A 到达节点 B，也可以沿着同一条边从节点 B 到达节点 A。
有向图
在有向图中，每条边都有一个方向，只有当存在一条指向该方向的边时，才能从节点 A 到达节点 B。
相邻顶点
仅由一条边连接的顶点（节点）。注意：顶点不能与其自身相邻。
边缘权重
这也被称为边的“成本”。它用于定义从节点 A 到节点 B 的路径中，哪条路径更优。权重越小，路径越好。
定义抽象图基类
希望有了这些新的词汇，我们就能更容易地理解代码中的图表示，而不会完全迷失方向。由于我们要实现两种不同的表示方法，我将首先定义一个名为 GraphBase 的抽象类。
public abstract class GraphBase
{
protected readonly int NumVertices;
protected readonly bool Directed;
public GraphBase(int numVertices, bool directed = false)
{
this.NumVertices = numVertices;
this.Directed = directed;
}
public abstract void AddEdge(int v1, int v2, int weight);
public abstract IEnumerable<int> GetAdjacentVertices(int v);
public abstract int GetEdgeWeight(int v1, int v2);
public abstract void Display();
public int NumVertices { get { return this.numVertices; } }
}
图的邻接矩阵表示
这里的代码非常简单，一目了然。现在我们来尝试使用它，并利用邻接矩阵实现一个图。为了便于理解，我会将代码分段展示。首先来看矩阵字段和构造函数，构造函数会调用 `GenerateEmptyMatrix` 方法来填充矩阵，使其包含空值（或零）。这个矩阵将作为我们的图表示。
int[,] Matrix;
public AdjacencyMatrixGraph(int numVertices, bool directed = false) : base(numVertices, directed)
{
GenerateEmptyMatrix(numVertices);
}
private void GenerateEmptyMatrix(int numVertices)
{
this.Matrix = new int[numVertices, numVertices];
for (int row = 0; row < numVertices; row++)
{
for (int col = 0; col < numVertices; col++)
{
Matrix[row, col] = 0;
}
}
}
如果图有 9 个顶点，调用构造函数后得到的矩阵将如下所示：
这其中包含了 81 个不同的单元格！没错，它的工作原理是，如果我们想知道一个顶点是否与另一个顶点相连，只需在这个矩阵中快速查找即可。例如，如果我们想知道顶点 0 是否与顶点 8 相连，只需查看矩阵右上角的元素，就能很快发现这两个节点没有连接。现在我们添加一个添加边的方法，看看“连接”这两个顶点后会发生什么变化。
public override void AddEdge(int v1, int v2, int weight = 1)
{
if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
throw new ArgumentOutOfRangeException("Vertices are out of bounds");
if (weight < 1) throw new ArgumentException("Weight cannot be less than 1");
this.Matrix[v1, v2] = weight;
//In an undirected graph all edges are bi-directional
if (!this.directed) this.Matrix[v2, v1] = weight;
}
这里并没有太复杂的操作。我们验证顶点是否在矩阵的边界内，确认权重不小于 1，并在给定的节点之间创建一条边。如果不是有向图，这条边应该是双向的，并且矩阵看起来是对称的。
现在，让我们尝试添加从顶点 0 到顶点 8 的边，看看它会如何改变我们的矩阵。
class Program
{
static void Main(string[] args)
{
var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
adjMatrixGraph.AddEdge(0, 8);
}
}
添加这条边之后，矩阵看起来是这样的：
如您所见，由于这是一个无向图，因此创建了从 0 到 8 的边，以及从 8 到 0 的边。
目前为止还不错，但还没完成。为了进行图遍历，我们需要一种方法来找到相邻顶点。接下来我们就来实现这一点。
public override IEnumerable<int> GetAdjacentVertices(int v)
{
if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");
List<int> adjacentVertices = new List<int>();
for (int i = 0; i < this.numVertices; i++)
{
if (this.Matrix[v, i] > 0)
adjacentVertices.Add(i);
}
return adjacentVertices;
}
我们可以看到，获取相邻顶点非常简单，只需遍历给定顶点所在的行，并获取权重值大于零的与该顶点匹配的边即可。
我们添加三条边：从 0 到 8，从 0 到 3，以及从 8 到 4，然后获取第 0 个顶点的相邻顶点。
var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
adjMatrixGraph.AddEdge(0, 8);
adjMatrixGraph.AddEdge(0, 3);
adjMatrixGraph.AddEdge(8, 4);
var adjacent = adjMatrixGraph.GetAdjacentVertices(0);
这就是我们的矩阵及其相邻顶点的样子：
如您所见，我们正确地获取了顶点 3 和 8 作为顶点 0 的相邻顶点，并正确地忽略了顶点 4，因为它与顶点 8 相邻但不与顶点 0 相邻。如果我们现在对顶点 8 调用 GetAdjacentVertices 函数，我们应该得到顶点 0 和 4 作为顶点 8 的相邻顶点。
var adjacent = adjMatrixGraph.GetAdjacentVertices(8);
最后一步是实现 GetEdgeWeight 方法。使用矩阵表示法，只需获取顶点 1 和顶点 2 的“交集”的值即可。
public override int GetEdgeWeight(int v1, int v2)
{
return this.Matrix[v1, v2];
}
这其实还不错。最难的部分可能就是记住 C# 中二维数组的工作原理了。
现在我们快速看一下使用邻接集实现图的另一种方法。
图的邻接集表示
为了帮助我们用集合表示图，让我们定义一个名为 Node 的类，它将保存边，并允许我们轻松访问相邻的顶点。
public class Node
{
private readonly int VertexId;
private readonly HashSet<int> AdjacencySet;
public Node(int vertexId)
{
this.VertexId = vertexId;
this.AdjacencySet = new HashSet<int>();
}
public void AddEdge(int v)
{
if (this.VertexId == v)
throw new ArgumentException("The vertex cannot be adjacent to itself");
this.AdjacencySet.Add(v);
}
public HashSet<int> GetAdjacentVertices()
{
return this.AdjacencySet;
}
}
每个节点都有一个 VertexId 字段，方便我们引用它，还有一个 Adjacency HashSet 来存储边。添加边就像向集合中添加一个顶点一样简单，而获取相邻顶点也只需返回 AdjacencySet 即可。
现在让我们来看看使用 AdjacencySetGraph 实现的 GraphBase。和上次一样，我们先从构造函数开始：
private HashSet<Node> vertexSet;
public AdjacencySetGraph(int numVertices, bool directed = false) : base(numVertices, directed)
{
this.vertexSet = new HashSet<Node>();
for (var i = 0; i < numVertices; i++)
{
vertexSet.Add(new Node(i));
}
}
在这里，我们创建另一个集合来保存代表顶点信息的节点，并用创建图对象时指定的顶点数量填充该集合。到目前为止都很简单。
我们来看一下 AddEdge 方法：
public override void AddEdge(int v1, int v2, int weight = 1)
{
if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
throw new ArgumentOutOfRangeException("Vertices are out of bounds");
if (weight != 1) throw new ArgumentException("An adjacency set cannot represent non-one edge weights");
this.vertexSet.ElementAt(v1).AddEdge(v2);
//In an undirected graph all edges are bi-directional
if (!this.directed) this.vertexSet.ElementAt(v2).AddEdge(v1);
}
你注意到这种图表示方式的局限性了吗？我们不能有值不为 1 的权重。嗯，或许当初引入 GraphBase 抽象类还为时过早。不过，
添加边非常简单，只需访问具有给定 VertexId 的节点，然后调用其 AddEdge 方法即可。我们记得，该方法会将该顶点添加到相邻顶点的集合中。因此，获取相邻顶点也很简单：
public override IEnumerable<int> GetAdjacentVertices(int v)
{
if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");
return this.vertexSet.ElementAt(v).GetAdjacentVertices();
}
最后，我们需要实现 GetEdgeWeight 方法，但由于权重值不能不为 1，所以我们直接返回 1：
public override int GetEdgeWeight(int v1, int v2)
{
return 1;
}
我会把分析每种方法的优缺点以及每种实现中可能存在的未处理问题的任务留给你自己。希望这能帮助你成为图论大师。我相信我也正在朝着最终“领悟”图论的方向前进。如果你愿意，可以尝试使用这两种图表示方法中的任何一种来实现深度优先搜索或广度优先搜索算法。如果你在阅读本文时发现了一些错误或任何让你无法接受的地方，请在评论区留言，我们可以一起讨论。
你觉得图表容易理解吗？
PS：这篇文章并没有涵盖图论的很多内容，例如循环图和非循环图。本文主要介绍如何用代码表示基本图，如果您想了解更多相关信息，网上有很多资源可以帮助您深入学习。
文章来源：https://dev.to/ Russianguycoding/how-to-represent-a-graph-in-c-4cmo