代表邻接矩阵/列表

Question

我很难想出合适的数据结构来表示无向图的邻接矩阵。

我希望能够从这些图中获取节点并将它们插入到数组中的随机位置，然后根据他们设法将相邻节点保持分开的程度对数组进行“评分”。即如果节点A和节点B连接在我的图中，并且阵列将它们放在一起，则会将+1添加到阵列的分数中，最低的分数阵列是最好的。

那么最好的数据结构用来表示一个节点集合，以及集合中每个节点的相邻节点呢？

Answer 1

如果我理解你的问题，我不认为它很清楚。 对于一个邻接矩阵，我认为最好的方法是数组。您可以访问O（1）中的每个位置，并且由于它是无向图，因此应该很容易创建。看到下面的图表

 0 --- 1------5---6 
     | \ \  |/
     | \ \ |/
     2 3----4---7 

      0 1 2 3 4 5 6 7 
      ----------------- 
     0 | 0 1 1 1 0 0 0 0 
     1 | 1 0 0 0 1 1 0 0 
     2 | 1 0 0 0 0 0 0 0 
     3 | 1 0 0 0 1 0 0 0 
     4 | 0 1 0 1 0 0 0 1 
     5 | 0 1 0 0 0 0 1 1 
     6 | 0 0 0 0 0 1 0 1 
     7 | 0 0 0 0 1 1 1 0 
      ------------------ 

你可以实现你的矩阵像这样，并执行任何你想要的操作。而所有重要的是，如果一个位置不是0，那么该图形就会连接起来，你可以为你正在做的任何事情选择最高的值。