圖的廣度優先遍歷

#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int MAXV = 1000;
const int INF = 1000000000; //下標代表點,數組元素代表連接的點 
//圖的鄰接表 
vector<int> Adj[MAXV];
//頂點數 
int n;//DFS 如果頂點i已經被訪問，則vis[i]=true,初始值為false 
bool vis[MAXV] = {false};//BFS 
bool inq[MAXV] =  { false };//u:當前訪問的頂點編號
//depth為深度 
void DFS(int u,int depth)
{//輸出，并設置頂點已經被訪問 cout << u ;vis[u] = true;for(int i=0;i<Adj[u].size();i++){//與u相接的頂點 int v = Adj[u][i];//如果沒有被訪問 if(vis[v] == false){DFS(v,depth + 1);}}} //測試DFS int main1(){Adj[0].push_back(1);Adj[0].push_back(2);Adj[1].push_back(0);Adj[1].push_back(2);Adj[1].push_back(3);Adj[1].push_back(4);Adj[2].push_back(0);Adj[2].push_back(1);Adj[2].push_back(4);Adj[3].push_back(1);Adj[3].push_back(4);Adj[3].push_back(5);Adj[4].push_back(1);Adj[4].push_back(2);Adj[4].push_back(3);Adj[4].push_back(5);Adj[5].push_back(1);Adj[5].push_back(4);DFS(0,1);return 0;}//遍歷單個連通塊 void BFS(int u){queue<int> q;q.push(u);inq[u] = true;while(!q.empty()){int u = q.front();cout << u ;q.pop();for(int i=0;i<Adj[u].size();i++){int v = Adj[u][i];if(inq[v] == false){q.push(v);inq[v] = true;//標記v為已被加入過隊列 
             }}} }//遍歷所有連通量void BFSTrave(){for(int u=0;u<n;u++){if(inq[u] == false){BFS(u);}}} //BFS
int main(){Adj[0].push_back(1);Adj[0].push_back(2);Adj[1].push_back(0);Adj[1].push_back(2);Adj[1].push_back(3);Adj[1].push_back(4);Adj[2].push_back(0);Adj[2].push_back(1);Adj[2].push_back(4);Adj[3].push_back(1);Adj[3].push_back(4);Adj[3].push_back(5);Adj[4].push_back(1);Adj[4].push_back(2);Adj[4].push_back(3);Adj[4].push_back(5);Adj[5].push_back(1);Adj[5].push_back(4);BFS(0);return 0;}

?題目練習:PAT?A1076?Forwards on Weibo

#include <stdio.h>
#include <string.h> 
#include <vector>
#include <queue>
#include <iostream> 
using namespace std;const int MAXV = 1010;struct Node
{int id;int layer;};//鄰接表 vector<Node> Adj[MAXV];//是否被加入過隊列 bool inq[MAXV] = {false};//s為起始結點,L為層數上限 int BFS(int s,int L){int numForward = 0;//轉發數queue<Node> q; Node start;//定義起始結點start.id = s;start.layer = 0; q.push(start);inq[start.id] = true;while(!q.empty()){//取出隊首結點 Node topNode = q.front();q.pop();//取出隊首結點的編號 int u = topNode.id;for(int i=0; i < Adj[u].size();i++){Node next = Adj[u][i];next.layer = topNode.layer + 1;//如果next的編號未被加入過隊列,且next的層次不超過上限Lif(inq[next.id] == false && next.layer <= L){q.push(next);inq[next.id] = true;numForward++;//轉發數加1 
             } } } return numForward; } int main(){Node user;//n為人數 L為層數  numFollow為關注的人數  idFollow為關注的人 int n,L,numFollow,idFollow;cin >> n >> L;for(int i=1;i<=n;i++){user.id = i;cin >> numFollow;for(int j=0;j<numFollow;j++){cin >> idFollow;//下標為點,元素為連接的點 
            Adj[idFollow].push_back(user); }} //numQuery為查詢的個數 int numQuery,s; cin >> numQuery;for(int i=0;i<numQuery;i++){memset(inq,false,sizeof(inq));cin >> s;int numForward = BFS(s,L);cout << numForward << endl;} } 

?

?