c# - 为加权图生成邻接矩阵

Question

我正在尝试实现Floyd-Warshall Algorithm。为此，它需要我设置adjacency matrix 一个加权图。我该怎么做呢？我知道这些值并附上了加权图的图片。我试图在网上寻找一些这样的例子，但我似乎找不到任何东西。我了解 Floyd-Warshall 算法，我只需要帮助设置它，以便我能够实现它。这是我之前构建的一个，但我不必使用特定的值。

代码：

public static void buildAdjMatrix()
{

    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            if (directionAllowed(i, j) == true)
            {
                adjMatrix[i, j] = 1;
            }
            else
            {
                adjMatrix[i, j] = 50;
            }
        }
    }

}

这是手头的特定图表：

这是我需要创建的矩阵的图片。抱歉质量太差了...

Answer 1

因此，您似乎对Graphs不熟悉，请查看 Wikipedia。也浏览一些图像，它变得更容易理解。

一点概念

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

ANode代表您图片中的字母，它们将是 A、B、C 等。 An ArcorLink是连接两个节点的线，如果您查看 H 到 L 之间的连接，则两者之间有联系，在 a加权图，不同的链接有不同的权重。

解决您的问题 - 第 1 部分

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

节点

一个节点有一个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;
    }
}

弧

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

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

图形

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 x n，其中 n 是我们从图形类中获得的节点数。对于每个节点，我们搜索它们是否有链接，如果它们有链接，则在适当的位置填充矩阵。看，在你的邻接矩阵例子中，你只有1s，这里我放了链接的权重，我是这样放的，所以有一个加权图是没有意义的！

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, ., &, ]