数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历

àì夳堔傛蜴生んèń 2022-10-25 12:57 197阅读 0赞

![20210131211933949.png][]

> ** C++ 非递归深度优先遍历**

#include <iostream>
    #include <malloc.h>
    #include <stack> 
    using namespace std;
    const int MaxSize=6;//图中最多顶点个数
    typedef string DataType;
    int visited[MaxSize] = {0};//全局数组变量visited初始化 
    class MGraph{
    	public:
    		MGraph();//构造函数 
    		~MGraph(); 
    		void DFTraverse(int v);
    		void BFTraverse(int v);
    	private:
    		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
    		int edge[MaxSize][MaxSize] = {
       {0,34,46,INT_MAX,INT_MAX,19}, 
    								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
    								{46,INT_MAX,0,17,INT_MAX,25},
    								{INT_MAX,INT_MAX,17,0,38,25},
    								{INT_MAX,12,INT_MAX,38,0,26},
    								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
    		int vertexNum=MaxSize,edgeNum=MaxSize;
    }; 
    
    MGraph::MGraph(){
    	
    } 
    
    MGraph::~MGraph(){
    
    } 
    
    void MGraph::DFTraverse(int v){//非递归深度优先遍历 
    	stack<int> DF_stack;
    	DF_stack.push(v);
    	cout<<vertex[DF_stack.top()];
    	visited[v]=1;
    	for(int j=0;j<vertexNum;j++){
    		if( visited[j] == 0 && (edge[v][j]!=INT_MAX && edge[v][j]!=0 )){
    			cout<<vertex[j];
    			visited[j]=1;
    			v = j;
    			DF_stack.push(j); 
    			j=0;
    		}
    		if(j == vertexNum-1 ){
    			DF_stack.pop();
    		}
    	}
    }
    int main(){
    	int i;
    	MGraph MG{};
    	for(i=0;i<MaxSize;i++)
    		visited[i]=0;
    	cout<<"深度优先遍历序列是："<<endl;
    	MG.DFTraverse(0);
    	cout<<endl;
    }

> **实验结果图：**

![20210131211346794.png][]

> ** C++ 递归深度优先遍历**

#include <iostream>
    #include <malloc.h>
    #include <stack> 
    using namespace std;
    const int MaxSize=6;//图中最多顶点个数
    typedef string DataType;
    int visited[MaxSize] = {0};//全局数组变量visited初始化 
    class MGraph{
    	public:
    		MGraph();//构造函数 
    		~MGraph(); 
    		void DFTraverse(int v);
    		void BFTraverse(int v);
    	private:
    		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
    		int edge[MaxSize][MaxSize] = {
       {0,34,46,INT_MAX,INT_MAX,19}, 
    								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
    								{46,INT_MAX,0,17,INT_MAX,25},
    								{INT_MAX,INT_MAX,17,0,38,25},
    								{INT_MAX,12,INT_MAX,38,0,26},
    								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
    		int vertexNum=MaxSize,edgeNum=MaxSize;
    }; 
    
    MGraph::MGraph(){
    	
    } 
    
    MGraph::~MGraph(){
    
    } 
     
    void MGraph::DFTraverse(int v){//深度优先遍历 
    	cout<<vertex[v];
    	visited[v]=1;
    	for(int j=0;j<vertexNum;j++)
    		if(visited[j] == 0 && (edge[v][j]!=INT_MAX && edge[v][j]!=0 ))
    			DFTraverse(j);
    }
    
    int main(){
    	int i;
    	MGraph MG{};
    	for(i=0;i<MaxSize;i++)
    		visited[i]=0;
    	cout<<"深度优先遍历序列是："<<endl;
    	MG.DFTraverse(0);
    	cout<<endl;
    }

> **实验结果图：**

![20210131211041955.png][]

> **C++广度优先遍历**

#include <iostream>
    #include <malloc.h>
    #include <stack> 
    using namespace std;
    const int MaxSize=6;//图中最多顶点个数
    typedef string DataType;
    int visited[MaxSize] = {0};//全局数组变量visited初始化 
    class MGraph{
    	public:
    		MGraph();//构造函数 
    		~MGraph(); 
    		void DFTraverse(int v);
    		void BFTraverse(int v);
    	private:
    		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
    		int edge[MaxSize][MaxSize] = {
       {0,34,46,INT_MAX,INT_MAX,19}, 
    								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
    								{46,INT_MAX,0,17,INT_MAX,25},
    								{INT_MAX,INT_MAX,17,0,38,25},
    								{INT_MAX,12,INT_MAX,38,0,26},
    								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
    		int vertexNum=MaxSize,edgeNum=MaxSize;
    }; 
    
    MGraph::MGraph(){
    	
    } 
    
    MGraph::~MGraph(){
    
    } 
     
    void MGraph::BFTraverse(int v){//广度优先遍历 
    	int w,j,Q[MaxSize];//采用顺序队列
    	int front=-1,rear=-1;//初始化队列
    	cout<<vertex[v];
    	visited[v]=1;
    	Q[++rear]=v;//被访问顶点入队
    	while(front!=rear){
    		w=Q[++front];//将队头元素出队并送到v中
    		for(j=0;j<vertexNum;j++)
    			if((edge[w][j]!=INT_MAX && edge[w][j]!=0 ) && visited[j] == 0){
    				cout<<vertex[j];
    				visited[j] = 1;
    				Q[++rear] = j;
    			} 
    	} 
    }
    
    int main(){
    	int i;
    	MGraph MG{};
    	for(i=0;i<MaxSize;i++)
    		visited[i]=0;
    	cout<<"广度优先遍历序列是："<<endl;
    	MG.BFTraverse(0);
    }

> **实验结果图：**

![20210131211515805.png][]

> ### 我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~ ###
> 
> **如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o**
> 
> **我会定期更新文章，继续为您提供优质文章**

[20210131211933949.png]: /images/20221024/dfbf6267a0d5485785f69b5a604782cb.png
[20210131211346794.png]: /images/20221024/79c80afb200a4c5dba4caf996fc54a95.png
[20210131211041955.png]: /images/20221024/40a3ea6186a2479497b9bb5ff9b7fe25.png
[20210131211515805.png]: /images/20221024/94a1dc9abe4b4620b127eea32252162d.png