图的深度优先遍历和广度优先遍历代码实现

本文主要是介绍图的深度优先遍历和广度优先遍历代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>using namespace std;typedef char TypeData; /* 数据类型 */
#define MAXVEX 100   /* 最大顶点数 */
#define INFINITY 65535   /* 用65535代表 正无穷 *//* 存储采用邻接矩阵 */
typedef struct stGraph
{TypeData vexs[MAXVEX];    /* 定点表 */int arc[MAXVEX][MAXVEX];  /* 邻接矩阵，可看作边表 */int numVertexes, numEdges;/* 图中当前的顶点数和边数 */
}MGraph;/* 建立无向网图邻接矩阵表示 */
void createMGraph(MGraph* G);/* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
void DFS(MGraph* G, int i);
void DFSTraverse(MGraph* G);/* 邻接矩阵的广度优先遍历 */
void BFSTraverse(MGraph* G);/* 建立无向网图邻接矩阵表示 */
void createMGraph(MGraph* G)
{int i = 0, j  = 0, k = 0, w = 0;cout << "请输入定点数和边数: ";cin >> G->numVertexes >> G->numEdges;/* 读入定点信息，建立定点表 */cout << "请输入图的节点" << endl;for(i = 0; i < G->numVertexes; i++){cin >> G->vexs[i];}/* 初始化邻接矩阵 */for(i = 0; i < G->numVertexes; i++){for(j = 0; j < G->numVertexes; j++){G->arc[i][j] = INFINITY;}}/* 读入numEdges边信息 */for(k = 0; k < G->numEdges; k++){cout << "输入边(vi,vj)上的下标，i,j和权值w" << endl;cin >> i >> j >> w;G->arc[i][j] = w;/* 因为是无向图，矩阵对称 */G->arc[j][i] = w;}
}/* 邻接矩阵的深度优先遍历和广度优先遍历所用辅助数组记录图中的节点是否被访问过 */
int visited[MAXVEX] = {0};/* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
void DFS(MGraph* G, int i)
{int j = 0;visited[i] = 1;/* 打印定点的信息 */cout << G->vexs[i] << " ";for(j = 0; j < G->numVertexes; j++){if(G->arc[i][j] != 65535 && visited[j] == 0 ){DFS(G,j);}}
}void DFSTraverse(MGraph* G)
{int i = 0;/* 把每一个定点都设为未访问过 */for(i = 0; i < G->numVertexes; i++){visited[i] = 0;}/* 对未访问过的定点调用DFS */for(i = 0; i < G->numVertexes; i++){if(visited[i] == 0){DFS(G,i);}}
}/* 邻接矩阵的广度优先遍历 */
void BFSTraverse(MGraph* G)
{int i = 0, j = 0;queue<int> myqueue;/* 初始化，把每一个定点都设为未访问过 */for(i = 0; i < G->numVertexes; i++){visited[i] = 0;}/* 对每一个定点做循环 */for(i = 0; i < G->numVertexes; i++){/* 如果节点没有被访问过 */if(visited[i] == 0){/* 该节点设置为已经被访问 */visited[i] = 1;/* 打印出该节点,并把该节点入队列 */cout << G->vexs[i] << " ";myqueue.push(i);/* 若当前的队列不为空 */while(!myqueue.empty()){i = myqueue.front();myqueue.pop();for(j = 0; j < G->numVertexes; j++){/* 判断其他定点若与当前的定点存在边且未访问过 */if(G->arc[i][j] != 65536 && visited[j] == 0){visited[j] = 1;cout << G->vexs[j] << " ";myqueue.push(j);}}}}}}int main(void)
{MGraph* pGraph = new MGraph;int i = 0, j = 0;/* 创建一个图 */createMGraph(pGraph);/* 深度优先遍历 *///  DFSTraverse(pGraph);/* 广度优先遍历 */BFSTraverse(pGraph);delete pGraph;return 0;
}

这篇关于图的深度优先遍历和广度优先遍历代码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---