如何在C#中表示图

作者 : IT 大叔 本文共5648个字,预计阅读时间需要15分钟 发布时间: 2020-09-24

2020年软件工程师的求职是“算法”一词的同义词。鉴于这些天可用于处理的数据量,这些公司希望聘请真正擅长解决问题并知道何时使用哪种数据结构的人员。但是,无论我花多少时间来尝试理解所有这些信息,都有一个主题似乎比其他主题难一些。那个话题是“图形”。

我了解图形是什么,为什么使用它以及在哪里使用,甚至还了解基本遍历算法-BSF(广度优先搜索)和DSF(深度优先搜索)。但是,最困难的部分是理解图形在代码中的表示方式。在我刚开始从事软件工程师的职业生涯中,除了在HackerRank,LeetCode和类似资源上遇到算法挑战之外,我只需要使用几次。因此,在这篇文章中,我将尝试解释几种用C#表示图形的不同方式,以期我最终会记住该怎么做。因为学习某物的最好方法是教别人。

术语

想象您正在学习另一种语言。如果只是在没有任何上下文的情况下向您投掷单词,而且听起来都不熟悉,那么您就不可能走得很远。但是,如果您学会了一些单词并开发了词汇,甚至是基础词汇,那么即使您对所有内容都不是很了解,您仍然可以理解对您说的话,甚至尝试答复。因此,让我们在这里应用相同的概念并学习一些新词汇。

图形

不涵盖图形是很愚蠢的。用最简单的术语来说,就是点由线连接。点也可以称为“顶点”(“顶点”为单数)或“节点”,线通常称为“边”。

顶点

这听起来像是一本不好的字典,因为我们已经在“图形”部分中进行了介绍,但是顶点只是图形上可以通过图形边缘连接的一个点。

边缘

很长一段时间以来,这一直使我有些困惑,因为我脑海中的“边缘”代表事物的终结,或者就像互联网所说的那样,它是“物体的外部界限”。但是在数学图中却不是这种情况,并且一条边只是一条连接两个节点(顶点)的线。

无向图

在无向图中,边没有方向,您可以通过与从节点B到节点A相同的边从节点A到达节点B。

有向图

在有向图中,每个边都有一个方向,并且只有在有一个边指向该方向时,您才能从节点A到达节点B。

相邻顶点

恰好与一条边相连的顶点(节点)。注意:顶点不能与其自身相邻

边缘重量

这也称为边缘的“成本”。这用于定义从节点A到节点B的一条路径是否比另一条路径更好。权重越小-路径越好。

定义抽象GraphBase类

希望有了这个新词汇,我们可以更轻松地查看代码中的图形表示而不会完全迷失方向。由于我们要实现两种不同的表示形式,因此我将首先定义一个抽象类,我将其称为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; } }
    }

图的邻接矩阵表示

这里的代码非常简单,不言自明。现在,让我们尝试使用它,并使用邻接矩阵实现图形。为了更容易理解,我将代码分块发布。让我们从Matrix字段和构造函数开始,后者将依次调用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个顶点的图,则在调用构造函数后,矩阵将如下所示:

如何在C#中表示图插图

虽然它包含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);
    }
}

添加此边后,矩阵如下所示:

如何在C#中表示图插图(2)

如您所见,创建了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);

这是矩阵和相邻顶点的样子:

如何在C#中表示图插图(4)

如您所见,我们正确地获得了3和8作为与顶点0相邻的顶点,并正确地忽略了顶点4,因为它与8相邻但不与0相邻。如果现在在顶点8上调用GetAdjacentVertices,则应该将顶点0和4分别作为毗邻8。

var adjacent = adjMatrixGraph.GetAdjacentVertices(8);

如何在C#中表示图插图(6)

我们现在要做的最后一件事是实现GetEdgeWeight方法。使用矩阵表示法,就像获取vertex1和vertex2的“交集”值一样容易。

public override int GetEdgeWeight(int v1, int v2)
{
    return this.Matrix[v1, v2];
}

这绝对还不错。可能最具挑战性的部分是记住2D数组如何在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;
}

我将留给您了解每种方法的利弊,以及每种实现中未解决的可能问题。希望它能帮助您成为图形大师。而且我相信我有望最终“得到”它。如果需要,请尝试使用这两种图形表示形式来实现深度优先搜索或宽度优先搜索算法。如果您正在阅读本文,并且发现一些错误或无法忍受的内容,请在评论部分留言,我们可以进行讨论。

图形对您来说容易吗?

附言:在这篇文章中,我没有涉及很多关于图形的内容。例如,循环图与非循环图。本文是关于用代码表示基本图形的,如果您想了解有关该主题的更多信息,那么在线上有很多资源可以帮助您更深入地学习该主题。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 如何在C#中表示图

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论