# c++ 深度优先算法输出树的访问顺序

2017-01-12 09:54:01来源:oschina作者:元禛慎独人点击

[email protected]:~/C_script\$ cat dfs_two.cpp #include #include #include

using std::cout; using std::endl; using std::vector;

vector > vec; vector book(13,0); vector result(13,0);

void show(vector > avec) { vector >::const_iterator cit; vector::const_iterator it;

for(cit=avec.begin(); cit!=avec.end();++cit) { vector ivec=(*cit); for(it=ivec.begin();it!=ivec.end();++it) {cout << *it << " "; } cout << endl; } }

vector > init() { int arr[11][2]={{1,2},{1,7},{1,8},{2,3},{2,6},{3,4},{3,5},{8,9},{8,12},{9,10},{9,11}};

vector >avec(13, vector(13,0)); for(int i=1;i<13;++i)avec[i][0]=i;

for(int j=1;j<13;++j)avec[0][j]=j;

for(int k=0;k<11;++k) { int x=arr[k][0]; int y=arr[k][1];

avec[x][y]=1; avec[y][x]=1; } return avec; }

void dfs(int node, int step) { cout << node << endl; for(int i=1;i<13;++i) { if(vec[node][i]==1 && book[i]==0) {book[i]=1;dfs(i, step+1);book[i]=0; } } }

int main(int argc, char** argv) { vec=init(); show(vec); book[1]=1; dfs(1,1); } ##################################

0 1 2 3 4 5 6 7 8 9 10 11 12 1 0 1 0 0 0 0 1 1 0 0 0 0 2 1 0 1 0 0 1 0 0 0 0 0 0 3 0 1 0 1 1 0 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 0 0 0 5 0 0 1 0 0 0 0 0 0 0 0 0 6 0 1 0 0 0 0 0 0 0 0 0 0 7 1 0 0 0 0 0 0 0 0 0 0 0 8 1 0 0 0 0 0 0 0 1 0 0 1 9 0 0 0 0 0 0 0 1 0 1 1 0 10 0 0 0 0 0 0 0 0 1 0 0 0 11 0 0 0 0 0 0 0 0 1 0 0 0 12 0 0 0 0 0 0 0 1 0 0 0 0 ------------------------------ 1 2 3 4 5 6 7 8 9 10 11 12