数据结构——深度优先遍历、广度优先遍历 C++实现（含实例代码以及详细注解以及测试数据）

本文主要是介绍数据结构——深度优先遍历、广度优先遍历 C++实现（含实例代码以及详细注解以及测试数据），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文章适用于以下人群：

已经理解了深度优先和广度优先的相关概念和思路，但是缺少相关代码和使用的实例，以及不清楚代码的相应内容的原理的作用的人，本文的详细注释的代码以及测试的数据都放在了代码行里面，可自行取用。

深度优先代码较少而且比较简单，所以没有上注释。

代码内容：

#include <iostream>
using namespace std;

const int MaxSize = 10;           //图中最多顶点个数
int visited[MaxSize]={0};

template <class DataType>
class MGraph
{
public:
	MGraph(DataType a[ ], int n, int e);    //构造函数，建立具有n个顶点e条边的图
	~MGraph( ) { }                     //析构函数为空
	void DFSTraverse(int v);              //深度优先遍历图
	void BFSTraverse(int v);               //广度优先遍历图
private:
    DataType vertex[MaxSize];          //存放图中顶点的数组
    int arc[MaxSize][MaxSize];          //存放图中边的数组
    int vertexNum, arcNum;             //图的顶点数和边数
};

补充1//
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e){
	
	for(int i=0;i<vertexNum;i++){ //重置访问痕迹 
		visited[i]=0;
	}
	
	int i,j,k;
	vertexNum = n;
	arcNum = e;
	for(i = 0;i < vertexNum; i++){
		vertex[i] = a[i];
	}
	for( j = 0; j < vertexNum; j++){
		for(k = 0; k < vertexNum;k++){
			arc[j][k] = 0;
		}
	}
	for(k = 0;k < arcNum; k++){
		cout<<"请输入边的两个顶点的编号：";
		cin>>i>>j;
		arc[i][j] = 1;
		arc[j][i] = 1;
	}
//	for( j = 0; j < vertexNum; j++){
//		
//		for(k = 0; k < vertexNum;k++){
//			cout<<arc[j][k];
//		}
//		cout<<endl;
//	}
} 

//深度优先 
template <class DataType>
void MGraph<DataType>::DFSTraverse(int v){
	cout<<vertex[v];
	visited[v] = 1;
	for(int i=0;i<vertexNum;i++){
		if(arc[v][i]==1&&visited[i]==0){
			DFSTraverse(i);
		}
	}
}

//广度优先
template <class DataType>
void MGraph<DataType>::BFSTraverse(int v){
	
	for(int i=0;i<vertexNum;i++){ //重置访问痕迹 
		visited[i]=0;
	} 
	
	int w, j, Q[MaxSize]; 		//Q作为队列存储访问的点以及其连接的点 
	int front = -1, rear = -1;	//初始化头指针和尾指针 
	cout<<vertex[v];			//输出输入v的对应字符 
	visited[v] = 1;				//把V设定为访问过 
	Q[++rear] = v;				//将访问过的v入队列 
	while(front != rear){  		//判定栈是否为空，如果为空就结束 
		w = Q[++front];			//w暂存Q栈读取出来的数 
		for(j = 0; j < vertexNum; j++){			//循环访问所有的数字，看是否与w连接但没有被访问过 
			if(arc[w][j]==1&&visited[j]==0){ 	//如果与w连接但是没有被访问过的话 
				cout<<vertex[j];				//就输出这个数字对应的字符 
				visited[j] = 1;					//并且将这个数字设置为访问过 
				Q[++rear] = j;					//再将这个字符入栈Q 
			}
		}										//循环完毕当前的w的字符，所有w对应连接的字符都被访问并且入队列完毕 
	}											//继续循环，直到所有的队列里面的数字被访问完毕 
}
//

int main( )
{
	char ch[]={'A','B','C','D','E','F'};
	MGraph<char> MG(ch, 6, 6);
补充2//
	cout<<"深度优先遍历序列是："; 
	MG.DFSTraverse(0); 
	cout<<endl;
	cout<<"广度优先遍历序列是："; 
	MG.BFSTraverse(0); 
//
}

/*
测试数据 
0 1
0 2
0 5
1 2
1 4
2 3

*/

实例结果：

这篇关于数据结构——深度优先遍历、广度优先遍历 C++实现（含实例代码以及详细注解以及测试数据）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！