hash_ir hash_ir - 4 months ago 48
Java Question

Graph using adjacency list in Java

I am trying to implement an undirected graph in Java using adjacency list from the following resource: http://www.geeksforgeeks.org/graph-and-its-representations/

The code runs without any errors but doesn't give any output. Here's the code:

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


Please help!

Answer

You haven't initialized elements with in array before you make a call to this.array[i].head. Hence you would be getting NullPointerExcpetion. Following fix should work

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

Note:

  1. You may follow StackOverflow documentation on arrays to understand in detail about how arrays work in Java
  2. I din't refactor other parts of your code