功名半纸，风雪千山
不得不说八个字，真的是充满佛性
文章目录- 前言
- 一、深度优先遍历(DFS)
- 思想
- 深度优先(邻接矩阵)
- 效果截图
- 深度优先(邻接表)
- 运行截图
- 二、广度优先(BFS)
- 思想
- 广度优先(邻接矩阵)
- 运行截图
- 深度优先(邻接表)
- 运行截图
- 可执行代码汇总
前言
提示：以下是本篇文章正文内容，下面案例可供参考
上一篇我们写过创建一个图的常用的三种方式，也写了对应的打印方式，第一希望读者自己打一遍，因为你都不知道你自己怎么放的数据，你又和谈操作呢？，脑子中最起码要有它怎么放的，这里同样附上链接，但是我们打印却只是检查存储是否正确，今天我们就来唠唠关于图的遍历的那些事，之前树那一个章节的时候 我们就说过，其实三种遍历方式也就是深度优先，层序遍历也就是广度遍历 这里图也是分为广度和深度
其实思想就是一直往下找若是与当前结点邻接的顶点都被遍历过了，则返回此结点的上一个顶点 继续检查，因为要检查所以我们需要另外再定义一个数组，来判断此时的点 是否遍历过，直到所有返回到根，并且根的所有顶点也被访问过，不知道你有没有听懂，这里我们使用一个图来讲解一下 本来想画图的 但是相当太丑了，还是使用word来写了
基于上图 最后的遍历顺序就是ACBED 有人可能会问为什么在图的讲解中使用的是树，就遍历来说没有区别，思路都是一样的，至于这里为什么使用使用这个图 给你一点提示 “凯佐苦喔尼,喔类哇纳鲁” 真中二，哈哈哈，收… 下面写出代码
解析放在代码中了
void DFS(AMGraph G,int i){//给一个结点给一个图
//我们来看结点i的所有关联点从中找到一个未遍历的
//这里使用的是邻接表 所以它的邻接点就是数组的行
for(int j=0;j
if(G.arcs[i][j]!=0&&visited[j]==false){//i结点与j结点存在边 并且j结点没有被访问过
visited[j]=true;
cout<
for(int i=0;i//因为有可能是非连通图
if(visited[i]==false){//若是没有遍历则遍历
visited[i]=true;
cout<
效果截图
深度优先(邻接表)
邻接表的深度需要绕一点点弯 但是思想与邻接矩阵是一样的 第一个我们启动的时候传入的是第一个图的第一个顶点 我们要找到第一个点邻接的点cur->adjvex 判断这些邻接中那些没有被访问过，我们就深入，这个时候其实就需要脑子中有递归的执行方式 而不是像一些‘大神’说的递归简单的理解成将问题变小处理小问题就行
void DFSChart(AdjoinChart G,int i){//从顶点i连接的点中选择一个没有被遍历过的 然后深入
ArcNode* cur=G.vertices[i].firstarc;
while(cur){
if(visited[cur->adjvex]==false){
visited[cur->adjvex]=true;
cout<adjvex].data<<" ";
DFSChart(G,cur->adjvex);
}
cur=cur->nextarc;
}
}
//深度优先遍历(邻接表)
void DFSTrevelChart(AdjoinChart G){
for(int i=0;i//因为有可能是非连通图
if(visited[i]==false){//若是没有遍历则遍历
visited[i]=true;
cout<
运行截图
因为是无向图 输入的时候也就需要AC CA 各输入一次 边的个数也就变成了两倍
二、广度优先(BFS)
思想
这里对上述的图进行一波修改 其实与树中的层序遍历有点类似 所以这里依然是使用的队列来进行的操作 所以这个时候可能有人问了 所以上面的深度优先可以使用栈？这里认为是可以的，而且应该是前序的方式，不知道大家是否记得我们写过树的前序遍历 而且不止一种方式
广度优先(邻接矩阵)
这里我第一次写也写错了 只要是一直将他类比成树种 但这里使用的是数组 我刚开始的时候就是没有确定队首元素的位置 调试的时候才发现的，还有就是要注意第一次来到一个
//从i点开始进行广度
void BFSAdjoin(AMGraph G,int i){
queue Q;
cout<
char first=Q.front();
int h=0;while(first!=G.vexs[h++]);//来寻找队列中第一个字母在顶点表终点位置
//int size=Q.size();//就跟前面写过的层序遍历一样 这里也分层输出 明显一点
for(int j=0;j
if(G.arcs[h-1][j]!=0&&visited[j]==false){
cout<
for(int i=0;i//为了避免非连通图的情况
if(visited[i]==false)BFSAdjoin(G,i);
}
}
运行截图
深度优先(邻接表)
//广义邻接表
void BFSCharst(AdjoinChart G,int i){//其实跟上面是一样的 就是对数据的操控
queue Q;
cout<
VNode first=Q.front();
//此时我们要找到i的邻接点 并且没有被访问过的
ArcNode* cur=first.firstarc;
while(cur){
if(visited[cur->adjvex]==false){
visited[cur->adjvex]=true;
cout<<"将"<adjvex].data<<"放入队列"<adjvex].data<<" ";
Q.push(G.vertices[cur->adjvex]);
}
cur=cur->nextarc;
}
Q.pop();
}
}
//广义优先(邻接表)
void BFSTravelChart(AdjoinChart G){
for(int i=0;i//为了避免非连通图的情况
if(visited[i]==false)BFSCharst(G,i);
}
}
运行截图
因为邻接表的插入是头插入，所以也就导致不一样的输入方式 就有不一样的运行结果 但是一层一层还是不会变得 因为是无向图，所以输入的个数要是正反两个方向都要输入
可执行代码汇总
#include
using namespace std;
#define MaxInt 32767 //表示极大值∞ 其实就是一种无穷标志
#define MVNum 100 //表示最大顶点数
typedef char VerTexType;//假设顶点的数据结构类型为char
typedef int ArcType;//假设权值类型为整形
//下面的是邻接矩阵的
typedef struct{
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum;//图的当前顶点数
int arcnum;//图的当前边数
}AMGraph;
//需要判读此时点是否遍历过 所以需要一个数组来与点对应
bool visited[MVNum]={false};
//下面的结构体是邻接表的
typedef struct ArcNode{//边结构
int adjvex;//该边所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条边的指针
int info; //和边相关的信息如权重等 若是没有权值也可以省略 省略之后就可以于点结构相统一
}ArcNode;
typedef struct VNode{//顶点结构
VerTexType data;
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode;
//相当于多个链表 将首结点存放于一个数组中 就像单链表中存放长度一样 这里存放的是点与边的个数
typedef struct AdjoinChart{//邻接表
VNode vertices[MVNum];//因为顶点中已经存在边的信息了 也就不需要在添加了
int vexnum;//图当前的顶点数
int arcnum;//图当前的边数
}AdjoinChart;
//打印邻接矩阵
void PrintAMG(AMGraph G){
cout<<" "<<" ";
for(int i=0;i
cout<
cout<
cout<
cout<<"请输入顶点数和边数"<>G.vexnum>>G.arcnum;
cout<<"请输入各个顶点名称"<
cin>>G.vexs[i];
}
for(int h=0;h
char vex1;char vex2;
cout<<"请输入弧的两个顶点"<>vex1>>vex2;
//首先来看是否存在这两个顶点 若是存在则找到这两个点对应的下标
// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
int i=0;while(G.vexs[i++]!=vex1);
int j=0;while(G.vexs[j++]!=vex2);
if(i>G.vexnum||j>G.vexnum){//没有找到
cout<<"你输入的结点值不正确"<
cout<<"请输入此边对应的权重"<>G.arcs[i-1][j-1];
G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
}
}
PrintAMG(G);
}
//打印邻接表 每打印一个顶点 需要打印出相对应的链表
void PrintAdjoinChart(AdjoinChart G){
for(int i=0;i
ArcNode* cur=G.vertices[i].firstarc;
while(cur){
cout<"<adjvex].data<<" ";
cur=cur->nextarc;
}
cout<
cout<<"请输入顶点数以及边的个数"<>G.vexnum>>G.arcnum;
cout<<"请输入顶点名称"<
cin>>G.vertices[i].data;
}
//输入一个边有点类似于单链表的插入
for(int h=0;h
cout<<"请一个弧的两个边，类如从A指向B则 输入A B"<>vex1>>vex2;
//依然需要判断输入的结点是否存在;
int i=0;while(G.vertices[i++].data!=vex1);
int j=0;while(G.vertices[j++].data!=vex2);
if(i>G.vexnum||j>G.vexnum){
cout<<"你输入的位置不正确"<//这里使用头插插入一个弧
ArcNode* NewAcr=(ArcNode*)malloc(sizeof(ArcNode));
NewAcr->nextarc=G.vertices[i-1].firstarc;
G.vertices[i-1].firstarc=NewAcr;
cout<<"请输入此边对应的权值"<>NewAcr->info;
NewAcr->adjvex=j-1;
}
}
PrintAdjoinChart(G);
}
//深入优先邻接矩阵
void DFSAdjoin(AMGraph G,int i){//给一个结点给一个图
//我们来看结点i的所有关联点从中找到一个未遍历的
//这里使用的是邻接表 所以它的邻接点就是数组的行
for(int j=0;j
if(G.arcs[i][j]!=0&&visited[j]==false){//i结点与j结点存在边 并且j结点没有被访问过
visited[j]=true;
cout<
for(int i=0;i//因为有可能是非连通图
if(visited[i]==false){//若是没有遍历则遍历
visited[i]=true;
cout<
queue Q;
cout<
char first=Q.front();
int h=0;while(first!=G.vexs[h++]);//来寻找队列中第一个字母在顶点表终点位置
//int size=Q.size();//就跟前面写过的层序遍历一样 这里也分层输出 明显一点
for(int j=0;j
if(G.arcs[h-1][j]!=0&&visited[j]==false){
cout<
for(int i=0;i//为了避免非连通图的情况
if(visited[i]==false)BFSAdjoin(G,i);
}
}
//广义邻接表
void BFSCharst(AdjoinChart G,int i){//其实跟上面是一样的 就是对数据的操控
queue Q;
cout<
VNode first=Q.front();
//此时我们要找到i的邻接点 并且没有被访问过的
ArcNode* cur=first.firstarc;
while(cur){
if(visited[cur->adjvex]==false){
visited[cur->adjvex]=true;
cout<<"将"<adjvex].data<<"放入队列"<adjvex].data<<" ";
Q.push(G.vertices[cur->adjvex]);
}
cur=cur->nextarc;
}
Q.pop();
}
}
//广义优先(邻接表)
void BFSTravelChart(AdjoinChart G){
for(int i=0;i//为了避免非连通图的情况
if(visited[i]==false)BFSCharst(G,i);
}
}
//深度优先邻接表
void DFSChart(AdjoinChart G,int i){//从顶点i连接的点中选择一个没有被遍历过的 然后深入
ArcNode* cur=G.vertices[i].firstarc;
while(cur){
if(visited[cur->adjvex]==false){
visited[cur->adjvex]=true;
cout<adjvex].data<<" ";
DFSChart(G,cur->adjvex);
}
cur=cur->nextarc;
}
}
//深度优先遍历(邻接表)
void DFSTravelChart(AdjoinChart G){
for(int i=0;i//因为有可能是非连通图
if(visited[i]==false){//若是没有遍历则遍历
visited[i]=true;
cout<
cout<<"1、邻接矩阵 2、邻接表 "<
int choice=0;
cout<<"请输入你要使用何种方式来创建一个表"<>choice;
switch(choice){
case 1:{
AMGraph G;
CreateAdjoin(G);
cout<<"是否要对图进行遍历"<>flag;
if(1==flag){
DFSTravel(G);
}
else if(2==flag){
BFSTravel(G);
}
break;
}
case 2:{
AdjoinChart G;
CreateAdjoinChart(G);
cout<<"是否要对图进行遍历"<>flag;
if(1==flag){
DFSTravelChart(G);
}
else if(2==flag){
BFSTravelChart(G);
}
else{
;
}
break;
}
default:break;
}
}
感觉对你有帮助的话 点歌赞呗 你的点赞是对作者的一种莫大鼓励
