数据结构——实验五·图

news/2025/1/23 21:39:48/

嗨~~欢迎来到Tubishu的博客🌸如果你也是一名在校大学生，正在寻找各种编程资源，那么你就来对地方啦🌟
Tubishu是一名计算机本科生，会不定期整理和分享学习中的优质资源，希望能为你的编程之路添砖加瓦⭐🔥
当然，如果你也好的资源推荐，欢迎在评论区分享，让我们共同打造一个丰富的编程资源库🔥🔥🔥
本文专栏 ➡️ 数据结构

图的遍历

本实验是基于C实现图的遍历操作，包括用邻接矩阵和邻接表创建有向图/无向图，深度优先和广度优先分别遍历。

实验目的：

  • 掌握图的逻辑结构
  • 掌握图的邻接矩阵、邻接表存储结构
  • 掌握图在邻接矩阵、邻接表上遍历算法的实现

实验内容:

（1）建立图的邻接矩阵、邻接表存储；
（2）对建立的图进行深度优先遍历；
（3）对建立的图进行广度优先遍历。

要求：设计菜单，根据菜单提示进行操作。

注：图遍历也涉及到堆栈与队列。在广度遍历中用到了队列，深度遍历中用到了堆栈。

实验产出：

1.核心代码：

#include<stdio.h>
#include<stdlib.h>#define ERROR 0
#define OK 1// 定义循环队列
#define MAXQSIZE 1024
typedef char QElemType;
typedef struct {QElemType data[MAXQSIZE]; // 数据的存储区 int front, rear;          // 队头、队尾指针 int num;                  // 队中元素个数 
} c_SeqQ;#define MaxVerNum 100        // 最大订点数为100 
#define MAxInt 32767         // 表示极大值 即 ∞// 定义邻接矩阵数据类型
typedef char VertexType;      // 顶点类型  
typedef int ArcType;          // 边的权值 
typedef int OtheInfo;
typedef struct {VertexType vexs[MaxVerNum];           // 顶点表，储存顶点信息 ArcType arcs[MaxVerNum][MaxVerNum];   // 邻接矩阵，即边表 int vexnum, arcnum;
} AMGraph;// 定义邻接表数据类型
typedef struct ArcNode {      // 边结点 int adjvex;               // 该边所指向的顶点的位置 struct ArcNode *nextarc;  // 指向下一条边的指针 OtheInfo info;
} ArcNode;typedef struct VNode {        // 顶点表结点 VertexType data;          // 顶点信息 ArcNode *firstarc;        // 指向第一条依附该顶点的边指针 
} VNode, AdjList[MaxVerNum];typedef struct {AdjList vertices;         // 邻接表 int vexnum, arcnum;
} ALGraph;// 循环队列的初始化
int InitQueue_Sq(c_SeqQ *&Q) {if (!(Q = new c_SeqQ)) return ERROR;Q->front = Q->rear = 0;Q->num = 0;return OK;
}// 销毁顺序队列
int DestroyQueue_Sq(c_SeqQ *Q) {if (!Q) {free(Q);   // delete Q;return OK;}return ERROR;
}// 判断顺序队列空
int QueueEmpty_Sq(c_SeqQ *Q) {return (Q->num == 0);
}// 入队操作
int EnQueue_Sq(c_SeqQ *Q, QElemType e) {if (Q->num == MAXQSIZE) return ERROR;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXQSIZE;Q->num++;return OK;
}// 出队操作
int DeQueue_Sq(c_SeqQ *Q, QElemType &e) {if (Q->num == 0) return ERROR;e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXQSIZE;Q->num--;return OK;
}// 建立图G的邻接矩阵存储
void CreateAMGraph(AMGraph &G) {int i, j, k;int flag = 1;printf("图为有向图,还是无向图,输入1,表示无向图,否则,表示有向图: ");scanf(" %d", &flag);printf("请输入顶点数和边数(输入格式为:顶点数,边数): ");scanf(" %d,%d", &G.vexnum, &G.arcnum);printf("请输入顶点信息(例如:若有 5个顶点,则连续输入 ABCDE): ");for (i = 0; i < G.vexnum; i++) {scanf(" %c", &G.vexs[i]);}for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = 0;              // 初始化邻接矩阵      printf("\n\t注意：顶点序列对应的序号从 0 起始编号，即 0, 1, 2, ... \n\n");printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j <cr>)\n");for (k = 0; k < G.arcnum; k++) {printf("\n");for (i = 0; i < G.vexnum; i++)printf("%c--%d\n", G.vexs[i], i);printf("请输入第%d条边: ", k + 1);scanf("%d,%d", &i, &j);            // 输入边，建立邻接矩阵if (i < 0 || i >= G.vexnum || j < 0 || j >= G.vexnum) {printf("输入出错!\n");k--;continue;}printf("(%c--%c)\n", G.vexs[i], G.vexs[j]);G.arcs[i][j] = 1;// 无向图的邻接矩阵存储建立if (flag == 1)G.arcs[j][i] = 1;}// 输出邻接矩阵 printf("\n邻接矩阵：\n");for (i = 0; i < G.vexnum; i++) {for (j = 0; j < G.vexnum; j++) printf("%d ", G.arcs[i][j]);printf("\n"); }
}// 建立图G的邻接表存储
void CreateALGraph(ALGraph &G) {int i, j, k;ArcNode *s;int flag = 1;printf("图为有向图,还是无向图,输入1,表示无向图,否则,表示有向图: ");scanf(" %d", &flag);printf("请输入顶点数和边数(输入格式为:顶点数,边数): ");scanf(" %d,%d", &G.vexnum, &G.arcnum);   // 读入顶点和边数 printf("请输入顶点信息(例如:若有 5个顶点,则连续输入 ABCDE): ");for (i = 0; i < G.vexnum; i++) {         // 建立有n个顶点的顶点表 scanf(" %c", &G.vertices[i].data);   // 读入顶点信息 G.vertices[i].firstarc = NULL;       // 顶点的边表头指针设为空 }printf("\n\t注意：顶点序列对应的序号从 0 起始编号，即 0, 1, 2, ... \n\n");printf("请输入每条边对应的两个顶点的序号(输入格式为: i,j <cr>)\n");for (k = 0; k < G.arcnum; k++) {         // 建立边表printf("\n");for (i = 0; i < G.vexnum; i++)printf("%c--%d\n", G.vertices[i].data, i);printf("请输入第%d条边: ", k + 1);scanf("%d,%d", &i, &j);              // 读入边(Vi,Vj)或<Vi,Vj>的顶点对应序号if (i < 0 || i >= G.vexnum || j < 0 || j >= G.vexnum) {printf("输入出错!\n");k--;continue;}printf("(%c--%c)\n", G.vertices[i].data, G.vertices[j].data);s = new ArcNode;                           // 生成新边表结点ss->adjvex = j;                             // 邻接点序号为js->nextarc = G.vertices[i].firstarc;       // 将新边表结点s插入到顶点Vi的边表头部G.vertices[i].firstarc = s;// 无向图 if (flag == 1) {s = new ArcNode;                       // 生成新边表结点ss->adjvex = i;                         // 邻接点序号为is->nextarc = G.vertices[j].firstarc;   // 将新边表结点s插入到顶点Vj的边表头部G.vertices[j].firstarc = s;}}
}// 深度优先搜索遍历一个连通图（图的存储结构采用邻接矩阵表示）
// 从第v个顶点出发递归地深度优先遍历图G，图的存储结构采用邻接矩阵表示。
// 第1个形参AMGraph G是指要遍历的图的存储结构
// 第2个形参int v是指从序号为v的顶点开始深度优先遍历图
// 第3个形参int visited[]数组，指示顶点是否被访问过
void DFSM(AMGraph G, int v, int visited[]) {visited[v] = 1;                                     // 设置访问标志数组相应分量值为1printf("访问顶点: %d --- %c\n", v, G.vexs[v]);      // 输出正访问的顶点for (int w = 0; w < G.vexnum; w++)                  // 依次检查邻接矩阵v所在的行if ((G.arcs[v][w] != 0) && (!visited[w]))       // G.arcs[v][w]!=0表示w是v的邻接顶点DFSM(G, w, visited);                        // 如果w未访问，则递归调用DFSM}// 深度优先遍历图(图的存储结构采用邻接矩阵表示)
void DFSMTraverse(AMGraph &G) {int v, visited[MaxVerNum];for (v = 0; v < G.vexnum; v++)           // 初始化visited数组，该数组每一个元素对应图的一个顶点 visited[v] = 0;                      // 用来标识顶点是否被访问过 for (v = 0; v < G.vexnum; v++) {if (!visited[v]) {printf("顶点 %c 为起点的深度优先遍历:\n", G.vexs[v]);DFSM(G, v, visited);             // 对未访问过的顶点调用DFS }}
}// 深度优先遍历邻接表
void DFSL(ALGraph G, int v, int visited[]) {ArcNode *p;visited[v] = 1;printf("访问顶点: %d --- %c\n", v, G.vertices[v].data);p = G.vertices[v].firstarc;while (p) {if (!visited[p->adjvex]) {DFSL(G, p->adjvex, visited);}p = p->nextarc;}
}// 深度优先遍历邻接表的主函数
void DFSLTraverse(ALGraph &G) {int v, visited[MaxVerNum];for (v = 0; v < G.vexnum; v++) {visited[v] = 0;}for (v = 0; v < G.vexnum; v++) {if (!visited[v]) {printf("顶点 %c 为起点的深度优先遍历:\n", G.vertices[v].data);DFSL(G, v, visited);}}
}// 广度优先遍历邻接矩阵
void BFSM(AMGraph G, int v, int visited[]) {c_SeqQ *queue;InitQueue_Sq(queue);QElemType u;visited[v] = 1;printf("访问顶点: %d --- %c\n", v, G.vexs[v]);EnQueue_Sq(queue, v);while (!QueueEmpty_Sq(queue)) {DeQueue_Sq(queue, u);    // 出队操作 for (int w = 0; w < G.vexnum; w++) {if (G.arcs[u][w] != 0 && !visited[w]) {visited[w] = 1;printf("访问顶点: %d --- %c\n", w, G.vexs[w]);EnQueue_Sq(queue, w);}}}DestroyQueue_Sq(queue);
}// 广度优先遍历邻接矩阵的主函数
void BFSMTraverse(AMGraph &G) {int v, visited[MaxVerNum];for (v = 0; v < G.vexnum; v++) {visited[v] = 0;}for (v = 0; v < G.vexnum; v++) {if (!visited[v]) {printf("顶点 %c 为起点的广度优先遍历:\n", G.vexs[v]);BFSM(G, v, visited);}}
}// 广度优先搜索遍历函数(图的存储结构采用邻接表表示)
// 第1个形参 ALGraph &G是指要遍历的图的存储结构
// 第2个形参int v是指从序号为v的顶点开始广度优先遍历图
// 第3个形参int visited数组，指示顶点是否被访问过
void BFSL(ALGraph &G, int v, int visited[]) {c_SeqQ *queue = NULL;               // 定义一个顺序队列InitQueue_Sq(queue);                // 初始化队列QElemType u;ArcNode *p;                         // 定义边指针visited[v] = 1;                     // 标识序号为 v 的顶点被访问过printf("访问顶点: %d --- %c\n", v, G.vertices[v].data); // 输出正访问的顶点if (EnQueue_Sq(queue, v) == 0) {    // 把表头访问过的点放入队列中printf("队溢出，操作错误，结束!\n");exit(1);                        // 队列满，溢出}while (!QueueEmpty_Sq(queue)) {     // 队列不空DeQueue_Sq(queue, u);p = G.vertices[u].firstarc;while (p) {                                      // 遍历顶点v的所有邻接点if (visited[p->adjvex] == 0) {               // 判断p->adjvex顶点是否被访问过visited[p->adjvex] = 1;                  // 若没被访问过，则对其进行访问printf("访问顶点: %d --- %c\n", p->adjvex, G.vertices[p->adjvex].data); // 输出正访问的结点if (EnQueue_Sq(queue, p->adjvex) == 0) { // 把访问过的点放入队列中printf("队溢出，操作错误，结束!\n");exit(1);                             // 队列满，溢出}}p = p->nextarc; // 指向下一个相邻顶点}}DestroyQueue_Sq(queue); // 删除队列
}// 广度优先遍历图（图的存储结构采用邻接表表示）
void BFSLTraverse(ALGraph &G) {int v, visited[MaxVerNum];// 初始化 visited 数组，该数组每一个元素对应图的一个顶点，用来标识顶点是否被访问过for (v = 0; v < G.vexnum; v++) {visited[v] = 0;}// 遍历所有顶点，对未访问的顶点执行 BFS 搜索for (v = 0; v < G.vexnum; v++) {if (!visited[v]) {printf("顶点 %c 为起点的广度优先遍历:\n", G.vertices[v].data);BFSL(G, v, visited); // v 未访问过，从 v 开始 BFS 搜索}}
}// 显示菜单
void showmenu() {printf("\n\n\n"); printf("\t*                  --图的遍历--                  *\n");printf("\t**************************************************\n");printf("\t*    1---------用邻接矩阵表示一个图              *\n");printf("\t*    2---------用邻接表表示一个图                *\n");printf("\t*    3---------深度优先搜索遍历图（邻接矩阵）    *\n");printf("\t*    4---------深度优先搜索遍历图（邻接表）      *\n");printf("\t*    5---------广度优先搜索遍历图（邻接矩阵）    *\n");printf("\t*    6---------广度优先搜索遍历图（邻接表）      *\n");printf("\t*                                                *\n");printf("\t*    0---------退出                              *\n");printf("\t**************************************************\n");}// 图的操作
void graphOP() {char choice = 'N';int adjacency_matrix = 0; // 标志邻接矩阵是否存在int adjacency_list = 0;   // 标志邻接表是否存在AMGraph G;                // 邻接矩阵ALGraph T;                // 邻接表while (choice != '0') {printf("\n请选择菜单号(0--6): ");scanf(" %c", &choice);switch (choice) {case '1':CreateAMGraph(G); // 创建图的邻接矩阵adjacency_matrix = 1;break;case '2':CreateALGraph(T); // 创建图的邻接表adjacency_list = 1;break;case '3':             // 深度优先搜索遍历图（邻接矩阵）if (adjacency_matrix) {DFSMTraverse(G);} else {printf("请先输入图的顶点信息!\n");}break;case '4':             // 深度优先搜索遍历图（邻接表）if (adjacency_list) {DFSLTraverse(T);} else {printf("请先输入图的顶点信息!\n");}break;case '5':             // 广度优先搜索遍历图（邻接矩阵）if (adjacency_matrix) {BFSMTraverse(G);} else {printf("请先输入图的顶点信息!\n");}break;case '6':             // 广度优先搜索遍历图（邻接表）if (adjacency_list) {BFSLTraverse(T);} else {printf("请先输入图的顶点信息!\n");}break;case '0':printf("\n\t 程序结束! \n");break;default:printf("\n\t 输入错误, 请重新输入! \n");}}
}int main() {
showmenu();
graphOP();
}

2.运行结果：
在这里插入图片描述
这里以无向图的邻接矩阵为例
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

	// 输出邻接矩阵 for (i = 0; i < G.vexnum; i++) {for (j = 0; j < G.vexnum; j++) printf("%d ", G.arcs[i][j]);printf("\n"); }

在这里插入图片描述
输出：
在这里插入图片描述

3.调试：
图空测试：
未创建图并尝试从图中弹出元素，验证程序是否能够正确检测到图空并输出相应的提示信息。
预期结果：程序应提示“请先输入图的顶点信息!”并阻止弹出操作。
在这里插入图片描述

输入信息错误调试：
输入不存在的顶点的边信息，验证程序是否能够正确检测到顶点信息错误并输出相应的提示信息。
预期结果：程序应提示“输入出错”，并重新输入边的信息。
在这里插入图片描述

总结

不同表示法表示同一个图，其深度优先遍历与广度优先遍历的结果分别相同，即同一个图的邻接表和邻接矩阵的深度优先遍历结果相同，广度优先遍历的结果也相同。

如果你觉得这篇文章对你有所启发，请为博客点赞👍、收藏⭐️、评论💬或分享🔗，你的支持是Tubishu不断前行的源泉✨！衷心感谢你的鼓励与陪伴🙏！
若你有任何疑问、见解或补充，欢迎随时留言💬，让我们在交流中共同成长📚！❤️
愿各位大佬们在技术的道路上，代码顺畅无阻💻，思路清晰如光💡，不断突破自我，向着更高的目标迈进，实现自己的梦想！🎉
再次感谢你的阅读🌸


http://www.ppmy.cn/news/1565586.html

相关文章

python学opencv|读取图像（三十九 ）阈值处理Otsu方法

python学opencv|读取图像（三十九 ）阈值处理Otsu方法

【1】引言 前序学习了5种阈值处理方法&#xff0c;包括(反)阈值处理、(反)零值处理和截断处理&#xff0c;还学习了一种自适应处理方法&#xff0c;相关文章链接为&#xff1a; python学opencv|读取图像&#xff08;三十三&#xff09;阈值处理-灰度图像-CSDN博客 python学o…
阅读更多...
数据库性能优化(sql优化)_索引详解04_深入理解B+树_yxy)

数据库性能优化(sql优化)_索引详解04_深入理解B+树_yxy)

数据库性能优化_深入理解B+树 1 通过代码方式解释B+树1.1 查找操作1.2 插入操作1.3 删除操作1.4 更新操作2 组合索引的查找逻辑2.1 等值查找2.1 范围查找1 通过代码方式解释B+树 B树索引在增删改操作时，底层结构会发生相应的变化，以保持树的平衡和有序性。 下面通过简单的伪…
阅读更多...
【云南省乡镇界】面图层shp格式arcgis数据乡镇名称和编码+wgs84坐标无偏移内容测评

【云南省乡镇界】面图层shp格式arcgis数据乡镇名称和编码+wgs84坐标无偏移内容测评

新2020年乡镇界面图层shp格式arcgis数据乡镇名称和编码wgs84坐标无偏移。arcgis直接打开&#xff0c;单独乡镇界一个图层。品质高
阅读更多...
如何优化企业的CRM流程管理？

如何优化企业的CRM流程管理？

一、了解你的客户&#xff1a;建立深度关系 首先&#xff0c;咱们得明白一点——企业与客户的每一次互动都是一次宝贵的沟通机会。就像我们跟朋友聊天一样&#xff0c;你不可能一开始就聊得很深吧&#xff1f;所以&#xff0c;在和新客户打交道的时候&#xff0c;千万别着急推…
阅读更多...
【漏洞复现】|方正畅享全媒体新闻采编系统reportCenter.do/screen.do存在SQL注入

【漏洞复现】|方正畅享全媒体新闻采编系统reportCenter.do/screen.do存在SQL注入

漏洞描述 方正畅享全媒体新闻采编系统reportCenter.do存在SQL注入漏洞&#xff0c;未经身份验证的恶意攻击者利用SQL注入漏洞获取数据库中信息。 资产概要 app"FOUNDER-全媒体采编系统" 漏洞复现 POST /newsedit/report/reportCenter.do HTTP/1.1 Host: User…
阅读更多...
web服务器 网站部署的架构

web服务器 网站部署的架构

WEB服务器工作原理 Web web是WWW(World Wide Web)的简称&#xff0c;基本原理是&#xff1a;请求(客户端)与响应(服务器端)原理&#xff0c;由遍布在互联网中的Web服务器和安装了Web浏览器的计算机组成 客户端发出请求的方式&#xff1a;地址栏请求、超链接请求、表单请求 …
阅读更多...
ue5 在一个蒙太奇的上半身插槽放两段动画，用片段1，2作为区分。播放动画蒙太奇，自由选择片段1，2

ue5 在一个蒙太奇的上半身插槽放两段动画，用片段1，2作为区分。播放动画蒙太奇，自由选择片段1，2

如图 在一个蒙太奇中&#xff0c;上半身插槽放入两段动画&#xff0c;新建1&#xff0c;2片段。拖到如图位置 角色蓝图 运行成功&#xff0c;只播放第2段动画
阅读更多...
GCPAAS/DashBoard：完全免费的仪表盘设计，基于Vue+ElementUI+G2Plot+Echarts，开源代码，简单易用！还在等什么呢

GCPAAS/DashBoard：完全免费的仪表盘设计，基于Vue+ElementUI+G2Plot+Echarts，开源代码，简单易用！还在等什么呢

嗨&#xff0c;大家好&#xff0c;我是小华同学&#xff0c;关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 GCPAAS/DashBoard&#xff0c;一款基于SpringBoot、MyBatisPlus、ElementUI、G2Plot、Echarts等技术栈的仪表盘设计器&#xff0c;具备仪表盘目录管理…
阅读更多...
最新文章

Copyright @ 2022~2023