实验 3：图形数据结构的实现与应用

news/2024/7/20 20:39:21 标签: 数据结构, 算法, 深度优先
  • 东莞理工学院的同学可以借鉴，请勿抄袭

1.实验目的

通过实验达到：

  1. 理解和掌握图的基本概念、基本逻辑结构；

  2. 理解和掌握图的邻接矩阵存储结构、邻接链表存储结构；

  3. 理解和掌握图的 DFS、BFS 遍历操作的思想及其实现；

  4. 加深对堆栈、队列的概念及其典型操作思想的理解；

  5. 理解和掌握图的应用-最小生成树、最短路径算法的思想及其实现；

  6. 掌握典型图操作算法的算法分析。

2. 实验题目：图的建立、遍历及其应用

设图结点的元素类型为 ElemType(可以为 char 或 int)，通过文件读取方式， 建立一个不少于10个顶点的带权无向图G，实现以下图的各种基本操作的程序：

① 用邻接矩阵作为储结构存储图 G 并输出该邻接矩阵；

② 用邻接链表作为储结构存储图 G 并输出该邻接链表；

③ 按深度优先遍历(DFS)算法输出图 G 中顶点的遍历序列；

④ 按广度优先遍历(BFS)算法输出图 G 中顶点的遍历序列；

⑤ 使用 Prime 算法(或者 Kruskal 算法)从某个指定的顶点出发输出图 G 的 最小生成树；（要求把最小生成树的各条边输出成 A-B-wight,或者 (A,B,weight)的形式）；

⑥ 求从有向图的某个节点出发到其余各顶点的最短路径和最短路径值； （带权有向图）；

⑦ 主函数通过菜单选择函数调用实现以上各项操作，请在实验报告中请画 出设计的图。

附加题：（每完成一个额外附加 5 分，上限 10 分）

① 编写函数求邻接矩阵存储结构的有向图 G 中各顶点的入度和出度；

② 用狄克斯特拉（Dijkastra）算法或者 Floyd 算法求每对顶点之间的最 短路径；（带权有向图）。

一个无向图的例子,可以把此图扩展作为实验用图：

在这里插入图片描述

2.1. 数据结构设计

typedef char ElemType;

typedef struct GraphByMatrix {
	//顶点数组
	ElemType* arrayV;

	//邻接矩阵
	int** matrix;

	//有向or无向
	int isDirect;

	int size;

}GraphByMatrix;

typedef struct Node {
	int src;
	int dest;
	int weight;
	struct Node* next;
}Node;

typedef struct GraphByList {
	Node** edges;
	ElemType* arrayV;
	int isDirect;
	int size;//顶点个数
}GraphByList;

2.2. 主要操作算法设计与分析

2.2.1. 读文件建立邻接矩阵并输出

GraphByMatrix* createMByFile(char* file);

GraphByMatrix* createGByM(ElemType* arrayV, int n, int flag);

int getIndexM(GraphByMatrix* pg, ElemType v);

void addEdgeM(GraphByMatrix* pg, ElemType v1, ElemType v2, int weight)

void printMatrix(GraphByMatrix* pg)

返回类型：GraphByMatrix*；

是否有参数：char* file，（文件名）

步骤：

  1. 根据固定的文件格式读取对应信息
  2. 第一个整数为顶点的个数，空格分割后是一个字符串，是顶点，然后一个回车，每行一条边，边的格式为起始顶点 + 空格 + 目的顶点 + 空格 + 权重
  3. 定义getIndexM函数，获取顶点在邻接矩阵中的下标
  4. 定义createGByM函数通过文件构造不包含权重的邻接矩阵初始化版本
  5. 定义addEdgeM函数给邻接矩阵增加边，循环读取文件直到结束
  6. 读取文件结束后，返回邻接矩阵
  7. 通过printMatrix函数打印邻接矩阵

算法时间复杂度：

  • 时间复杂度为O(N);
  • 空间复杂度为O(N2);

2.2.2 读文件建立邻接链表并输出

Node* newNode(int src, int dest, int weight);

GraphByList* createGByL(ElemType* arrayV, int n, int flag);

GraphByList* createLByFile(char* file);

int getIndexL(GraphByList* pg, ElemType v);

void addEdgeL(GraphByList* pg, ElemType src, ElemType dest, int weight);

void printList(GraphByList* pg);

返回类型：GraphByList*；

是否有参数：char* file，（文件名）

步骤：

  1. 根据固定的文件格式读取对应信息
  2. 第一个整数为顶点的个数，空格分割后是一个字符串，是顶点，然后一个回车，每行一条边，边的格式为起始顶点 + 空格 + 目的顶点 + 空格 + 权重
  3. 定义getIndexL函数，获取顶点在邻接表中的下标
  4. 定义createGByL函数通过文件构造不包含权重的邻接表初始化版本，即数组的值都为null，暂无链表的情况
  5. 定义addEdgeL函数，为邻接表增加边，在顶点对应下标的数组的链表上头插一个节点，这个节点由newNode函数构造
  6. 文件读完后返回邻接表
  7. 通过printList函数打印邻接表

算法时间复杂度：

  • 时间复杂度为O(N);
  • 空间复杂度为O(N);

2.2.3. 按深度优先遍历(DFS)算法输出图 G 中顶点的遍历序列

void dfs(GraphByMatrix* pg, ElemType v);

void dfsOrder(GraphByMatrix* pg, int src, int* isVisited);

返回类型：无返回值；

是否有参数：有，GraphByMatrix*邻接矩阵，char 起始顶点

步骤：

  1. 定义一个数组标记顶点是否被打印过，调用getIndexM函数获取顶点对应的下标
  2. 调用递归函数dfsOrder，传入邻接矩阵，下标，标记数组
  3. 打印过的则不能再打印，由于是连通图，所以任何一个顶点都能够打印所有顶点
  4. 一直递归至结束，回到dfs函数，释放临时的空间

算法时间复杂度：

  • 时间复杂度为O(N);
  • 空间复杂度为O(N);

2.2.4. 按广度优先遍历(BFS)算法输出图 G 中顶点的遍历序列

导入一个队列结构体Queue与其基本方法 ；（见附件）

void bfs(GraphByMatrix* pg, ElemType v);

返回类型：无返回值；

是否有参数：有，GraphByMatrix*邻接矩阵，char 起始顶点

步骤：

  1. 定义一个队列对象
  2. 定义一个数组标记顶点是否被打印过，调用getIndexM函数获取顶点对应的下标
  3. 让下标入队列
  4. 进入循环，出队列一个元素并打印，标记数组标记其打印过，循环此顶点所连顶点入队列，并标记数组为打印过（两层保证，防止打印多次）
  5. 直到队列为空，循环结束，释放临时的空间

算法时间复杂度：

  • 时间复杂度为O(N);
  • 空间复杂度为O(N);

2.2.5. 使用 Prime 算法输出图 G 的 最小生成树

导入一个优先级队列结构体PriorityQueue与其基本方法 ；（见附件）

定义一个Edge类，代表边

typedef struct Edge {
	int src;
	int dest;
	int weight;
}Edge;
Edge newEdge(int src, int dest, int weight) {
	Edge e = { src, dest, weight };
	return e;
}

void prime(GraphByMatrix* pg, ElemType v);

无返回值，有参数，邻接矩阵和起始顶点

步骤：

  1. 获取顶点下标
  2. 申请两部分空间，一部分代表起始顶点集合，一部分代表目的顶点集合，并进行初始化
  3. 定义一个优先级队列，并将v对应的所有边都入堆
  4. 进入循环，取出堆顶元素，如果这条边的起始顶点不存在于起始顶点集合，则可以打印这条边，打印后将此起始顶点加入起始顶点集合，目的顶点集合删除这个顶点，将此目的顶点的所有边都入堆
  5. 直到堆为空或者打印的边数为n-1，退出循环，释放临时的资源

复杂度分析：

时间复杂度：O(N2)

空间复杂度：O(N)

2.2.6. SPFA最短路径

导入队列结构体Queue及其基本方法；（见附件）

void SPFA(GraphByMatrix* pg, ElemType src, int* dist, int* path)

void printPath(GraphByMatrix* pg, int* dist, int* path, int srcIndex)

void printMinPath(GraphByMatrix* pg, ElemType v);

无返回值，传入邻接矩阵，起始顶点，dist最短路径长数组，path路径数组

步骤：

  1. 在printMinPath中，定义dist和path数组
  2. 调用SPFA函数，传入dist和path
  3. 在SPFA函数中，对dist和path进行初始化
  4. 定义一个队列
  5. 将起始顶点入队列
  6. 进入循环，每次取出队头元素，进行松弛操作，松弛成功，将其目的顶点入队列
  7. 直到队列为空
  8. 调用printPath打印最短路径

复杂度分析：

时间复杂度：O(NM)

空间复杂度：O(N)

2.2.7. 输出各顶点的入度和出度

void printDevOfV(GraphByMatrix* pg, ElemType v)

void printDevs(GraphByMatrix* pg, ElemType v)

无返回值，传入邻接矩阵，无意义参数v（故意构造这个参数列表，后面可以用函数指针数组节省代码长度）

步骤：

  1. 循环n次，调用printDevOfV函数，传入邻接矩阵和顶点
  2. 获取顶点下标，计算其入度边数和出度边数，在这里要区分无向图和有向图~

复杂度分析：

时间复杂度：O(N)

空间复杂度：O(1)

2.2.8. Floyd 算法求每对顶点之间的最 短路径；

void floydWarShall(GraphByMatrix* pg, int** dist, int** path);

void printMinPaths(GraphByMatrix* pg, ElemType v);

无返回值，传入邻接矩阵，无意义参数v（故意构造这个参数列表，后面可以用函数指针数组节省代码长度）

步骤：

  1. 定义二维数组dist和二维数组path
  2. 掉头floydWarShall函数，传入这些参数，在这个函数中，首先要对二维数组初始化
  3. 在经历三层循环（最外层循环是中间节点），进行n3次松弛
  4. 循环结束返回到printMinPaths函数，循环n次调用printPath函数打印每一个顶点的最短路径
  5. 最终释放临时资源

复杂度分析：

时间复杂度：O(N3)

空间复杂度：O(N2)

2.2.9. 主函数菜单和测试设计

#include "basis.h"


void menu1() {
	printf("***************************\n");
	printf("0. 退出\n");
	printf("1. 有向图示例\n");
	printf("2. 无向图示例\n");
	printf("***************************\n");
}

void menu2() {
	printf("***************************\n");
	printf("0. 退出\n");
	printf("1. 输出邻接矩阵\n");
	printf("2. 输出邻接表（出度表）\n");
	printf("3. DFS\n");
	printf("4. BFS\n");
	printf("5. 获取最小生成树\n");
	printf("6. 获取最短路径\n");
	printf("7. 获取顶点的入度和出度\n");
	printf("8. 获取多元最短路径\n");
	printf("***************************\n");

}
void test(char* file) {
	GraphByMatrix* pg1 = createMByFile(file);
	GraphByList* pg2 = createLByFile(file);
	void(*p[])(GraphByMatrix*, ElemType) = {
		NULL, NULL, NULL, dfs, bfs, prime,
		printMinPath, printDevs, printMinPaths
	};
	int input = 0;
	do {
		ElemType V = 'A';
		menu2();
		scanf("%d", &input);
		if (input < 0 || input > 8) {
			printf("请重新输入");
			continue;
		}
		switch (input) {
			case 0 :
				printf("退出成功\n");
				break;
			case 1:
				printMatrix(pg1);
				break;
			case 2:
				printList(pg2);
				break;
			default:
				printf("输入起始点:");
				do {
					scanf("%c", &V);
				} while (V == '\n' || V == ' ');
				
			case 7:
			case 8:
				p[input](pg1, V);	
				printf("\n");
				break;
		}
	} while (input);
}

int main() {


	int input = 0;
	do {
		menu1();
		scanf("%d", &input);
		switch (input) {
			case 0:
				printf("退出成功\n");//由于此次后程序就结束了，所以就不free了
				break;
			case 1:
				test("有向图.txt");
				break;
			case 2:
				test("无向图.txt");
				break;
			default:
				printf("请重新输入\n");
				break;

		}

	} while (input);

	return 0;
}

返回int是与否，传入二叉树根节点

步骤：

  • 选择有向图或者无向图实例，然后进行测试

2.2.10. 层序遍历序列构造二叉树(用2.2.9的类似操作)

Node* createTreeByLevelOrder(char string[]);

返回二叉树根节点，传入字符数组

步骤：

  1. 只要数组不为空，就先入队数组首元素，并用这个值创建二叉树的root。
  2. 然后进入循环，循环条件为队列不为空，取出队头元素，队头出队。
  3. 只要数组还有元素，就先给刚刚拿出的对头元素创建左孩子，然后左孩子入队。
  4. 同上，再创建右孩子，右孩子入队。
  5. 结束一次循环。回到2

复杂度分析：

时间复杂度：O(N)

空间复杂度：O(log2N)

2.3. 程序运行过程及结果

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

5. 总结

  • 在这个过程中遇到很多问题，例如空指针异常，结果与预计结果不符
  • 但是只要好好调试，总是能解决问题

6. 附录：源代码

代码仓库地址


http://www.niftyadmin.cn/n/370138.html

相关文章

（详解）Vue3自定义指令

（详解）Vue3自定义指令

目录 一、背景 二、提前预习&#xff08;必看&#xff09; 2.1自定义指令生命周期 2.2 生命周期四个参数 三、 自定义指令 3.1私有自定义指令 3.1.1定义指令 3.1.2使用自定义指令 3.2全局自定义指令 3.2.1定义指令 3.2.2使用自定义指令 一、背景 在我们日常开发中&…
阅读更多...
被比尔盖茨选中的GPT技术，是如何演进，又革谁的命？

被比尔盖茨选中的GPT技术，是如何演进，又革谁的命？

作者 | 智商掉了一地、Python 如果机器能够以类似于人类的方式进行理解和沟通&#xff0c;那会是怎样的情况&#xff1f;这一直是学界中备受关注的话题&#xff0c;而由于近些年来在自然语言处理的一系列突破&#xff0c;我们可能比以往任何时候都更接近实现这个目标。在这个突…
阅读更多...
基于博奇编码的计算全息图及再现研究

基于博奇编码的计算全息图及再现研究

一、引言 全息技术作为一种新的成像技术近年来得到迅速的发展&#xff0c;计算机制全息图不需要实物的存在&#xff0c;同时还能通过计算机实现像的再现。计算全息图主要包括迂回位相型计算全息图和修正离轴参考光计算全息图&#xff0c;这两类全息图由不同的编码方式得到。前…
阅读更多...
可视化库seaborn常用操作介绍

可视化库seaborn常用操作介绍

目录 1.seaborn 概括2.Seaborn的调色板3.单变量绘图分析4.回归分析绘图5.分类图绘制6.FacetGrid使用7.Heatmap 1.seaborn 概括 seaborn库是一个用于数据可视化的Python库&#xff0c;它建立在matplotlib之上&#xff0c;可以让你轻松地创建各种美观的图表和图形。 在seaborn中…
阅读更多...
2023 年面向初学者的 5 大自由写作技巧

2023 年面向初学者的 5 大自由写作技巧

在这篇文章中&#xff0c;我们将讨论初学者的自由写作技巧 译自&#xff1a;https://jitendra.co/freelance-writing-tips-for-beginners/ 比较平易近人&#xff0c;在做独立站并且自己写原创时候可以参考下&#xff0c;面对的甲方爸爸不同而已 最初的兼职活动最终成为我生活中…
阅读更多...
【Unity】Playable使用细则

【Unity】Playable使用细则

【Unity】Playable使用细则 本文基于Unity 2021.3 API。 本文介绍官方文档中没提及的Playable使用限制、注意事项、Bug及规避方案&#xff0c;不是Playable的入门教程&#xff01; 如果你还不熟悉Playable的基础用法&#xff0c;请先学习以下官方文档和示例&#xff1a; Playa…
阅读更多...
Unity小知识

Unity小知识

1.父子关系 在unity里各物体之间可能存在某种关系&#xff0c;有或者没有&#xff0c;我这里介绍父子关系&#xff0c;提到父子关系&#xff0c;就要讲到父子级&#xff0c;父就是主物体&#xff0c;子物体就是副物体。换成我们好理解的话&#xff0c;一个是父亲&#xff0c;一…
阅读更多...
day2 -- MySQL内部模块

day2 -- MySQL内部模块

学习目标 我希望了解一下Mysql的工作原理&#xff0c;实现这个工作原理的各个模块是如何协同工作的。 学习内容 服务端与客户端 服务端与客户端如何通信 存储引擎 存储结构 具体细节 这里先放上Mysql可视化结构&#xff0c;来自B站 服务端 服务端也就是我们常说的Mysql&…
阅读更多...
最新文章

Copyright @ 2022~2023