2021-10-29
2021/11/16 23:09:51
本文主要是介绍2021-10-29,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#define _CRT_SECURE_NO_WARNINGS 1 /*设计一个有向图和一个无向图,建立图的邻接矩阵或邻接表的存储结构 完成有向图和无向图的DFS(深度优先遍历) BFS(广度优先遍历)的操作。(有向图采用邻接矩阵存储,无向图采用邻接表存储)*/ #include<stdio.h> #include<stdlib.h> #define MAXVEX 100 #define INF 0 typedef struct MGraph { char data; int Vertex[MAXVEX]; int Arc[MAXVEX][MAXVEX]; int vexnum, arcnum; }MGraph; //有向图的邻接矩阵 MG void CreatMGraph(MGraph& G) { int i, j; printf("建立有向图的邻接矩阵\n"); printf("请输入顶点数和边数:"); scanf("%d %d", &G.vexnum, &G.arcnum); getchar(); printf("请输入顶点信息:"); for (i = 0; i < G.vexnum; i++) { scanf("%c", &G.Vertex[i]); } //初始化边表 for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) { G.Arc[i][j] = INF; } } //建立邻接矩阵 for (int k = 0; k < G.arcnum; k++) { printf("请输入(Vi,Vj)的i,j的下标:"); scanf("%d %d", &i, &j); G.Arc[i][j] = 1; } } void PrintMGraph(MGraph G) { int i, j; for (i = 0; i < G.vexnum; i++) { printf("%c:", G.Vertex[i]); for (j = 0; j < G.vexnum; j++) { printf("%d ", G.Arc[i][j]); } printf("\n"); } } typedef struct ArcNode { int adjvex; ArcNode* next; }ArcNode; typedef struct VNode { char data; ArcNode* first; }VNode,AdjList[MAXVEX]; typedef struct { AdjList vertices; int vexnum, arcnum; }ALGraph; //无向图的邻接表 ALG void CreatALGraph(ALGraph& G) { printf("建立无向图的邻接表\n"); int i, j; printf("请输入顶点数和边数:"); scanf("%d %d", &G.vexnum, &G.arcnum); getchar(); printf("请输入顶点信息:"); for (i = 0; i < G.vexnum; i++) { scanf("%c", &G.vertices[i].data); G.vertices[i].first = NULL; } //建立邻接表 for (int k = 0; k < G.arcnum; k++) { printf("请输入(Vi,Vj)的i,j的下标:"); scanf("%d %d", &i, &j); ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = j; s->next = G.vertices[i].first; G.vertices[i].first = s; ArcNode* m = (ArcNode*)malloc(sizeof(ArcNode)); m->adjvex = i; m->next = G.vertices[j].first; G.vertices[j].first = m; } } void PrintALGraph(ALGraph G) { ArcNode* p; for (int i = 0; i < G.vexnum; i++) { printf("%c:", G.vertices[i].data); for (p = G.vertices[i].first; p; p = p->next) { printf("%2c", G.vertices[p->adjvex].data); } printf("\n"); } } //全局变量,表示是否访问过 int Visited1[MAXVEX]; int Visited2[MAXVEX]; int Visited3[MAXVEX]; int Visited4[MAXVEX]; //有向图的邻接矩阵 MG 广度优先遍历 void BFS(MGraph& G, int i) { Visited1[MAXVEX] = { 0 }; //非递归,要用到队列 int front, rear; int Q[MAXVEX]; front = rear = -1; // 初始化队列 printf("%c ", G.Vertex[i]); // 输出当前结点 Visited1[i] = 1; // 表示访问过了 Q[++rear] = i; // 入队 while (front != rear) { i = Q[++front]; for (int j = 0; j < G.vexnum; j++) { if (G.Arc[i][j] != INF && Visited1[j] == 0) { printf("%c ", G.Vertex[j]); Visited1[j] = 1; // 已访问 Q[++rear] = j; // 入队 } } } } //无向图的邻接表 ALG 广度优先遍历 void BFS(ALGraph& G, int v) { Visited2[MAXVEX] = { 0 }; int front, rear; int Q[MAXVEX]; front = rear = -1; printf("%2c", G.vertices[v].data); Visited2[v] = 1; Q[++rear] = v; while (front != rear) { v = Q[++front]; for (ArcNode* p = G.vertices[v].first; p; p = p->next) { if (Visited2[p->adjvex] == 0) { printf("%2c", G.vertices[p->adjvex].data); Visited2[p->adjvex] = 1; Q[++rear] = p->adjvex; } } } } //有向图的邻接矩阵 MG 深度优先遍历递归 void DFS(MGraph& G, int i) { Visited3[MAXVEX] = { 0 }; if (i < 0 || i >= G.vexnum) { printf("i的位置出错!"); return; } printf("%2c", G.Vertex[i]); Visited3[i] = 1; for (int j = 0; j < G.vexnum; j++) { if (Visited3[j] == 0 && G.Arc[i][j] != INF) { DFS(G, j); } } } //无向图的邻接表 ALG 深度优先遍历递归 void DFS(ALGraph& G, int i) { Visited4[MAXVEX] = { 0 }; if (i < 0 || i >= G.vexnum) { printf("i的位置出错!"); return; } printf("%2c", G.vertices[i].data); Visited4[i] = 1; ArcNode* p = G.vertices[i].first; while (p) { if (Visited4[p->adjvex] == 0) { DFS(G, p->adjvex); } p = p->next; } } int main() { int i, j; MGraph MG; ALGraph ALG; CreatMGraph(MG); PrintMGraph(MG); printf("-----------------------------------\n"); printf("有向图的邻接矩阵 MG 广度优先遍历\n"); printf("从A开始:"); BFS(MG, 0); printf("\n"); printf("-----------------------------------\n"); printf("有向图的邻接矩阵 MG 深度优先遍历\n"); printf("从A开始:"); DFS(MG, 0); printf("\n"); printf("-----------------------------------\n"); CreatALGraph(ALG); PrintALGraph(ALG); printf("-----------------------------------\n"); printf("无向图的邻接表 ALG 广度优先遍历\n"); printf("从A开始:"); BFS(ALG, 0); printf("\n"); printf("-----------------------------------\n"); printf("无向图的邻接表 ALG 深度优先遍历\n"); printf("从A开始:"); DFS(ALG, 0); printf("\n"); printf("-----------------------------------\n"); return 0; } 测试数据: /* 7 8 ABCDEFG 0 1 0 2 1 0 1 3 2 4 2 5 4 6 5 6 7 7 ABCDEFG 0 1 0 2 1 3 2 4 2 5 4 6 5 6 */
这篇关于2021-10-29的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?