1 回答

• 37

  所以，你似乎不熟悉Graphs，看看维基百科 . 还浏览一些图像，它更容易理解 .

  一点概念

  您的照片可以表示为 Graph . 通常，图形使用2种基本类型的元素实现， Nodes 和 Links （有时称为 Arcs ） .

  一个 Node 表示你图片中的字母，它们将是A，B，C等 . 一个 Arc 或 Link ，是连接两个节点的线，如果看看H到L之间的连接，两者之间有一个连接在加权图中，不同的链接具有不同的权重 .

  解决您的问题 - 第1部分

  我们要做的是在代码中将图片表示为图形，所以让我们开始创建基本元素 Node 和 Arc ：

  Node

  节点有 Name ，因此我们可以识别节点 . 并且节点可以连接到其他节点，我们可以使用节点集合，但是您的节点是加权图，因此，每个连接必须由链接节点和它的权重来表示 . 因此，我们使用Arcs的集合 .

  public class Node
  {
      public string Name;
      public List<Arc> Arcs = new List<Arc>();
  
      public Node(string name)
      {
          Name = name;
      }
  
      /// <summary>
      /// Create a new arc, connecting this Node to the Nod passed in the parameter
      /// Also, it creates the inversed node in the passed node
      /// </summary>
      public Node AddArc(Node child, int w)
      {
          Arcs.Add(new Arc
          {
              Parent = this,
              Child = child,
              Weigth = w
          });
  
          if (!child.Arcs.Exists(a => a.Parent == child && a.Child == this))
          {
              child.AddArc(this, w);
          }
  
          return this;
      }
  }
  

  Arc

  真正简单的类，它包含链接的节点，以及连接的权重：

  public class Arc
  {
      public int Weigth;
      public Node Parent;
      public Node Child;
  }
  

  Graph

  Graph是一种包装类，用于组织目的 . 我也为图表声明了一个Root，我们没有使用它，但在以下几种情况下很有用：

  public class Graph
  {
      public Node Root;
      public List<Node> AllNodes = new List<Node>();
  
      public Node CreateRoot(string name)
      {
          Root = CreateNode(name);
          return Root;
      }
  
      public Node CreateNode(string name)
      {
          var n = new Node(name);
          AllNodes.Add(n);
          return n;
      }
  
      public int?[,] CreateAdjMatrix()
      {
          // Matrix will be created here...
      }
  }
  

  解决您的问题 - 第2部分

  现在我们拥有了用于保存图形的所有数据结构，让我们用一些数据填充它 . 这是一些初始化类似于您的立方体图片的图形的代码 . 它枯燥乏味，但在现实生活中，图形将动态创建：

  static void Main(string[] args)
  {
      var graph = new Graph();
  
      var a = graph.CreateRoot("A");
      var b = graph.CreateNode("B");
      var c = graph.CreateNode("C");
      var d = graph.CreateNode("D");
      var e = graph.CreateNode("E");
      var f = graph.CreateNode("F");
      var g = graph.CreateNode("G");
      var h = graph.CreateNode("H");
      var i = graph.CreateNode("I");
      var j = graph.CreateNode("J");
      var k = graph.CreateNode("K");
      var l = graph.CreateNode("L");
      var m = graph.CreateNode("M");
      var n = graph.CreateNode("N");
      var o = graph.CreateNode("O");
      var p = graph.CreateNode("P");
  
      a.AddArc(b, 1)
       .AddArc(c, 1);
  
      b.AddArc(e, 1)
       .AddArc(d, 3);
  
      c.AddArc(f, 1)
       .AddArc(d, 3);
  
      c.AddArc(f, 1)
       .AddArc(d, 3);
  
      d.AddArc(h, 8);
  
      e.AddArc(g, 1)
       .AddArc(h, 3);
  
      f.AddArc(h, 3)
       .AddArc(i, 1);
  
      g.AddArc(j, 3)
       .AddArc(l, 1);
  
      h.AddArc(j, 8)
       .AddArc(k, 8)
       .AddArc(m, 3);
  
      i.AddArc(k, 3)
       .AddArc(n, 1);
  
      j.AddArc(o, 3);
  
      k.AddArc(p, 3);
  
      l.AddArc(o, 1);
  
      m.AddArc(o, 1)
       .AddArc(p, 1);
  
      n.AddArc(p, 1);
  
      // o - Already added
  
      // p - Already added
  
      int?[,] adj = graph.CreateAdjMatrix(); // We're going to implement that down below
  
      PrintMatrix(ref adj, graph.AllNodes.Count); // We're going to implement that down below
  }
  

  解决您的问题 - 第3部分

  所以，我们有一个完整的初始化图，让我们创建矩阵 . 下一个方法创建一个二维矩阵，n乘n，其中n是我们从图类中得到的节点数 . 对于节点的Foreach，我们搜索它们是否有链接，如果它们有链接，则在适当的位置填充矩阵 . 看看在你的邻接矩阵示例中，你只有 1 s，这里我把链接的权重，我've put this way, so there'在加权图中没有意义！

  public int?[,] CreateAdjMatrix()
  {
      int?[,] adj = new int?[AllNodes.Count, AllNodes.Count];
  
      for (int i = 0; i < AllNodes.Count; i++)
      {
          Node n1 = AllNodes[i];
  
          for (int j = 0; j < AllNodes.Count; j++)
          {
              Node n2 = AllNodes[j];
  
              var arc = n1.Arcs.FirstOrDefault(a => a.Child == n2);
  
              if (arc != null)
              {
                  adj[i, j] = arc.Weigth;
              }
          }
      }
      return adj;
  }
  

  完成

  完成后，你有加权邻接矩阵，有些方法可以打印它：

  private static void PrintMatrix(ref int?[,] matrix, int Count)
  {
      Console.Write("       ");
      for (int i = 0; i < Count; i++)
      {
          Console.Write("{0}  ", (char)('A' + i));
      }
  
      Console.WriteLine();
  
      for (int i = 0; i < Count; i++)
      {
          Console.Write("{0} | [ ", (char)('A' + i));
  
          for (int j = 0; j < Count; j++)
          {
              if (i == j)
              {
                  Console.Write(" &,");
              }
              else if (matrix[i, j] == null)
              {
                  Console.Write(" .,");
              }
              else
              {
                  Console.Write(" {0},", matrix[i, j]);
              }
  
          }
          Console.Write(" ]\r\n");
      }
      Console.Write("\r\n");
  }
  

  什么给我们以下输出：

  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
  A | [  &, 1, 1, ., ., ., ., ., ., ., ., ., ., ., ., ., ]
  B | [  1, &, ., 3, 1, ., ., ., ., ., ., ., ., ., ., ., ]
  C | [  1, ., &, 3, ., 1, ., ., ., ., ., ., ., ., ., ., ]
  D | [  ., 3, 3, &, ., ., ., 8, ., ., ., ., ., ., ., ., ]
  E | [  ., 1, ., ., &, ., 1, 3, ., ., ., ., ., ., ., ., ]
  F | [  ., ., 1, ., ., &, ., 3, 1, ., ., ., ., ., ., ., ]
  G | [  ., ., ., ., 1, ., &, ., ., 3, ., 1, ., ., ., ., ]
  H | [  ., ., ., 8, 3, 3, ., &, ., 8, 8, ., 3, ., ., ., ]
  I | [  ., ., ., ., ., 1, ., ., &, ., 3, ., ., 1, ., ., ]
  J | [  ., ., ., ., ., ., 3, 8, ., &, ., ., ., ., 3, ., ]
  K | [  ., ., ., ., ., ., ., 8, 3, ., &, ., ., ., ., 3, ]
  L | [  ., ., ., ., ., ., 1, ., ., ., ., &, ., ., 1, ., ]
  M | [  ., ., ., ., ., ., ., 3, ., ., ., ., &, ., 1, 1, ]
  N | [  ., ., ., ., ., ., ., ., 1, ., ., ., ., &, ., 1, ]
  O | [  ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ., ]
  P | [  ., ., ., ., ., ., ., ., ., ., 3, ., 1, 1, ., &, ]
  

  回复于 2024-05-02T11:37:39+08:00