基本思想

1.建立一个队列
2.把初始顶点加入，此后每次取出队首顶点进行访问
3.把从该顶点出发可以到达的，未曾加入过队列的顶点全部加入队列
4.不断取出，直至队列为空结束

遍历实现

1.邻接矩阵实现

const int maxn=100;
const int INF=1000000;//作为无关标志
int G[maxn][maxn];//邻接矩阵:存储两顶点的关系
bool enter[maxn]={false};
int num;

void BFS(int index){
    queue<int> q;
    q.push(index);
    enter[index]=true;
    while(!q.empty()){
        index=q.front();
        q.pop();
        for(int i=0;i<num;i++){
        if(G[index][i]!=INF&&enter[i]==false)
            q.push(i);
            enter[i]=true;
        }
    }
}
void BFStrave(){
    for(int i=0;i<num;i++){
        if(enter[i]==false)
        BFS(i);
    }
}

2.邻接表实现

#include <queue>
#include <vector>
using namespace std;
const int maxn=100;
bool enter[maxn]={false};
vector<int> V[maxn];//V[i].push(j)：将顶点j存入V[i]中，则V[i][size]才是顶点编号
int num;

void BFS(int index){//遍历顶点index的邻接表
    queue<int> q;
    q.push(index);
    enter[index]=true;
    while(!q.empty()){
        index=q.front();
        q.pop();
    for(int i=0;i<V[index].size();i++){
        //与index相连的顶点
        int node=V[index][i];
        if(enter[node]!=false){
            q.push(node);
            enter[node]=true;
        }
       }
    }
}
void BFStrave(){
    for(int i=0;i<num;i++){
        if(enter[i]==false)
        BFS(i);
    }
}

应用

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn=100;
bool enter[maxn]={false};
int num,limit,follownum;
int inNum;
struct user{
    int n;//编号
    int layer;
}u;
vector<user> users[maxn];

void BFS(int index){
    inNum=0;//记录访问次数
    queue<user> q;
    u.n=index;
    u.layer=0;
    q.push(u);
    enter[index]=true;
    while(!q.empty()){
        user front=q.front();
        q.pop();
        for(int i=0;i<users[front.n].size();i++){
            user node=users[front.n][i];
            node.layer=front.layer+1;
            if(enter[node.n]==false&&node.layer<=limit)
            {
                q.push(node);
                inNum++;
                enter[node.n]=true;
            }
        }
    }
}
int main(){
    int tempt=0,inquireNum,inquire,result=0;
    cin>>num>>limit;
    for(int i=1;i<=num;i++){//从1开始编号
        u.n=i;
        cin>>follownum;
        for(int j=0;j<follownum;j++){
            cin>>tempt;
            //存储信息的被关注者，即接收者
            users[tempt].push_back(u);
        }
    }
    cin>>inquireNum;
    for(int i=0;i<inquireNum;i++){
        cin>>inquire;
        BFS(inquire);
        //恢复enter，开始第二个数的查询
        memset(enter,false,sizeof(enter));
        cout<<inNum<<endl;
    }
    return 0;
}