How does this code of printing graph work?

Question

I was studying BFS on geeksforgeeks and i actually got confused on 2nd for loop "for(Integer pCrawl: graph.adjListArray[v])". Can anyone explain this part?

static void printGraph(Graph graph) 
    {        
        for(int v = 0; v < graph.V; v++) 
        { 
            System.out.println("Adjacency list of vertex "+ v); 
            System.out.print("head"); 
            for(Integer pCrawl: graph.adjListArray[v]){ 
                System.out.print(" -> "+pCrawl); 
            } 
            System.out.println("\n"); 
        } 
    }

following is the code of graph

class Graph 
{ 
    private int V;   // No. of vertices 
    private LinkedList<Integer> adj[]; //Adjacency Lists 

    // Constructor 
    Graph(int v) 
    { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 

    // Function to add an edge into the graph 
    void addEdge(int v,int w) 
    { 
        adj[v].add(w); 
    }

What is `graph.V`, edit your question with definition of Graph class? — Ashvin Sharma, Sep 12 '19 at 06:55
i believe `graph.adjListArray[v]` is a list and `for(Integer pCrawl: graph.adjListArray[v])` is a way to iterate over the list. https://stackoverflow.com/questions/18410035/ways-to-iterate-over-a-list-in-java — Nafis Islam, Sep 12 '19 at 06:57

score 0 · Answer 1 · answered Sep 12 '19 at 07:03

0

The second loop just iterate over all the elements in the graph.adjListArray[v]

int[] array = {1, 2, 3};
for (int n: array) {
   System.out.println(n);
}

Prints:

1
2
3

answered Sep 12 '19 at 07:03

kumarchandresh

559
2
16

score 0 · Answer 2 · answered Sep 12 '19 at 07:05

I guess you are using graph following example:

static class Graph 
{ 
    int V; 
    LinkedList<Integer> adjListArray[]; 

    // constructor  
    Graph(int V) 
    { 
        this.V = V; 

        // define the size of array as  
        // number of vertices 
        adjListArray = new LinkedList[V]; 

        // Create a new list for each vertex 
        // such that adjacent nodes can be stored 
        for(int i = 0; i < V ; i++){ 
            adjListArray[i] = new LinkedList<>(); 
        } 
    } 
}

So, second iteration is iteration through nodes on single level (v - index of the level).

for(Integer pCrawl: graph.adjListArray[v]){ 
    System.out.print(" -> "+pCrawl); 
}

score 0 · Answer 3 · answered Sep 12 '19 at 08:39

for all the Vertex of graph. first loop will iterate over them and inner loop will print every vertex adjacent elements.. means it will start with root as root will have no adjacent so it will move to next element of next element from root and than print its adjacent .. and this will go on.. Breath First Search is :

We traverse through one entire level of children nodes first, before moving on to traverse through the grandchildren nodes. And we traverse through an entire level of grandchildren nodes before going on to traverse through great-grandchildren nodes.

so lets assume our Tree is :

this algorithm will work like: first vertex is 1 it will print 1. but 1 have no adjacent element so it will move to next vertex 2 and print its adjacent which is 3 now now out put will be 1 ,2,3 . our next vertex will be 4 and it will print its adjacent which are 5,6,7 so that's how it did the breath first search.. traversing all the element on on level before going to next level.. i hope it will clear..

How does this code of printing graph work?

3 Answers3