22.3-6重写DBS,用一个栈来实现递归
只需要将调用过程参数用栈保存即可,分析发现需要保存的数据只有当前的访问节点。
数据仍然使用做22.2-6的图
#include<stack>
#include<iostream>
#include<fstream>
#define V 10
#define MAX (~(1<<(8*sizeof(int)-1)))
using namespace std;
enum Color{WHITE,GRAY,BLACK};
int m[V][V];
Color color[V];
int d[V];
int p[V];
int f[V];
int num;
stack<int> st;
int tim;
//从u开始dfs
void DFS(){
for(int i=0;i<num;i++){
color[i]=WHITE;
p[i]=-1;
}
tim=0;
for(int u=0;u<num;u++){
if(color[u]!=WHITE)continue;
color[u]=GRAY;
tim=tim+1;
d[u]=tim;
st.push(u);
printf("%d-->",u);
while(!st.empty()){
int v=st.top();
bool flag=true;
for(int i=0;i<num;i++){
if(m[v][i]!=0&&color[i]==WHITE){
p[i]=v;
tim++;
color[i]=GRAY;
d[i]=tim;
printf("%d-->",i);
st.push(i); flag=false; break;
}
}
if(flag){
st.pop();
color[v]=BLACK;
tim++;
f[v]=tim;
}
}
}
}
int main()
{
fstream f;
f.open("input22.2-6.txt");
int u,v;
f>>num;
while(f>>u>>v){m[u][v]=m[v][u]=1;}
DFS();
f.close();
system("pause");
return 0;
}