BFS Graph loop execution

Animesh Srivastava :

I am trying to traverse breadth first in graph formed . My graph is in adjacency list by arraylist of arraylist as below

void bfs(int root,Graph g)
    {
        boolean[] visited = new boolean[g.al.size()];
        Queue<Integer> q = new LinkedList<Integer>();
        
        q.add(root);
        
        
        
        visited[root] = true;
        
        while(!q.isEmpty())
        {
            int v = q.remove();
            System.out.print(v);
        
       // **Using for each loop ( i.e. for(int k:g.al.get(v))) works well , but it isn't working with this for loop**
        for(int k= g.al.get(v).get(0) ; k <= g.al.get(v).size() ; k++ )
        {
            if(visited[k]==false)
            {
                visited[k]=true;
                q.add(k);
            }
        }           
        }           
    }

My Graph class is as follows :

class Graph
    {
        int v;
        ArrayList<ArrayList<Integer>> al = new ArrayList<>();
        
        Graph(int v)
        {
            this.v = v;
            
            for(int i = 0 ; i < v; i++)
            {
                al.add(new ArrayList<Integer>());
            }
            
            
        }
    
    public Graph() {
            // TODO Auto-generated constructor stub
        }

    void addEdge(int sr,int des)
    {
        al.get(sr).add(des);
        al.get(des).add(sr);
    }
    

The for loop in bfs function is executing for the node passed first time only .It adds the elements in queue for the node passed first time. Then after going in while loop not falling under the for loop .

DelfikPro :

The difference between enhanced for loop and indexed for loop is that they iterate through values and indexes respectively

In your code the k variable is an index, not an actual graph value.

The enhanced for (int k : g.al.get(v))) goes over all values and similar indexed for loop behaviour can be achieved by iterating through indexes and fetching a corresponding value for each index

ArrayList<Integer> list = g.al.get(v);
for (int k = 0 ; k < list.size() ; k++ ) {
    int value = list.get(k);
    if (visited[value] == false) {
         visited[value] = true;
         q.add(value);
    }
}

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related