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

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


输出使用深度优先算法访问树的顺序;


yuanzhen@ubuntu:~/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

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台