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