C/C++算法(图的广度优先遍历)

include<iostream>

include<vector>

include<queue>

include<stack>

using namespace std;

const int n=6;
vector< vector<int> > g;
vector<bool> visited;
queue<int> q;
int ccount;
int from[n];
int old[n];

void bfs(int s){
q.push(s);
visited[s]=true;
old[s]=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<g[v].size();i++){
if(!visited[g[v][i]]){
q.push(g[v][i]);
visited[g[v][i]]=true;
from[g[v][i]]=v;
old[g[v][i]]=old[v]+1;
}
}
}
}

bool isLian(int v,int w){ //判断是否连接
for(int i=0;i<g[v].size();i++){
if(g[v][i]==w){
return true;
}
}
return false;
}

int Marry(int v,int w,bool hasQuan){ //加一条边
if(isLian(v,w)){
return 0;
}
g[v].push_back(w);
if(!hasQuan){
g[w].push_back(v);
}
w++;
return 0;
}

bool hasPath(int v){

return visited[v];

}

void Path(int w,vector<int> &array){
stack<int> s;
int p=w;
while(p != -1){
s.push(p);
p=from[p];
}
array.clear();
while(!s.empty()){
array.push_back(s.top());
s.pop();
}

}

void showPath(int w){

vector<int> array;
Path(w,array);
for(int i=0;i<array.size();i++){
    cout<<array[i];
    if(i==array.size()-1){
        cout<<endl;
    }
    else{
        cout<<" -> ";
    }
}

}

int l(int v){
return old[v];
}

void init(){
for(int i=0;i<n;i++){ //初始化
g[i]=vector<int>();
visited[i]=false;
from[i]=-1;
old[i]=-1;
}
}

void setUp(){
Marry(1,2,true);
Marry(1,3,true);
Marry(2,4,true);
Marry(4,1,true);
Marry(3,4,true);
Marry(3,5,true);
Marry(4,0,true);
Marry(5,0,false);
}

int main(){
for(int i=0;i<n;i++){ //初始化
g.push_back( vector<int>() );
visited.push_back(false);
from[i]=-1;
old[i]=-1;
}
//连接一个五角星
setUp();
cout<<" 0 1 2 3 4 5"<<endl;
for(int i=0;i<n;i++){
cout<<i<<": ";
for(int j=0;j<g[i].size();j++){
cout<<g[i][j]<<" ";
}
cout<<endl;
}
//1.查找两个点是否连通
bfs(1);
cout<<l(0)<<endl;

init();
setUp();
bfs(0);
cout<<l(5)<<endl;

//2.找到两个点之间的一条路径
init();
setUp();
bfs(2);
showPath(5);

//3.查询一个图的连通分量
init();
setUp();
for(int i=0;i<n;i++){
    if(!visited[i]){
        bfs(i);
        ccount++;           
    }
}
cout<<ccount<<endl;
//bfs(1);   
//showPath(0);
return 0;

}