BFS Graph循环执行

Question

我试图在形成的图形中首先遍历广度。我的图在 arraylist 的 arraylist 的邻接列表中，如下所示

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

我的图表class如下：

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

bfs函数中的for循环只对第一次通过的节点执行，为第一次通过的节点添加队列中的元素。然后进入 while 循环后不属于 for 循环 .

Answer 1

enhanced for 循环和indexed for 循环的区别在于它们遍历values和索引分别

在您的代码中，k 变量是一个 index， 而不是 实际图表 value.

增强的 for (int k : g.al.get(v))) 遍历所有 values 并且类似的索引 for 循环行为可以通过遍历 indexes 和为每个 index

获取相应的 value

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

BFS Graph循环执行

BFS Graph loop execution

java

graph

breadth-first-search

data-structures