本文章适用于以下人群:
已经理解了深度优先和广度优先的相关概念和思路,但是缺少相关代码和使用的实例,以及不清楚代码的相应内容的原理的作用的人,本文的详细注释的代码以及测试的数据都放在了代码行里面,可自行取用。
深度优先代码较少而且比较简单,所以没有上注释。
代码内容:
#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 */
实例结果: