java—将邻接矩阵转移到node类型的邻接链表

sf6xfgos  于 2021-07-11  发布在  Java
关注(0)|答案(1)|浏览(461)

我在做一个关于把邻接矩阵转移到node类型的邻接链表的赋值。这是输入和输出的示例

  1. Input:
  2. int [][] matrix = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 1 ,0}}
  3. Output:
  4. 0: Node 1 -> Node 3
  5. 1: Node 0
  6. 2: Node 3
  7. 3: Node 1 -> Node 2

到目前为止我就是这么做的
节点类:

  1. class Node{
  2. //attribute
  3. private int index;
  4. //constructor
  5. Node(){
  6. //basic constructor
  7. }
  8. //parametize constructor
  9. Node(int index){
  10. this.index = index;
  11. }
  12. //accessors
  13. public int getIndex(){
  14. return this.index;
  15. }
  16. //mutators
  17. public void setIndex(int tmpIndex){
  18. this.index = tmpIndex;
  19. }
  20. //method to print node
  21. public void printNode(){
  22. System.out.println(" -> Node " + this.index);
  23. }
  24. }

将矩阵转换为链表的图形类

  1. import java.util.*;
  2. class MyGraph{
  3. //attributes
  4. LinkedList<Node> adjListArray[];
  5. private int v; //vertex
  6. //basic constructor
  7. MyGraph(){ //initialize empty graph
  8. this.v = 0;
  9. this.adjListArray = new LinkedList[this.v];
  10. }
  11. //transform an adjacent matrix to an adjacent matrix
  12. public void matrixToList(int [][] matrix){
  13. //initialize number of vertices
  14. this.v = matrix[0].length;
  15. //create a new list for each vertex
  16. for(int i = 0; i<this.v; i++){
  17. adjListArray[i] = new LinkedList<>();
  18. }
  19. for(int i=0; i<this.v; i++){
  20. for(int j = 0; j<this.v; j++){
  21. if(matrix[i][j] == 1){
  22. adjListArray[i].add(new Node(j));
  23. }
  24. }
  25. }
  26. }
  27. //print method
  28. public void displayAdjListArray(){
  29. Node node = new Node();
  30. for(int i = 0; i<this.v; i++){
  31. System.out.print(i+": ");
  32. for(Node j : adjListArray[i]){
  33. j.printNode();
  34. }
  35. }
  36. }
  37. }

以及主要的测试类:

  1. import java.util.*;
  2. class Main{
  3. public static void main(String[] args) {
  4. MyGraph graph = new MyGraph();
  5. int [][] array = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 1 ,0}};
  6. graph.matrixToList(array);
  7. System.out.println("Adjacency List: ");
  8. graph.displayAdjListArray();
  9. }
  10. }

所以当我运行我的代码时,我得到一个索引越界的异常。你们能帮我解决这个问题吗,我对这样的数据结构还不熟悉,所以任何我可以改进代码的想法都会受到赞赏。谢谢

lokaqttq

lokaqttq1#

构造函数中存在问题:

  1. public MyGraph() { // initialize empty graph
  2. this.v = 0;
  3. this.adjListArray = new LinkedList[this.v];
  4. }

你用长度来创造 0 然后你分配 this.vmatrix[0].length 哪个是 4 .

  1. // initialize number of vertices
  2. this.v = matrix[0].length;

这会导致 ArrayIndexOutOfBoundsException :

  1. for (int i = 0; i < this.v; i++) {
  2. adjListArray[i] = new LinkedList<>();
  3. }

您可以将构造函数更改为初始化 v 以及 adjListArray 长度合适:

  1. public MyGraph(int v) { // initialize empty graph
  2. this.v = v;
  3. this.adjListArray = new LinkedList[this.v];
  4. }
展开查看全部

相关问题