非递归深度遍历

#define ALGraph_CPP

#include  "ALGraph.h"

template

ALGraph::ALGraph(vector vs)

{ m_N = vs.size();

  m_Data.resize(m_N);

for(int i=0; i  { m_Data[i].data=vs[i];

    m_Data[i].firstarc=NULL;

  }

}

template

ALGraph::~ALGraph()

{ for(int i=0; i    Clear(m_Data[i].firstarc);

}  

template

void ALGraph::Clear(ArcNode *head)

{ while(head)

{ ArcNode *p=head->nextarc;

    delete head; head=p;

  }

}

template

void ALGraph::Append(vector &es)

{ for(int i=0; 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;

  }

}

template

void ALGraph::Output()

{ for(int i=0; i { cout< for(ArcNode *p=m_Data[i].firstarc; p; p=p->nextarc)

cout< cout<  }

cout<} 

template

vector ALGraph::DFSTraverse()

{ vector vs,vs1;

vector visited(m_N,false);

for(int v=0; v    if(visited[v]==false)       

    { vs1.clear();

      DoDFSTraverse(v,visited,vs1);

      vs.insert(vs.end(),vs1.begin(),vs1.end());

    }

  return vs;

}  

template

void ALGraph::DoDFSTraverse(int v,vector& visited,vector& vs)

{ stack 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