非递归深度遍历.doc

非递归深度遍历.txt9母爱是一滴甘露，亲吻干涸的泥土，它用细雨的温情，用钻石的坚毅，期待着闪着碎光的泥土的肥沃；母爱不是人生中的一个凝固点，而是一条流动的河，这条河造就了我们生命中美丽的情感之景。#ifndef ALGraph_CPP #define ALGraph_CPP #include ALGraph.h templateclass T ALGraphT::ALGraph(vectorT vs) { m_N = vs.size(); m_Data.resize(m_N); for(int i=0; im_N; i++) { m_Data[i].data=vs[i]; m_Data[i].firstarc=NULL; } } templateclass T ALGraphT::~ALGraph() { for(int i=0; im_N; i++) Clear(m_Data[i].firstarc); } templateclass T void ALGraphT::Clear(ArcNode *head) { while(head) { ArcNode *p=head-nextarc; delete head; head=p; } } templateclass T void ALGraphT::Append(vectorEdge es) { for(int i=0; ies.size(); i++) { int v1=es[i].v1, v2=es[i].v2; ArcNode *p=new ArcNode; p-adjvex=v2; p-weight=es[i].weight; p-nextarc=m_Data[v1].firstarc; m_Data[v1].firstarc = p; } } templateclass T void ALGraphT::Output() { for(int i=0; im_N; i++) { coutm_Data[i].data: ; for(ArcNode *p=m_Data[i].firstarc; p; p=p-nextarc) couti,p-adjvex:p-weight\t; coutendl; } coutendl; } templateclass T vectorT ALGraphT::DFSTraverse() { vectorT vs,vs1; vectorbool visited(m_N,false); for(int v=0; vm_N; v++) if(visited[v]==false) { vs1.clear(); DoDFSTraverse(v,visited,vs1); vs.insert(vs.end(),vs1.begin(),vs1.end()); } return vs; } templateclass T void ALGraphT::DoDFSTraverse(int v,vectorbool visited,vectorT vs) { stackStatus S; // 约定每个顶点被访问之后，再进栈 vs.push_back(m_Data[v].data); visited[v]=true; Status s1={v,m_Data[v].firstarc}; S.push(s1); while( !S.empty() ) { Status s=S.top(); // s是栈顶状态的引用 // 寻找v的下一个未访问过的邻接点 for(; s.p; s.p=s.p-nextarc) if(visited[s.p-adjvex]==false) break; if(s.p) { int w=s.p-adjvex; // 顶点w未访问过 vs.push_back(m_Data[w].data); visited[w]=true; Status nexts; nexts.v=w; nexts.p=m_Data[w].firstarc; S.push(nexts); } else S.pop(); // 以v为起点的搜索已经完毕 } } #endif