我对图和邻接矩阵感到困惑。我正在为一个班级分配一个作业,我有一个节点的文本文件和一个边的文本文件,我必须阅读它们的每一个并将它们制成一个图,然后可以在该图上执行操作,例如确定该图是否为连接,找到最小的生成树,遍历并找到路径。但是我以前从未使用过图形,并且整个过程让我很困惑,我想知道是否有人可以帮助我解释其中的一些内容。
首先,我是否要自己建立一个图(也许有节点和边类?),然后从中构造一个邻接矩阵?还是邻接矩阵本身就是图?
然后我对如何在程序中实现相邻矩阵感到困惑。节点被命名为“ ND5”和“ NR7”之类的东西,因此我将不得不设置并读取[ND5] [NR7]的边缘,但是我不确定如何设置带有字符串的2d数组。外面和里面的数字。
我一直在互联网上进行搜索,并通读了我教科书中有关图形的整章内容,但实际上我并不仅仅了解设置此图形的最初基本步骤。我非常感谢您的帮助。谢谢。
首先,我是否要自己建立一个图(也许有节点和边类?),然后从中构造一个邻接矩阵?还是邻接矩阵本身就是图?
如果没有实际阅读作业说明,任何人都无法肯定地回答该问题。但是,除非分配中特别提及Node
和Edge
类,否则我的猜测是您仅应使用邻接矩阵来表示图形。
然后我对如何在程序中实现相邻矩阵感到困惑。节点被命名为“ ND5”和“ NR7”之类的东西,因此我将不得不设置和读取其边缘,
[ND5][NR7]
但是我不确定如何设置像这样的二维数组,其外部为字符串,内部为数字。
我完全可以理解您在这里的困惑。您实际要做的是在节点名称和矩阵索引之间创建双射(一对一关系)。例如,如果图形中有n个节点,则需要一个n×n矩阵(即new boolean[n][n]
),并且每个节点将对应于范围为0到n(不包括n)的单个整数。
我不确定目前为止您班上已经讲过什么数据结构,但是最简单的方法可能是使用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]);
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句