Java中的邻接矩阵

Question

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

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

然后，我对如何在
程序中实现相邻矩阵感到困惑。节点被命名为“ ND5”和“ NR7”之类的东西，因此我将不得不
设置并读取[ND5] [NR7]的边缘，但是我不确定如何为
字符串设置像这样的二维数组外面和里面的数字。

我一直在互联网上进行搜索，并通读了
教科书中有关图形的整章内容，但实际上我并不仅仅了解
设置此图形的第一步。我真的很感谢您的帮助。
谢谢。

Answer 1

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

没有人真正阅读您的作业说明就无法肯定地回答该问题。但是，除非分配中特别提及Node和Edge类，否则我的猜测是您仅应使用邻接矩阵来表示图形。

然后，我对如何在程序中实现相邻矩阵感到困惑。节点被命名为“ ND5”和“ NR7”之类的东西，因此我将不得不设置并读取其边缘，[ND5][NR7]但是我不确定如何设置一个二维数组，其外部为字符串，内部为数字。

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

我不确定目前为止您班上已经讲过什么数据结构，但是最简单的方法可能是使用Map ，
它可以让您查找类似的名称”ND5”并获取整数（索引） 。

另一个不错的选择是使用数组。你可以把你所有的节点名称到一个数组，排序它Arrays.sort，然后一旦它的排序，你可以使用 发现，阵列中的特定节点名的索引。我认为该 解决方案实际上比使用a更好，因为它可以让您 双向进行查找。您曾经 用来进行名称到索引的查找，而您只是在数组中建立索引以执行索引到 名称的查找。
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]);
  }
}