广度优先搜索bfs遍历图

广度优先搜索bfs遍历图
建立一个队列，把初始定点加入队列，然后每次都取出队首元素进行访问，并把该定点除法可以到达的未曾加入过队列（而不是未访问）的定点全部加入队列，直到队列为空

bfs(u) {
  queue q;
  将u入队
  inq[u] = true;
  while(q非空) {
    for(从u除法道可到达的所有定点v) {
      if(inq[v] == false)
        将v入队
        inq[v] = true;
    }
  }
}
bfsTrave(G) {
  for(G的所有顶点u) {
    if(inq[u] == false)
      bfs(u);
  }
}

void bfs(int u) {
  queue<int> q;
  q.push(u);
  inq[u] = true;
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    for(int v = 0; v < n; v++) {
      if(inq[v] == false && G[u][v] != INF) {
        q.push(v);
        inq[v] = true;
      }
    }
  }
}
/*邻接表：
for(int i = 0; i < arr[u].size(); i++) {
  int v= arr[u][i];
  if(inq[v] == false) {
    q.push(v);
    inq[v] = true;
  }
}
*/
 
void bfsTrave() {
  for(int u = 0; u < n; u++) {
    if(inq[u] == false)
      bfs(q);
  }
}

//带层数的
struct node {
  int v;
  int layer;
}
next.layer = top.layer + 1;