Java中的邻接矩阵

Question

Java中的邻接矩阵

4

我很困惑于图形和相邻矩阵。我正在为课程做作业，其中我有一个节点文本文件和一个边缘文本文件，我必须读取它们并将它们制作成图形，然后可以在其上执行操作，例如确定图形是否连接、查找最小生成树、遍历和查找路径。虽然我以前从未使用过图形，但我对整个过程感到非常困惑，我想知道是否有人能帮助我解释其中的一些内容。

首先，我应该单独构建一个图形（也许是用节点和边缘类？），然后从中构建相邻矩阵吗？还是相邻矩阵本身就是图形？

然后我不明白如何将相邻矩阵实现到程序中。节点名称为“ND5”和“NR7”之类的东西，因此我必须设置和读取[ND5] [NR7]的边缘，但我不确定如何使用字符串设置这样的2D数组，在内部使用数值。

我已经在互联网上搜索了很多，并且阅读了我的教科书中关于图形的整章内容，但我真的不理解设置此图形的第一步基本步骤。非常感谢您的帮助。谢谢。

- Josephine

尝试发布每个文件的小样本和您目前拥有的任何代码，以获得更好的帮助。 - Chandranshu

首先，我是要单独构建一个图（可能使用节点和边类），然后从中构建邻接矩阵吗？还是邻接矩阵本身就是图？除非实际阅读您的任务说明，否则没有人能确切回答这个问题。但是，除非任务明确提到“节点”和“边”类之类的内容，否则我的猜测是您只需使用邻接矩阵来表示您的图。 - DaoWen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DaoWen · Accepted Answer

首先，我应该单独建立一个图表（也许是使用节点和边缘类？），然后从那个图表构建邻接矩阵吗？还是邻接矩阵本身就是图表？

没有人能确切地回答这个问题，除非实际阅读您的任务说明。但是，除非任务明确提到Node和Edge类或类似的内容，否则我的猜测是您只需使用邻接矩阵来表示您的图表。

然后我对如何将相邻矩阵实现到程序中感到困惑。节点被命名为“ND5”和“NR7”之类的名称，因此我必须设置和读取

 [ND5] [NR7] 的边缘，但我不知道如何使用外部字符串和内部数字设置2D数组。
我完全理解你的困惑。你实际想要做的是在节点名称和矩阵索引之间创建一个双射（一对一关系）。例如，如果你的图中有n个节点，则需要一个n×n矩阵（即new boolean[n][n]），每个节点对应于范围为0到n（不包括n）的单个整数。
我不确定你的课程已经涵盖了哪些数据结构，但最简单的方法可能是使用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]);
  }
}