数据结构-图【深度优先遍历递归与非递归&C++代码实现】

    关于图的深度优先遍历（Depth-First-Search，DFS）算法，具体原理在此不做阐述，仅是结合算法原理给出C++的代码实现。

• 0 关于基本类的定义
• 1 DFS递归算法实现
• 2 DFS非递归算法实现
• 3 代码测试
• 4 链式栈类-linkedStack

    关于顶点表VNode、边表ArcNode、邻接表ALGraph的定义，同上篇文章中给出的；使用到的链式栈类linkedStack的定义，源代码附在文末。此处仅对邻接表类ALGraph有所修改，对应类的定义现如下。

    直接上代码。

	void DFSTraverse_recursion(){
		int i;
		//初始化访问标记数组
		this->resetVisited();
		//默认从第1个顶点开始遍历
		std::cout<<"[ ";
		for (i=0;iverticeNum;i++)
			if (!this->visited[i])
				DFS_Recursion(i);
		std::cout<<" ]"<visit(vertexIndex);
		//2-修改访问标记数组
		this->visited[vertexIndex]=1;
		//3-遍历邻接顶点
		int curIndex=-1;
		VNode pNode=this->vertices[vertexIndex];
		for (ArcNode* pArc=pNode.getFirstArc();pArc!=NULL;pArc=pArc->getNextArc())
		{
			curIndex=this->getVNode(pArc->getAdjvex());
			if (!this->visited[curIndex])
				this->DFS_Recursion(curIndex);//递归访问顶点
		}
	}

    直接上代码。

	void DFSTraverse(VNode* pNode){
		VertexType data=pNode->getData();//获取结点信息
		VertexType curData=' ';
		int vertexIndex=this->getVNode(data);//获取顶点下标
		int curIndex=-1;
		ArcNode* pArc=NULL;
		if (pNode==NULL)
			return;	
		//从顶点v开始深度优先遍历-依次遍历一个连通分量的所有结点
		if (!this->S->isEmpty())
			this->S->resetlinkedStack();//若不为空-重置辅助栈为空
		//重置访问标记数组
		this->resetVisited();
		//结点进栈
		this->S->PushlinkedStack(data);
		//标记为已访问
		this->visited[vertexIndex]=1;
		//循环访问其它未被访问的顶点
		std::cout<<"[ ";
		while (!this->S->isEmpty())
		{
			//出栈操作
			this->S->PoplinkedStack(data);
			//更新顶点下标
			vertexIndex=this->getVNode(data);
			//访问当前结点
			this->visit(vertexIndex);
			//访问边表上的其它未被访问过的顶点
			pArc=this->vertices[vertexIndex].getFirstArc();
			while (pArc!=NULL)
			{
				curIndex=this->getVNode(pArc->getAdjvex());//获取边表上被访问的当前顶点下标
				curData=this->vertices[curIndex].getData();//获取当前顶点信息
				if (!this->visited[curIndex])
				{
					this->S->PushlinkedStack(curData);//进栈
					this->visited[curIndex]=1;//置为已访问状态
				}//if
				pArc=pArc->getNextArc();
			}//while
		}//while
		std::cout<<" ]"< 
3 代码测试 
#include 
#include "ALGraph.h"
using namespace std;

void setMinDis(){
	//边表
	ArcNode* aFirstArc=new ArcNode('B',new ArcNode('E',NULL));
	ArcNode* bFirstArc=new ArcNode('A',new ArcNode('C',new ArcNode('D',new ArcNode('E',NULL))));
	ArcNode* cFirstArc=new ArcNode('B',new ArcNode('D',NULL));
	ArcNode* dFirstArc=new ArcNode('B',new ArcNode('C',new ArcNode('E',NULL)));
	ArcNode* eFirstArc=new ArcNode('A',new ArcNode('B',new ArcNode('D',NULL)));

	//顶点表结点
	VNode *A=new VNode('A',aFirstArc);
	VNode *B=new VNode('B',bFirstArc);
	VNode *C=new VNode('C',cFirstArc);
	VNode *D=new VNode('D',dFirstArc);
	VNode *E=new VNode('E',eFirstArc);

	//将顶点表添加到邻接表实例的数组中
	ALGraph* graph=new ALGraph;
	//std::cout<getAdjList())/sizeof(VNode)<addVNode(0,A);
	graph->addVNode(1,B);
	graph->addVNode(2,C);
	graph->addVNode(3,D);
	graph->addVNode(4,E);

	//基本信息
	std::cout<<"顶点数目-"<getVerticeNum()<<"t边的条数-"<getArcNum()<BFSTraverse();
	
	//深度优先遍历
	std::cout<<"深度优先遍历-递归:[默认将顶点表中的第一个顶点A作为起始点]"<DFSTraverse_recursion();
	std::cout<<"深度优先遍历-非递归:[默认将顶点表中的第一个顶点A作为起始点]"<DFSTraverse(A);
}

int main(int argc,char** argv){
	//setGraph();
	setMinDis();
	return 0;
}
 
 
4 链式栈类-linkedStack 
    链式栈linkedStack也是之前自己封装的一个类，源代码如下。
 
//#include "linkNode.h"


template 
class linkedStack{
public:
	//inner class
	template 
	class linkNode{
	public:
		//setter
		void setData(T data){
			this->data=data;
		}
		void setNext(linkNode* next){
			this->next=next;
		}
		//getter
		T getData(){
			return this->data;
		}

		linkNode* getNext(){
			return this->next;
		}
		//constructor
		linkNode(){
			this->setData(0);
			this->setNext(NULL);
		}
		linkNode(T data,linkNode* next){
			this->setData(0);
			this->setNext(NULL);
		}

	protected:

	private:
		T data;//数据域
		linkNode* next;//指针域
	};

	//setter
	void setHeader(linkNode* header){
		if (this->header!=NULL)
		{
			this->header=header;
			return;
		}
		std::cout<<"do setHeader Failed!"<* getHeader(){
		return this->header;
	}
	//constructor
	linkedStack(){
		this->header=new linkNode;
	}

	//methods
	
	bool isEmpty(){
		return this->header->getNext()==NULL?true:false;
	}

	
	linkNode* getTop(){
		return this->header->getNext();
	}

	
	bool PushlinkedStack(T e){
		//创建新的结点
		linkNode* newNode=NULL;
		newNode=new linkNode;
		newNode->setData(e);
		//入栈操作
		newNode->setNext(this->header->getNext());
		this->header->setNext(newNode);
		return true;
	}

	
	bool PoplinkedStack(T& e){
		linkNode* p=NULL;//辅助指针
		//获取被删除的结点
		p=this->header->getNext();
		//出栈
		this->header->setNext(p->getNext());
		//销毁结点
		if (p!=NULL)
		{
			e=p->getData();
			delete p;
		}
		return true;
	}

	
	void resetlinkedStack(){
		linkNode *p=NULL;
		if (this->isEmpty()) return;
		//辅助指针
		//遍历所有结点-删除结点
		while ((p=this->header->getNext())!=NULL)
		{
			this->header->setNext(p->getNext());
			std::cout<getData()<* header;//头结点
};