• 数据结构——深度优先遍历（DFS）无向连通图

    以下是数据结构中关于深度优先遍历无向连通图的操作（编程风格参考严蔚敏版数据结构）。
    其实深度优先遍历就是二叉树的先序遍历的推广。

    头文件以及宏定义

    #include
#include
using namespace std; 
typedef char VerTexType; 
typedef int ArcType;
#define MaxInt 32767
#define MVNum 100
#define OK 1
#define ERROR -1;
bool visited[MVNum];

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    说明： VerTexType; //代表节点变量的类型（一般我们用ABCD表示节点，所以用char） typedef int
    ArcType; // 代表边变量的类型（肯定用长度表示边呀，所以用int或者double都可）
    #define MaxInt 32767 //边的最大值（表示目标不可达）
    #define MVNum 100 //最大节点数
    bool visited[MVNum];//标记访问记录的数组；宏定义会自动赋值为0

    无向图结构体的定义

    typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F','G','H'};//节点表
	ArcType arcs[MVNum][MVNum];//邻接表（肯定是个正方形的矩阵）
	int vexnum = 8,arcnum = 9;//该邻接矩阵的节点数、边数  
}AMGraph; 

    • 1
    • 2
    • 3
    • 4
    • 5

    说明：
    为了演示方便，就直接写死节点名称、节点数和边数了。有需要时自行修改即可。

    创建无向图

    status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;//自己到自己的距离为0
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=1;
	G.arcs[0][2]=1;
	G.arcs[1][3]=1;
	G.arcs[1][4]=1;
	G.arcs[2][5]=1;
	G.arcs[2][6]=1;
	G.arcs[3][7]=1;
	G.arcs[4][7]=1;
	G.arcs[5][6]=1;
	for(int i=0;i<G.vexnum;i++){
		for(int j=i+1;j<G.vexnum;j++){
			if(G.arcs[i][j]==1){
				G.arcs[j][i] = 1;
			} 
		}
	}//矩阵对称,生成矩阵下三角
	return OK; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    说明：
    这个邻接表的设置（即节点之间边的设置）如下图所示：
    在这里插入图片描述
    对称矩阵的生成，只需要把下标i和j置换即可。

    DFS（深度优先遍历）核心代码

    void DFS(AMGraph &G,VerTexType v){//节点v 
	int vi = LocateVex(G,v);//v(v-index)的下标 
	cout<<G.vexs[vi]<<" ";//输出当前节点
	visited[vi] = true;//已访问 
	for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn)){//vn(v-next)表示v的全部邻接点的下标（如果vn<0表示不存在邻接点） 
		if(!visited[vn]){//当前邻接点未被访问过,那就访问该节点
			VerTexType V = Transform(G,vn);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		} 
	} 
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    说明：
    vi(v-index)表示v的下标
    vn(v-next)表示v的全部邻接点的下标（如果vn<0表示不存在邻接点）
    因为这里DFS第二个参数类型是节点而不是下标，所以获取邻接节点下标后要转回节点V的形式递归调用DFS；
    FirstAdjVex(G,v)获取v的第一个邻接节点
    NextAdjVex(G,v,vn)依次获取v的每个邻接节点的下标

    获取节点下标

    int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    将下标转换成节点

    VerTexType Transform(AMGraph G, int vn){
	return G.vexs[vn]; 
}

    • 1
    • 2
    • 3

    获取当前的第一个邻接节点以及全部邻接节点下标

    int FirstAdjVex(AMGraph G,VerTexType v){//v的第一个邻接点 
	int vi = LocateVex(G,v);
	for(int i=0;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到邻接点 
}

int NextAdjVex(AMGraph G,VerTexType v ,int vn){//v相对于vn的下一个邻接点 
	int vi = LocateVex(G,v);
	
	for(int i=vn+1;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到下一个邻接点 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    注意：获取下一个邻接节点不需要从0开始遍历，从上一个邻接节点的下标开始遍历即可。

    输出邻接表

    void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
				
		}
		cout<<endl;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    源码执行结果：

    在这里插入图片描述

    执行过程：
    A的第一个邻接节点为B，此时A访问过了（输出A），去访问B
    B的第一个邻接节点为A，但是A和B都访问过了（输出B），往右寻找：D节点未被访问过，去访问D；
    D被访问（输出D），D的第一个邻接节点是B（已访问），向右寻找：寻到为被访问过的H；
    访问H（输出H），H的第一个邻接节点为D（已访问），向右寻找：寻到E；
    访问E（输出E），此时E的邻接点B和H都已访问。
    还记得DFS里循环的这行代码吗？
    for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn))
    刚才就是执行了vn=FirstAdjVex(G,v)这一次循环迭代DFS的过程，然后我们执行vn=NextAdjVex(G,v,vn)的循环迭代DFS的过程。
    此时vn = 2（也就是对应C），C未被访问过，访问C；
    访问C（输出C），C的第一个邻接节点是A（已访问），向右寻找：寻找到F未被访问过，访问F；
    访问F（输出F），F的第一个邻接节点是C（已访问），向右寻找：寻找到G未被访问过，访问G。
    访问G（输出G），此时G的邻接节点C和F全部都被访问过了，本次循环结束。
    接下来的循环还在进行，但是全部节点都已经被访问过了，就不会输出了，直到嵌套的循环全部跑完，程序结束。

    换个起始点一样适用

    在这里插入图片描述
    在这里插入图片描述

    完整源代码

    #include
#include
using namespace std; 
typedef char VerTexType; //代表节点变量的类型（一般我们用ABCD表示节点，所以用char）
typedef int ArcType; //  代表边变量的类型（肯定用长度表示边呀，所以用int或者double都可）
#define MaxInt 32767 //边的最大值（表示目标不可达）
#define MVNum 100    //最大节点数 
#define OK 1
#define ERROR -1;
typedef int status;
bool visited[MVNum];//标记访问记录的数组；宏定义会自动赋值为0 
typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F','G','H'};//节点表
	ArcType arcs[MVNum][MVNum];//邻接表（肯定是个正方形的矩阵）
	int vexnum = 8,arcnum = 9;//该邻接矩阵的节点数、边数  
}AMGraph; 

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=1;
	G.arcs[0][2]=1;
	G.arcs[1][3]=1;
	G.arcs[1][4]=1;
	G.arcs[2][5]=1;
	G.arcs[2][6]=1;
	G.arcs[3][7]=1;
	G.arcs[4][7]=1;
	G.arcs[5][6]=1;
	for(int i=0;i<G.vexnum;i++){
		for(int j=i+1;j<G.vexnum;j++){
			if(G.arcs[i][j]==1){
				G.arcs[j][i] = 1;
			} 
		}
	}//矩阵对称 
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
				
		}
		cout<<endl;
	}
}

VerTexType Transform(AMGraph G, int vn){
	return G.vexs[vn]; 
}

int FirstAdjVex(AMGraph G,VerTexType v){//v的第一个邻接点 
	int vi = LocateVex(G,v);
	for(int i=0;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到邻接点 
}

int NextAdjVex(AMGraph G,VerTexType v ,int vn){//v相对于vn的下一个邻接点 
	int vi = LocateVex(G,v);
	
	for(int i=vn+1;i<G.vexnum;i++){
		if(!visited[i]&&G.arcs[vi][i]==1){
			return i;//找到邻接点且此邻接点未被访问过 
		}
	} 
	return ERROR;//未找到下一个邻接点 
}

void DFS(AMGraph &G,VerTexType v){//节点v 
	int vi = LocateVex(G,v);//vi(v-index)的下标 
	cout<<G.vexs[vi]<<" ";//输出当前节点
	visited[vi] = true;//已访问 
	for(int vn=FirstAdjVex(G,v);vn>=0;vn=NextAdjVex(G,v,vn)){//vn(v-next)表示v的全部邻接点的下标（如果vn<0表示不存在邻接点） 
//		cout<
		if(!visited[vn]){//当前邻接点未被访问过 
			VerTexType V = Transform(G,vn);//将该下标转回节点名称进行迭代 
			DFS(G,V);
		} 
	} 
} 

int main(){
	AMGraph G;
	CreateUDN(G);
	ShowGraph(G);
	VerTexType V;
	cout<<"\n请输入开始遍历的节点:";
	cin>>V;
	DFS(G,V);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

    敬请批评指正！

  • 相关阅读:
    回归预测 | Matlab实现基于MIC-BP最大互信息系数数据特征选择算法结合BP神经网络的数据回归预测
    Mysql全局优化总结
    Node.js数据抓取乱码问题汇总
    Multimodal Token Fusion for Vision Transformers
    pycharm 打开Terminal时报错activate.ps1，因为在此系统上禁止运行脚本，并因此无法进入虚拟环境
    【CVPR2021】MLP-Mixer: An all-MLP Architecture for Vision
    通过curl命令分析http接口请求各阶段的耗时等
    八款流行无线黑客工具，非常实用
    编程大杂烩（四）
    DBA-现在应该刚刚入门吧
  • 原文地址：https://blog.csdn.net/qq_51231048/article/details/127591948