java - Java中的邻接矩阵

Question

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

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

然后我对如何在程序中实现相邻矩阵感到困惑。节点的名称类似于“ND5”和“NR7”，因此我必须设置和读取 [ND5][NR7] 的边缘，但我不确定如何使用字符串设置二维数组外面和里面的数字。

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

Answer 1

Firstly, do I build a graph on its own (with node and edges classes perhaps?) and then construct an adjacency matrix from that? Or is the adjacency matrix itself the graph?

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

And then I'm confused on how to implement the adjacent matrix into the program. The nodes are names things like "ND5" and "NR7" and so I would have to set and read the edges of [ND5][NR7] but I'm not sure how to set up a 2d array like that with strings for the outside and numbers on the inside.

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

到目前为止，我不确定您在类(class)中涵盖了哪些数据结构，但最简单的方法可能是使用 Map<String, Integer> , 这会让你查找像 "ND5" 这样的名字并取回一个整数(索引)。

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

---

示例:假设我们有这张图:

鉴于该图表，这里有一些示例代码可以说明如何执行此操作:(警告!它未经测试)

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]);
  }
}