如何在 Java 中使用邻接表实现图

Question

我正在尝试使用来自以下资源的邻接表在 Java 中实现无向图：http://www.geeksforgeeks.org/graph-and-its-representations/

代码运行没有任何错误，但没有给出任何输出。这是代码：

class AdjListNode{
    int dest;
    AdjListNode next;

    public AdjListNode(int dest){
        this.dest = dest;
        this.next = null;
    }
}

class AdjList{
    AdjListNode head;
}

public class graph{
    int V;
    AdjListNode newNode;
    AdjList array[];

    public graph(int V){
        this.V = V;
        this.array = new AdjList[V];
        int i;
        for(i=0;i<V;++i){
            this.array[i].head = null;
        }
    }

    void addEdge(graph g, int src, int dest){
        newNode = new AdjListNode(dest);
        newNode.next = g.array[src].head;
        g.array[src].head = newNode;

        newNode = new AdjListNode(src);
        newNode.next = g.array[dest].head;
        g.array[dest].head = newNode;
    }

    void printGraph(graph g){
        int v;
        for(v=0;v < g.V;++v){
            AdjListNode pCrawl = g.array[v].head;
            System.out.println();
            System.out.println("Adjacency list of vertex "+v);
            System.out.print("head");
            while(pCrawl != null){
                System.out.print(pCrawl.dest);
                pCrawl = pCrawl.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args){
        int V = 5;
        graph g = new graph(V);
        g.addEdge(g,0,1);
        g.addEdge(g,0,4);
        g.addEdge(g,1,2);
        g.addEdge(g,1,3);
        g.addEdge(g,1,4);
        g.addEdge(g,2,3);
        g.addEdge(g,3,4);

        g.printGraph(g);
    }
}

请帮忙！

Answer 1

在调用 this.array[i].head 之前，您尚未使用 in array 初始化元素。因此你会得到 NullPointerExcpetion。以下修复应该有效

public graph(int V){
    this.V = V;
    this.array = new AdjList[V];
    int i;
    for(i=0;i<V;++i){
        this.array[i] = new AdjList();
    }
}

注：

您可以关注 Oracle tutorial on arrays 以详细了解数组在 Java
我没有重构你代码的其他部分

如何在 Java 中使用邻接表实现图

How to implement Graph using Adjacency List in Java

java

algorithm

graph

adjacency-list

data-structures