利用邻接矩阵解决图问题

Question

我只是想知道如何使用和邻接矩阵来解决图的问题。

例如，对于我的程序，我有两个项目的汇率。

构建有向图的输入:6件衬衫15只袜子输入构建有向图:2只袜子1件内衣

有向图：

衬衫--(6/15)--袜子--(2/1)-内衣

所以从衬衫到袜子的边缘是6，从袜子到衬衫的边缘是15，袜子到内衣的边缘是2，内衣到袜子的边缘是1。

输入比较:袜子衬衫解决方案: 15只袜子6件衬衫

输入比较:衬衫内衣解决方案: 12件衬衫15件内衣

我的问题是，我如何用邻接矩阵来表示它，并能够获得它的权重来解决问题。

对于上面的问题，我想有一个邻接矩阵，看起来像这样。

          shirts   socks  underwear
shirts    [ 0       6     0 ]
socks     [ 15      0     2 ]
underwear [ 0       1     0 ]

这是一个好的开始吗？我试着在代码之前弄懂逻辑。

只是寻找一些更多的信息，如何在更大的规模上做更多的项目和独立的图表。

Answer 1

我将给你一个关于什么是邻接图的基本提示。解决你的问题是你的作业，所以我不能做。

想象一下下面的图表：

    A-----B
   / \   | \
  /   \  |  \
 /     \ |   \
C-------D-----E

邻接矩阵告诉图中的哪个节点连接到哪个节点：

    A  B  C  D  E
A [ 0  1  1  1  0 ]
B [ 1  0  0  1  1 ]
C [ 1  0  0  1  0 ]
D [ 1  1  1  0  1 ]
E [ 0  1  0  1  0 ]

例如，条目(D，E)显示D和E是连接的，而(A，E)显示A和E不是。请注意，该矩阵是对称的，因为该图是无向的。

如果矩阵按如下方式加权：

    A--3--B
   / \   | \
  5   3  2  1
 /     \ |   \
C---2---D--7--E

然后，邻接矩阵显示哪些是连接的，以及权重是什么(假设0表示没有连接)：

    A  B  C  D  E
A [ 0  3  5  3  0 ]
B [ 3  0  0  2  1 ]
C [ 5  0  0  2  0 ]
D [ 3  2  2  0  7 ]
E [ 0  1  0  7  0 ]

在您的示例中，您的图是一组节点，这些节点的边指向一组其他节点。您的邻接矩阵看起来与您已经得到的非常相似，但值可能不正确。这些值应该是相同的，彼此都是负的，或者是1乘以另一个，这取决于你的算法是什么。

Answer 2

This是我之前写的一篇关于如何使用邻接矩阵或邻接列表表示图的文章。

它讨论了解决Minimum Spanning Tree图问题，以及哪种数据结构适合于解决该问题。我不确定你试图用你的图形问题来完成什么，但这将是你如何表示图形的一个起点。如果您添加更多信息，我将尝试编辑我的答案。