4

我对图和邻接矩阵感到很困惑。我正在为一个类做作业，其中我有一个节点的文本文件和一个边的文本文件，我必须阅读它们中的每一个并将它们制作成一个图，然后我可以在其上执行操作，例如确定图是否是连接，寻找最小生成树，遍历和寻找路径。不过，我以前从未使用过图表，而且我对整个事情感到非常困惑，我想知道是否有人可以帮助向我解释其中的一些内容。

首先，我是否自己构建一个图（也许有节点和边类？），然后从中构建一个邻接矩阵？还是邻接矩阵本身就是图？

然后我对如何将相邻矩阵实现到程序中感到困惑。节点是诸如“ND5”和“NR7”之类的名称，因此我必须设置和读取 [ND5][NR7] 的边缘，但我不知道如何设置一个带有字符串的二维数组外面和里面的数字。

我一直在互联网上搜索并通读教科书中有关图表的整章，但我真的不了解设置此图表的第一个基本步骤。我真的很感激帮助。谢谢。

4

1 回答 1

15

首先，我是否自己构建一个图（也许有节点和边类？），然后从中构建一个邻接矩阵？还是邻接矩阵本身就是图？

如果没有实际阅读您的作业说明，任何人都无法确定地回答这个问题。但是，除非作业特别提到Node和Edge类或其他东西，否则我的猜测是你应该使用邻接矩阵来表示你的图。

然后我对如何将相邻矩阵实现到程序中感到困惑。节点是诸如“ND5”和“NR7”之类的名称，所以我必须设置和读取边缘，[ND5][NR7]但我不知道如何设置一个像外部字符串和内部数字的二维数组.

我完全可以理解你在这里的困惑。您真正想要做的是在节点名称和矩阵索引之间创建一个双射（一对一的关系）。例如，如果您的图中有n 个节点，那么您需要一个n×n矩阵（即），并且每个节点将对应于从 0 到n（不包括 n）new boolean[n][n]范围内的单个整数。

到目前为止，我不确定您在课堂上涵盖了哪些数据结构，但最简单的方法可能是使用 a Map<String, Integer>，它可以让您查找类似的名称"ND5"并返回一个整数（索引） .

另一个不错的选择可能是使用数组。您可以将所有节点名称放入一个数组中，使用 对其进行排序Arrays.sort，然后一旦排序，您就可以使用它Arrays.binarySearch来查找该数组中特定节点名称的索引。我认为这个解决方案实际上比使用 a 更好，Map因为它可以让您以两种方式进行查找。您用于Arrays.binarySearch执行名称到索引的查找，并且您只需索引到数组来执行索引到名称的查找。

示例：假设我们有这个图表：

AB、AD、BD、CD

鉴于该图，以下是一些示例代码，说明如何执行此操作：（警告！未经测试）

import java.util.Arrays;

// Add all your node names to an array
String[] nameLookup = new String[4];
nameLookup[0] = "A";
nameLookup[1] = "B";
nameLookup[2] = "C";
nameLookup[3] = "D";

// Our array is already properly sorted,
// but yours might not be, so you should sort it.
// (if it's not sorted then binarySearch won't work)
Arrays.sort(nameLookup);

// I'm assuming your edges are unweighted, so I use boolean.
// If you have weighted edges you should use int or double.
// true => connected, false => not connected
// (entries in boolean arrays default to false)
boolean[][] matrix = new boolean[4];
for (int i=0; i<matrix.length; i++) matrix[i] = new boolean[4];

// I don't want to call Arrays.binarySearch every time I want an index,
// so I'm going to cache the indices here in some named variables.
int nodeA = Arrays.binarySearch(nameLookup, "A");
int nodeB = Arrays.binarySearch(nameLookup, "B");
int nodeC = Arrays.binarySearch(nameLookup, "C");
int nodeD = Arrays.binarySearch(nameLookup, "D");

// I'm assuming your edges are undirected.
// If the edges are directed then the entries needn't be semmetric.
// A is connected to B
matrix[nodeA][nodeB] = true;
matrix[nodeB][nodeA] = true;
// A is connected to D
matrix[nodeA][nodeD] = true;
matrix[nodeD][nodeA] = true;
// B is connected to D
matrix[nodeB][nodeD] = true;
matrix[nodeD][nodeB] = true;
// C is connected to D
matrix[nodeC][nodeD] = true;
matrix[nodeD][nodeC] = true;

// Check if node X is connected to node Y
int nodeX = Arrays.binarySearch(nameLookup, stringNameOfX);
int nodeY = Arrays.binarySearch(nameLookup, stringNameOfY);

if (matrix[nodeX][nodeY]) { /* They're connected */ }

// Print all of node Z's neighbors' names
int nodeZ = Arrays.binarySearch(nameLookup, stringNameOfZ);
for (int i=0; i<matrix.length; i++) {
  if (matrix[nodeZ][i]) {
    System.out.println(nameLookup[nodeZ] + " is connected to " + nameLookup[i]);
  }
}
于 2013-11-16T22:05:14.277 回答