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

/
深度优先遍历
邻接表实现
作者:纸航
邮箱:1184191599@qq.com
/

using namespace std;

const int n=6;
int m=0;
vector< vector > g;
vector visited;
int ccount;
int from[n];
int id[n];

void dfs(int v){
visited[v]=true;
id[v]=ccount; //用联通分量来标记,可以达到判断两个点是否连通的效果
for(int i=0;i if(!visited[g[v][i]]){ //如果没有遍历过就开始遍历
from[g[v][i]]=v; //记录遍历的前一个点
dfs(g[v][i]);//递归
}
}
}

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);
}
m++;
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 cout< if(i==array.size()-1){
cout< }
else {
cout<<" -> ";
}
}
}

bool isCount(int v,int w){
return id[v]==id[w];
}

bool l(int v,int w){
return id[v] == id[w];
}

void init(){
//初始化
ccount=0;
for(int i=0;i visited[i]=false;
g[i]=vector();
from[i]=-1;
id[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(){
//初始化
ccount=0;
for(int i=0;i visited.push_back(false);
from[i]=-1;
g.push_back( vector() );
id[i]=-1;
}

setUp();
//1.查找两个点是否连通
for(int i=0;i
}