Java中的邻接矩阵

Question

我对图表和邻接矩阵感到困惑.我正在为一个类做一个任务,我有一个节点的文本文件和一个边缘的文本文件,我必须阅读它们中的每个并使它们成为一个图形,然后我可以在其上执行操作,例如确定图形是否为连接,找到最小的生成树,遍历和查找路径.我之前从未使用过图表,而且我对整个事情感到困惑,我想知道是否有人可以帮我解释一下这些.

首先,我自己构建一个图形(可能是节点和边类？)然后从中构造一个邻接矩阵？或者邻接矩阵本身是图形？

然后我对如何将相邻矩阵实现到程序中感到困惑.节点的名称是"ND5"和"NR7",所以我必须设置和读取[ND5] [NR7]的边缘,但我不知道如何设置像这样的2d数组的字符串外面和里面的数字.

我一直在网上搜索并阅读我教科书中关于图表的整章,我真的不明白设置这个图的第一步基本步骤.我非常感谢你的帮助.谢谢.

Answer 1

首先,我自己构建一个图形(可能是节点和边类？)然后从中构造一个邻接矩阵？或者邻接矩阵本身是图形？

如果没有真正阅读你的作业说明,任何人都无法肯定地回答这个问题.但是,除非作业特别提及Node和Edge类或其他东西,我的猜测是你应该使用邻接矩阵来表示你的图形.

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

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

我不确定你到目前为止在你的类中已经覆盖了什么数据结构,但是最简单的方法可能是使用a Map<String, Integer>,它可以让你查找一个名称"ND5"并获得一个整数(索引) .

另一个不错的选择可能是使用数组.您可以将所有节点名称放入一个数组中,对其进行排序Arrays.sort,然后一旦排序,您就可以使用它Arrays.binarySearch来查找该数组中特定节点名称的索引.我认为这个解决方案实际上比使用a更好,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]);
  }
}