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

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

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

Input:
int [][] matrix = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 1 ,0}}

Output:
0: Node 1 -> Node 3
1: Node 0
2: Node 3
3: Node 1 -> Node 2

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

class Node{
    //attribute
    private int index;

    //constructor
    Node(){
        //basic constructor
    }

    //parametize constructor
    Node(int index){
        this.index = index;
    }

    //accessors
    public int getIndex(){
        return this.index;
    }

    //mutators
    public void setIndex(int tmpIndex){
        this.index = tmpIndex;
    }

    //method to print node
    public void printNode(){
        System.out.println(" -> Node " + this.index);
    }
}

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

import java.util.*;
class MyGraph{
    //attributes
    LinkedList<Node> adjListArray[];
    private int v; //vertex

    //basic constructor
    MyGraph(){ //initialize empty graph
        this.v = 0;
        this.adjListArray = new LinkedList[this.v];
    }

    //transform an adjacent matrix to an adjacent matrix
    public void matrixToList(int [][] matrix){
        //initialize number of vertices
        this.v = matrix[0].length;

        //create a new list for each vertex
        for(int i = 0; i<this.v; i++){
            adjListArray[i] = new LinkedList<>();
        }

        for(int i=0; i<this.v; i++){
            for(int j = 0; j<this.v; j++){
                if(matrix[i][j] == 1){
                    adjListArray[i].add(new Node(j));
                }
            }
        }
    }

    //print method
    public void displayAdjListArray(){
        Node node = new Node();
        for(int i = 0; i<this.v; i++){
            System.out.print(i+": ");
            for(Node j : adjListArray[i]){
                j.printNode();
            }
        }
    }
}

以及主要的测试类:

import java.util.*;

class Main{
    public static void main(String[] args) {
        MyGraph graph = new MyGraph();

        int [][] array = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 1 ,0}};
        graph.matrixToList(array); 
        System.out.println("Adjacency List: "); 

        graph.displayAdjListArray();
    }
}

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

lokaqttq

lokaqttq1#

构造函数中存在问题:

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

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

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

这会导致 ArrayIndexOutOfBoundsException :

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

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

public MyGraph(int v) { // initialize empty graph
    this.v = v;
    this.adjListArray = new LinkedList[this.v];
}

相关问题