我正在尝试实现 Floyd-Warshall Algorithm .为此，我需要设置一个加权图的邻接矩阵。我该怎么做呢？我知道这些值并附上了加权图的图片。我试图寻找一些在线示例，但似乎找不到任何东西。我了解 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;
            }
        }
    }

}

这是手头的具体图表:

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

最佳答案

所以，你好像不熟悉Graphs ，看看维基百科。也浏览一些图片，更容易理解。

一些概念

您的图片可以表示为 Graph。通常，图是使用 2 种基本元素实现的，Nodes 和 Links(有时称为 Arcs)。

Node 代表图片中的字母，它们是 A、B、C 等。 Arc 或 Link，是连接两个节点的线，如果您查看 H 到 L 之间的连接，则两者之间存在链接，在加权图中，不同的链接有不同的权重。

解决您的问题 - 第 1 部分

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

节点

一个节点有一个名称，所以我们可以识别这个节点。一个节点可以连接到其他节点，我们可以使用一组节点，但你的是一个加权图，因此，每个连接都必须由链接节点及其权重表示。因此，我们使用 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 是一种包装类，用于组织目的。我还为图形声明了一个根，我们没有使用它，但在一些情况下很有用:

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

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

关于c# - 为加权图生成邻接矩阵，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15306040/