英文:
BFS Graph loop execution
问题
我正在尝试在构建的图中进行广度优先遍历。我的图是由数组列表的数组列表构成的邻接表，如下所示：
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);
// **对于每个循环（即for(int k:g.al.get(v))），它运行良好，但对于这个循环不起作用**
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);
}
}
}
}
我的Graph类如下所示：
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循环。
英文:
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 .
答案1
得分: 0
增强型for循环与索引型for循环的区别在于它们分别通过值和索引进行迭代。
在您的代码中，变量 k 是一个索引，而不是实际的图值。
增强型for (int k : g.al.get(v)) 循环遍历所有值，类似的索引型for循环行为可以通过遍历索引并获取相应的值来实现每个索引。
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);
}
}
英文:
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);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论