devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C语言|DFS+BFS】无向图的邻接表遍历非递归算法-用栈实现深度优先（DFS）以及用队列实现广度优先（BFS）遍历（文件读写操作）_无向图的非递归深度优先遍历算法

作者：盐析白兔 | 2024-04-18 10:03:55

赞

踩

无向图的非递归深度优先遍历算法

目录

实验课题：​

实验代码（C）：

实验思路：

实验代码解释：

申明相关变量：

初始化数据 

主函数部分：

算法核心：

实验代码（全）：

 实验效果：

实验课题：

现有一组无向图，要求用DFS和BFS遍历图，依次输出相关值。

实验代码（C）：

实验思路：

采用读取text文件，第一阶段依次读取文件中的顶点表数量和边表的数量，第二阶段读取各个顶点的名称，第三阶段读取各边表的两个下标位置。（注意：若是构建有向图的，可以在赋予边表时候只赋给一边，本案例是按照无向图双边赋值）。

实验代码解释：

申明相关变量：

申明变量（链表、节点、队列）

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. //#include<malloc.h>
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #define MaxVertices 100 
  6. #define MaxVertNum 100
  7. #define MAX 10 
  8.  
  9. typedef int VertextType;//顶点类型应由用户定义
  10. //typedef int EdgeType;//边上的权值类型应由用户定义
  11. /*边表结点*/
  12. typedef struct EdgeNode {//边表结点  边表
  13. 	int adjvex;//邻接点域，存储该顶点对应的下标
  14. 	//EdgeType weight;//用于存储权值，对于非网图可以不需要
  15. 	struct EdgeNode* next;//链域，指向下一个邻接点
  16. }EdgeNode;
  17.  
  18. typedef struct VertextNode {//顶点表结点 顶点表
  19. 	VertextType data;//顶点域，存储顶点信息
  20. 	EdgeNode* firstedge;//边表头指针
  21. }VertexNode;
  22.  
  23. typedef VertexNode AdjList[MaxVertices];//顶点表数组 
  24.  
  25. typedef struct {
  26. 	//VertexNode adjList[MaxVertices];
  27. 	AdjList adjList;//存放所有顶点表的数组-> VertexNode adjList[MaxVertices]
  28. 	int numVertexes, numEdges;//图中当前顶点数和边数
  29. }GraphAdjList;
  30. typedef GraphAdjList* GraphAdj;
  31.  
  32.  
  33. typedef struct LoopQueue{ //定义循环队列结构体
  34. 	int data[MAX];
  35. 	int front;
  36. 	int rear;   //注意每次队尾标记指向最后一个元素的下一个位置
  37. }Queue, *LQueue;
  38.  
  39. void InitQueue(LQueue &Q){  //初始化队列
  40. 	Q->front = Q->rear = 0;
  41. }
  42.  
  43. bool QueueisFull(LQueue &Q){ //判断队列是否满了
  44. 	if((Q->rear + 1) % MAX == Q->front){
  45. 		return true;  //已满
  46. 	}
  47. 	else{
  48. 		return false;
  49. 	}
  50. }
  51.  
  52. bool QueueisEmpty(LQueue &Q){//判断队列是否为空
  53. 	if(Q->front == Q->rear){
  54. 		return true;
  55. 	}
  56. 	return false;
  57. }
  58.  
  59.  
  60. void EnQueue(LQueue &Q, int i){ //入队列
  61. 	if(!QueueisFull(Q)){
  62. 		Q->data[Q->rear] = i;
  63. 		Q->rear = (Q->rear + 1) % MAX;  //队尾指针后移
  64. 	}
  65. }
  66.  
  67. void DeQueue(LQueue &Q, int *k){ //出队列
  68. 	if(!QueueisEmpty(Q)){
  69. 		*k = Q->data[Q->front];
  70. 		Q->front = (Q->front + 1) % MAX;
  71. 	}
  72. }

初始化数据 

  1. int InitGraph(GraphAdj G) {
  2.  
  3. 	int i, j;
  4. 	EdgeNode* s;//新的边结点
  5. 	FILE* fp = NULL;
  6. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList2.txt", "rb");
  7. 	if (fp == NULL) {
  8. 		printf("ERROR");
  9. 		return -1;
  10. 	}
  11. 	fscanf(fp, "%d %d", &G->numVertexes, &G->numEdges);//顶点数,边数
  12.  
  13. 	/*******************创建顶点表**************************/
  14. 	for (i = 0; i < G->numVertexes; i++) {
  15. 		fscanf(fp, "%d", &G->adjList[i].data);
  16. 		G->adjList[i].firstedge = NULL;//注意将边表置空
  17. 	}
  18.  
  19. 	/******************创建边表****************************/
  20. 	for (int k = 0; k < G->numEdges; k++) {
  21. 		fscanf(fp, "%d %d", &i, &j);//"输入边(Vi,Vj)上的顶点序号
  22.  
  23. 		//对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1) 
  24. 		s = (EdgeNode*)malloc(sizeof(EdgeNode));
  25. 		s->adjvex = j;//边表赋值
  26. 		s->next = G->adjList[i].firstedge;
  27. 		G->adjList[i].firstedge = s;
  28.  
  29. 		//对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
  30. 		s = (EdgeNode*)malloc(sizeof(EdgeNode));
  31. 		s->adjvex = i;
  32. 		s->next = G->adjList[j].firstedge;
  33. 		G->adjList[j].firstedge = s;
  34. 	}
  35.  
  36. 	fclose(fp);
  37. }
  38.  
  39.  
  40.  
  41. void DisplayGraph(GraphAdjList* G) {
  42. 	int i;
  43. 	FILE *fp;
  44. 	/**文档输出     ***/
  45. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result.txt", "w");
  46. 	if (fp == NULL) {
  47. 		printf("ERROR");
  48. 		//	return -1;
  49. 	}
  50. 	fprintf(fp, "Enter contents to store in file : \n");
  51. 	EdgeNode* p;
  52. 	for (int i = 0; i < G->numVertexes; i++) {
  53. 		p = G->adjList[i].firstedge;
  54. 		printf("%d->", i);
  55. 		fprintf(fp, "%d->", i);
  56. 		while (1) {
  57. 			if (p == NULL) {
  58. 				printf("^");
  59. 				fprintf(fp, "^");
  60. 				break;
  61. 			}
  62. 			printf("%d->", p->adjvex);//输出边表的下标，但这里可以表示原有的 数 
  63. 			fprintf(fp, "%d->", p->adjvex);
  64. 			p = p->next;
  65. 		}
  66. 		printf("\n");
  67. 		fprintf(fp, "\n");
  68. 	}
  69.  
  70. 	fclose(fp);//？？？ 
  71. }

主函数部分：

  1. int main() {
  2. 	int index, flage = 1;
  3. 	GraphAdjList* G = (GraphAdjList*)malloc(sizeof(GraphAdjList));
  4. 	InitGraph(G);
  5. 	printf("现有无向图的链表存储：\n");
  6. 	DisplayGraph(G);
  7.  
  8. 	while (flage) {
  9. 		printf("现有无向图的DFS(按1)：\n");
  10. 		printf("现有无向图的BFS(按2)：\n");
  11. 		printf("退出遍历(按3)：\n");
  12. 		//DFSTraverse(G);
  13. 		scanf("%d", &index);
  14. 		switch (index) {
  15. 		case 1:
  16. 			DFS(G, 0);
  17. 			break;
  18. 		case 2:
  19. 			BFS(G,0);
  20. 			break;
  21. 		case 3:
  22. 			flage = 0;
  23. 			break;
  24. 		}
  25. 	}
  26. 	return 0;
  27. }

算法核心：

DFS部分。运用栈。将head后面依次放入栈中，并选取栈头的visit为1置为新的head,遍历其后面的依次放入栈中，直到栈为空结束。

  1. void DFS(GraphAdjList* G, int v0) { //图，下标位置 
  2. 	int stack[MaxVertNum];
  3. 	EdgeNode* p;
  4. 	int visited[MaxVertNum] = { 0 }, top = -1, v;
  5. 	printf("此图的DFS遍历：\n");
  6. 	//p = G->adjList[v0].firstedge;
  7. 	stack[++top] = v0;//top=0,存储第一个数v0(下标) 
  8.  
  9. 	FILE *fp;	/**文档输出     ***/
  10. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result_DFS.txt", "w");
  11. 	if (fp == NULL) {
  12. 		printf("ERROR");
  13. 		//	return -1;
  14. 	}
  15. 	fprintf(fp, "此图的DFS遍历：\n");
  16.  
  17. 	while (top != -1)//判断栈有无有空 
  18. 	{
  19. 		v = stack[top--];//出栈 v(数值data/下标)
  20. 		if (!visited[v]) {//v 未被访问 
  21. 			printf("%d ", G->adjList[v].data);
  22. 			fprintf(fp, "%d ", G->adjList[v].data);
  23. 			visited[v] = 1;
  24. 		}
  25. 		p = G->adjList[v].firstedge;//边结点指针 
  26. 		while (p) {
  27. 			if (!visited[p->adjvex]) {//p边结点的下标有无访问到 
  28. 				stack[++top] = p->adjvex;
  29. 			}
  30. 			p = p->next;
  31. 		}
  32. 	}
  33. 	fclose(fp);
  34. 	printf("\n");
  35. }

BFS部分。运用队列。将head后面依次放入队列中，并选取队头的取出，其visit为1置为新的head,遍历其后面的依次放入队列中，直到队列为空结束。

  1. void BFS(GraphAdjList* G,int i){
  2. 	int visited[MaxVertNum] = { 0 };
  3. 	//int i = 0;
  4. 	Queue *Q =(LQueue)malloc(sizeof(Queue));
  5. 	for(int i = 0; i < G->numVertexes; i++){
  6. 		visited[i] = 0;
  7. 	}
  8.  
  9. 	FILE *fp;	/**文档输出     ***/
  10. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result_BFS.txt", "w");
  11. 	if (fp == NULL) {
  12. 		printf("ERROR");
  13. 		//	return -1;
  14. 	}
  15. 	fprintf(fp, "此图的BFS遍历：\n");
  16.  
  17. 	InitQueue(Q);  //初始化队列
  18.  
  19. 	visited[i] = 1;//从0下标开始
  20. 	printf("%d ", G->adjList[i].data);
  21. 	fprintf(fp,"%d ", G->adjList[i].data);
  22.  
  23. 	EnQueue(Q, i);//入队？
  24.  
  25. 	while(!QueueisEmpty(Q)){//根据队列遍历全部顶点坐标
  26. 		DeQueue(Q, &i);  //这里不断的修改i的值，队头元素出队，改变i值？
  27. 		EdgeNode *e = G->adjList[i].firstedge;  //i顶点的邻接链表的第一个结点
  28. 		while(e){//e存在时，将e的所有邻接点加入队列,也就是遍历i的所有邻接点
  29. 			if(!visited[e->adjvex]){ // adjvex是e所表示的结点下标
  30. 				visited[e->adjvex] = 1;
  31. 				printf("%d ", G->adjList[e->adjvex].data);//输出顶点下标的数值
  32. 				fprintf(fp,"%d ", G->adjList[e->adjvex].data);//输出顶点下标的数值
  33. 				EnQueue(Q, e->adjvex); //将该结点入队
  34. 			}
  35. 			e = e->next; //遍历i的下一个邻接点
  36. 		}
  37. 	}
  38. 	
  39. 	printf("\n");
  40. 	fclose(fp);
  41. }

实验代码（全）：

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. //#include<malloc.h>
  4. #define _CRT_SECURE_NO_WARNINGS
  5. #define MaxVertices 100 
  6. #define MaxVertNum 100
  7. #define MAX 10 
  8.  
  9. typedef int VertextType;//顶点类型应由用户定义
  10. //typedef int EdgeType;//边上的权值类型应由用户定义
  11. /*边表结点*/
  12. typedef struct EdgeNode {//边表结点  边表
  13. 	int adjvex;//邻接点域，存储该顶点对应的下标
  14. 	//EdgeType weight;//用于存储权值，对于非网图可以不需要
  15. 	struct EdgeNode* next;//链域，指向下一个邻接点
  16. }EdgeNode;
  17.  
  18. typedef struct VertextNode {//顶点表结点 顶点表
  19. 	VertextType data;//顶点域，存储顶点信息
  20. 	EdgeNode* firstedge;//边表头指针
  21. }VertexNode;
  22.  
  23. typedef VertexNode AdjList[MaxVertices];//顶点表数组 
  24.  
  25. typedef struct {
  26. 	//VertexNode adjList[MaxVertices];
  27. 	AdjList adjList;//存放所有顶点表的数组-> VertexNode adjList[MaxVertices]
  28. 	int numVertexes, numEdges;//图中当前顶点数和边数
  29. }GraphAdjList;
  30. typedef GraphAdjList* GraphAdj;
  31.  
  32. int InitGraph(GraphAdj G) {
  33.  
  34. 	int i, j;
  35. 	EdgeNode* s;//新的边结点
  36. 	FILE* fp = NULL;
  37. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList2.txt", "rb");
  38. 	if (fp == NULL) {
  39. 		printf("ERROR");
  40. 		return -1;
  41. 	}
  42. 	fscanf(fp, "%d %d", &G->numVertexes, &G->numEdges);//顶点数,边数
  43.  
  44. 	/*******************创建顶点表**************************/
  45. 	for (i = 0; i < G->numVertexes; i++) {
  46. 		fscanf(fp, "%d", &G->adjList[i].data);
  47. 		G->adjList[i].firstedge = NULL;//注意将边表置空
  48. 	}
  49.  
  50. 	/******************创建边表****************************/
  51. 	for (int k = 0; k < G->numEdges; k++) {
  52. 		fscanf(fp, "%d %d", &i, &j);//"输入边(Vi,Vj)上的顶点序号
  53.  
  54. 		//对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1) 
  55. 		s = (EdgeNode*)malloc(sizeof(EdgeNode));
  56. 		s->adjvex = j;//边表赋值
  57. 		s->next = G->adjList[i].firstedge;
  58. 		G->adjList[i].firstedge = s;
  59.  
  60. 		//对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
  61. 		s = (EdgeNode*)malloc(sizeof(EdgeNode));
  62. 		s->adjvex = i;
  63. 		s->next = G->adjList[j].firstedge;
  64. 		G->adjList[j].firstedge = s;
  65. 	}
  66.  
  67. 	fclose(fp);
  68. }
  69.  
  70.  
  71.  
  72. void DisplayGraph(GraphAdjList* G) {
  73. 	int i;
  74. 	FILE *fp;
  75. 	/**文档输出     ***/
  76. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result.txt", "w");
  77. 	if (fp == NULL) {
  78. 		printf("ERROR");
  79. 		//	return -1;
  80. 	}
  81. 	fprintf(fp, "Enter contents to store in file : \n");
  82. 	EdgeNode* p;
  83. 	for (int i = 0; i < G->numVertexes; i++) {
  84. 		p = G->adjList[i].firstedge;
  85. 		printf("%d->", i);
  86. 		fprintf(fp, "%d->", i);
  87. 		while (1) {
  88. 			if (p == NULL) {
  89. 				printf("^");
  90. 				fprintf(fp, "^");
  91. 				break;
  92. 			}
  93. 			printf("%d->", p->adjvex);//输出边表的下标，但这里可以表示原有的 数 
  94. 			fprintf(fp, "%d->", p->adjvex);
  95. 			p = p->next;
  96. 		}
  97. 		printf("\n");
  98. 		fprintf(fp, "\n");
  99. 	}
  100.  
  101. 	fclose(fp);//？？？ 
  102. }
  103.  
  104. void DFS(GraphAdjList* G, int v0); //图，下标位置 
  105. void BFS(GraphAdjList* G,int v0);
  106.  
  107.  
  108. int main() {
  109. 	int index, flage = 1;
  110. 	GraphAdjList* G = (GraphAdjList*)malloc(sizeof(GraphAdjList));
  111. 	InitGraph(G);
  112. 	printf("现有无向图的链表存储：\n");
  113. 	DisplayGraph(G);
  114.  
  115. 	while (flage) {
  116. 		printf("现有无向图的DFS(按1)：\n");
  117. 		printf("现有无向图的BFS(按2)：\n");
  118. 		printf("退出遍历(按3)：\n");
  119. 		//DFSTraverse(G);
  120. 		scanf("%d", &index);
  121. 		switch (index) {
  122. 		case 1:
  123. 			DFS(G, 0);
  124. 			break;
  125. 		case 2:
  126. 			BFS(G,0);
  127. 			break;
  128. 		case 3:
  129. 			flage = 0;
  130. 			break;
  131. 		}
  132.  
  133. 	}
  134.  
  135. 	return 0;
  136. }
  137.  
  138. /********************DFS*************************************/
  139. void DFS(GraphAdjList* G, int v0) { //图，下标位置 
  140. 	int stack[MaxVertNum];
  141. 	EdgeNode* p;
  142. 	int visited[MaxVertNum] = { 0 }, top = -1, v;
  143. 	printf("此图的DFS遍历：\n");
  144. 	//p = G->adjList[v0].firstedge;
  145. 	stack[++top] = v0;//top=0,存储第一个数v0(下标) 
  146.  
  147. 	FILE *fp;	/**文档输出     ***/
  148. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result_DFS.txt", "w");
  149. 	if (fp == NULL) {
  150. 		printf("ERROR");
  151. 		//	return -1;
  152. 	}
  153. 	fprintf(fp, "此图的DFS遍历：\n");
  154.  
  155. 	while (top != -1)//判断栈有无有空 
  156. 	{
  157. 		v = stack[top--];//出栈 v(数值data/下标)
  158. 		if (!visited[v]) {//v 未被访问 
  159. 			printf("%d ", G->adjList[v].data);
  160. 			fprintf(fp, "%d ", G->adjList[v].data);
  161. 			visited[v] = 1;
  162. 		}
  163. 		p = G->adjList[v].firstedge;//边结点指针 
  164. 		while (p) {
  165. 			if (!visited[p->adjvex]) {//p边结点的下标有无访问到 
  166. 				stack[++top] = p->adjvex;
  167. 			}
  168. 			p = p->next;
  169. 		}
  170. 	}
  171. 	fclose(fp);
  172. 	printf("\n");
  173. }
  174. /********************BFS*************************************/
  175.  
  176.  
  177. typedef struct LoopQueue{ //定义循环队列结构体
  178. 	int data[MAX];
  179. 	int front;
  180. 	int rear;   //注意每次队尾标记指向最后一个元素的下一个位置
  181. }Queue, *LQueue;
  182.  
  183. void InitQueue(LQueue &Q){  //初始化队列
  184. 	Q->front = Q->rear = 0;
  185. }
  186.  
  187. bool QueueisFull(LQueue &Q){ //判断队列是否满了
  188. 	if((Q->rear + 1) % MAX == Q->front){
  189. 		return true;  //已满
  190. 	}
  191. 	else{
  192. 		return false;
  193. 	}
  194. }
  195.  
  196. bool QueueisEmpty(LQueue &Q){//判断队列是否为空
  197. 	if(Q->front == Q->rear){
  198. 		return true;
  199. 	}
  200. 	return false;
  201. }
  202.  
  203.  
  204. void EnQueue(LQueue &Q, int i){ //入队列
  205. 	if(!QueueisFull(Q)){
  206. 		Q->data[Q->rear] = i;
  207. 		Q->rear = (Q->rear + 1) % MAX;  //队尾指针后移
  208. 	}
  209. }
  210.  
  211. void DeQueue(LQueue &Q, int *k){ //出队列
  212. 	if(!QueueisEmpty(Q)){
  213. 		*k = Q->data[Q->front];
  214. 		Q->front = (Q->front + 1) % MAX;
  215. 	}
  216. }
  217.  
  218. void BFS(GraphAdjList* G,int i){
  219. 	int visited[MaxVertNum] = { 0 };
  220. 	//int i = 0;
  221. 	Queue *Q =(LQueue)malloc(sizeof(Queue));
  222. 	for(int i = 0; i < G->numVertexes; i++){
  223. 		visited[i] = 0;
  224. 	}
  225.  
  226. 	FILE *fp;	/**文档输出     ***/
  227. 	fp = fopen("D://Project//shuJuJieGou//DFS//GraphAdjList_result_BFS.txt", "w");
  228. 	if (fp == NULL) {
  229. 		printf("ERROR");
  230. 		//	return -1;
  231. 	}
  232. 	fprintf(fp, "此图的BFS遍历：\n");
  233.  
  234. 	InitQueue(Q);  //初始化队列
  235.  
  236. 	visited[i] = 1;//从0下标开始
  237. 	printf("%d ", G->adjList[i].data);
  238. 	fprintf(fp,"%d ", G->adjList[i].data);
  239.  
  240. 	EnQueue(Q, i);//入队？
  241.  
  242. 	while(!QueueisEmpty(Q)){//根据队列遍历全部顶点坐标
  243. 		DeQueue(Q, &i);  //这里不断的修改i的值，队头元素出队，改变i值？
  244. 		EdgeNode *e = G->adjList[i].firstedge;  //i顶点的邻接链表的第一个结点
  245. 		while(e){//e存在时，将e的所有邻接点加入队列,也就是遍历i的所有邻接点
  246. 			if(!visited[e->adjvex]){ // adjvex是e所表示的结点下标
  247. 				visited[e->adjvex] = 1;
  248. 				printf("%d ", G->adjList[e->adjvex].data);//输出顶点下标的数值
  249. 				fprintf(fp,"%d ", G->adjList[e->adjvex].data);//输出顶点下标的数值
  250. 				EnQueue(Q, e->adjvex); //将该结点入队
  251. 			}
  252. 			e = e->next; //遍历i的下一个邻接点
  253. 		}
  254. 	}
  255. 	
  256. 	printf("\n");
  257. 	fclose(fp);
  258. }

 实验效果：

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/445358
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号