Java中的邻接矩阵 [英] Adjacency Matrix In Java

问题描述

我被图和邻接矩阵搞糊涂了。我正在做一个类的任务，我有一个节点的文本文件和一个边缘文本文件，我必须读取它们中的每一个，并将它们绘制成一个图形，然后我可以执行操作，比如确定图形是否连接，寻找最小生成树，遍历和查找路径。我从来没有用过图表，但我对整个事情感到困惑，而且我想知道是否有人可以帮我解释一些。

首先，我是否自己创建一个图（可能有节点和边的类），然后用它构造一个邻接矩阵？或者是邻接矩阵本身的图？

然后我很困惑如何在程序中实现相邻矩阵。节点的名称就像ND5和NR7，所以我必须设置和读取[ND5] [NR7]的边缘，但我不知道如何设置一个2d数组外面和里面的数字。

我一直在搜索整个互联网，并阅读我的教科书中关于图表的整章，我真的不理解只是获取此图表的第一个基本步骤。我真的很感激帮助。首先，我是否自己构建一个图（带有节点和边的类）也许？），然后构造一个邻接矩阵？或者说邻接矩阵本身就是图表？

任何人都无法确切地回答这个问题，而没有真正阅读你的指令分配。然而，除非这个任务特别提到了 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; 
 
 //将所有节点名称添加到数组
 String [] nameLookup = new String [4]; 
 nameLookup [0] =A; 
 nameLookup [1] =B; 
 nameLookup [2] =C; 
 nameLookup [3] =D; 
 
 //我们的数组已经正确排序，
 //但你的可能不是，所以你应该对它进行排序。 
 //（如果它没有排序，那么binarySearch将不起作用）
 Arrays.sort（nameLookup）; 
 
 //我假设你的边缘是未加权的，所以我使用布尔值。 
 //如果你有加权边缘，你应该使用int或double。 
 // true =>连接，false =>未连接
 //（布尔数组中的条目默认为false）
 boolean [] [] matrix = new boolean [4]; 
 for（int i = 0; i< matrix.length; i ++）matrix [i] = new boolean [4]; 
 
 //我不想在每次需要索引时调用Arrays.binarySearch，
 //所以我将在这里缓存一些指定变量的索引。 
 int nodeA = Arrays.binarySearch（nameLookup，A）; 
 int nodeB = Arrays.binarySearch（nameLookup，B）; 
 int nodeC = Arrays.binarySearch（nameLookup，C）; 
 int nodeD = Arrays.binarySearch（nameLookup，D）; 
 
 //我假设你的边缘是无向的。 
 //如果边是指向的，则条目不必是半角。 
 // A连接到B 
矩阵[nodeA] [nodeB] = true; 
 matrix [nodeB] [nodeA] = true; 
 // A连接到D 
矩阵[nodeA] [nodeD] = true; 
 matrix [nodeD] [nodeA] = true; 
 // B连接到D 
矩阵[nodeB] [nodeD] = true; 
 matrix [nodeD] [nodeB] = true; 
 // C连接到D 
矩阵[nodeC] [nodeD] = true; 
 matrix [nodeD] [nodeC] = true; 
 
 //检查节点X是否连接到节点Y 
 int nodeX = Arrays.binarySearch（nameLookup，stringNameOfX）; 
 int nodeY = Arrays.binarySearch（nameLookup，stringNameOfY）; 
 
 if（matrix [nodeX] [nodeY]）{/ *它们已连接* /} 
 
 //打印所有节点Z的邻居名称
 int nodeZ = Arrays.binarySearch（nameLookup，stringNameOfZ）; 
 for（int i = 0; i< matrix.length; i ++）{
 if（matrix [nodeZ] [i]）{
 System.out.println（nameLookup [nodeZ] + 连接到+ nameLookup [i]）; 
} 
} 
  

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.

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.

解决方案

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 Node and Edge classes or something, my guess is that you're just supposed to use the adjacency matrix to represent your 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.

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 n nodes in your graph, then you need an n×n matrix (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).

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).

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.binarySearch to find the index of a particular node name in that array. I think this solution is actually better than using a Map because it lets you do the lookups both ways. You use Arrays.binarySearch to do name-to-index lookups, and you just index into the array to do an index-to-name lookup.

---

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

这篇关于Java中的邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！