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

using namespace std;

const int n=6;
vector< vector > g;
vector visited;
queue 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 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 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 &array){
stack 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 array;
Path(w,array);
for(int i=0;i ";
    }
}

}

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

void init(){
for(int i=0;i g[i]=vector();
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 g.push_back( vector() );
visited.push_back(false);
from[i]=-1;
old[i]=-1;
}
//连接一个五角星
setUp();
cout<<" 0 1 2 3 4 5"< for(int i=0;i cout< for(int j=0;j cout< }
cout< }
//1.查找两个点是否连通
bfs(1);
cout<

init();
setUp();
bfs(0);
cout<
}