Java中的邻接矩阵

Adjacency Matrix In Java

提问by Josephine

I'm so confused by graphs and adjacency matrices. I'm doing an assignment for a class where I have a text file of nodes and a text file of edges and I have to read each of them and make them a graph onto which I can then perform operations such as determining if the graph is connected, finding a minimal spanning tree, traversals and finding paths. I've never worked with graphs before though, and I'm really confused by the whole thing, and I was wondering if someone could help explain some of this to me.

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

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?

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

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.

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

I've been searching all over the internet and read through the whole chapter on graphs in my textbook, and I'm really not understanding just the first basic steps of getting this graph set up. I'd really appreciate the help. Thanks.

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

采纳答案by DaoWen

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?

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

There is no way anyone can answer that question for sure without actually reading the instructions for your assignment. However, unless the assignment specifically mentions Nodeand Edgeclasses or something, my guess is that you're just supposed to use the adjacency matrix to represent your 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.

然后我对如何在程序中实现相邻矩阵感到困惑。节点是诸如“ND5”和“NR7”之类的名称，因此我必须设置和读取 的边缘，[ND5][NR7]但我不确定如何设置这样的二维数组，外部为字符串，内部为数字.

I can totally understand your confusion here. What you actually want to do is create a bijection(a one-to-one relationship) between your node names and the indices of your matrix. For example, if you have nnodes in your graph, then you need an n×nmatrix (i.e. new boolean[n][n]), and each of your nodes would correspond to a single integer in the range 0 until n(not inclusive of n).

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

I'm not sure what data structures you've covered in your class so far, but the easiest way to do this would probably be to use a Map<String, Integer>, which would let you look up a name like "ND5"and get back an integer (the index).

到目前为止，我不确定您在类中涵盖了哪些数据结构，但最简单的方法可能是使用 a Map<String, Integer>，它可以让您查找名称，"ND5"并返回一个整数（索引） .

Another nice alternative might be to use an array. You could put all your node names into an array, sort it with Arrays.sort, and then once it's sorted you can use Arrays.binarySearchto find the index of a particular node name in that array. I think this solution is actually better than using a Mapbecause it lets you do the lookups both ways. You use Arrays.binarySearchto do name-to-index lookups, and you just index into the array to do an index-to-name lookup.

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

---

---

Example:Let's say we have this graph:

示例：假设我们有这个图：

Given that graph, here's some sample code of how you could do this: (warning! it's untested)

鉴于该图，这里有一些示例代码，说明如何执行此操作：（警告！未经测试）

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