实验四 图 设计一个简单的医院导航系统

一、实验目的

1. 能利用图的邻接矩阵和邻接表存储表示法构造图；

2. 掌握图的广度和深度优先搜索遍历、最短路径算法思想；

3. 能够用图的算法思想解决生活中的实际应用问题。

二、课程目标

支撑课程目标（3）：能够在工程实践中选择、构建合适的数据结构，描述复杂软件工程问题中的数据及数据之间的关系，体现科学思维能力。

三、实验任务

请设计一个简单的医院导航系统，该医院主要有以下部门：门诊部(A)、住院部(B)、急诊部(C)、药房(D)、收费室(E)、化验室(F)、放射科(G)、手术室(H)、B超室(I)、行政楼(J)，各部门之间的路径及距离如图1所示。

要求：

（1）请利用C/C++/Java语言定义数据类型；

（2）请利用邻接矩阵或邻接表创建带权图，以表示该医院各部门之间的关系；

（3）提供各部门信息查询，如输入“急诊部”，显示“急诊部”相关信息的介绍；

（4）输入任意部门A和部门B的名称，为患者提供从A到B的最短路径

四、实验要求

1. 程序要添加适当的注释，程序的书写要采用缩进格式。

2. 程序要具备一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

3. 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

4. 上传源程序和实验报告到学习通。实验报告命名为：学号姓名实验n.doc，如541713460101白坤鹏-实验1.doc。所有源程序压缩为一个文件，按以下方式命名：学号姓名实验n.rar，如541713460101白坤鹏-实验1.rar。将541713460101白坤鹏-实验1.doc和541713460101白坤鹏-实验1.rar均上传到学习通指定的位置。

五、实验设计（算法设计思路、算法步骤或流程图、核心代码）

//部分代码如下。全码+v:ershiqijian#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_DEPARTMENTS 10
#define INF 999999// 数据类型定义
typedef struct {char name[20];
} Department;typedef struct {int adjacencyMatrix[MAX_DEPARTMENTS][MAX_DEPARTMENTS];int numDepartments;Department departments[MAX_DEPARTMENTS];
} HospitalGraph;// 初始化医院图
void initHospitalGraph(HospitalGraph *graph) {int i, j;// 初始化邻接矩阵for (i = 0; i < MAX_DEPARTMENTS; i++) {for (j = 0; j < MAX_DEPARTMENTS; j++) {if (i == j) {graph->adjacencyMatrix[i][j] = 0;} else {graph->adjacencyMatrix[i][j] = INF;}}}graph->numDepartments = 0;
}// 添加部门
void addDepartment(HospitalGraph *graph, const char *name) {if (graph->numDepartments < MAX_DEPARTMENTS) {strcpy(graph->departments[graph->numDepartments].name, name);graph->numDepartments++;} else {printf("Error: Maximum number of departments reached.\n");}
}// 添加边
void addEdge(HospitalGraph *graph, int from, int to, int distance) {graph->adjacencyMatrix[from][to] = distance;graph->adjacencyMatrix[to][from] = distance;
}// 查询部门信息
void queryDepartmentInfo(HospitalGraph *graph, const char *departmentName) {int i;for (i = 0; i < graph->numDepartments; i++) {if (strcmp(graph->departments[i].name, departmentName) == 0) {printf("Department: %s\n", graph->departments[i].name);return;}}printf("Department not found.\n");
}

六、实验结果（运行效果截图）

七、思考题

1. 图有哪几种存储表示方法？

2. 利用普里姆算法构造的最小生成树是唯一的吗？为什么？

3. 迪杰斯特拉算法用于求单源最短路径，为了求一个图中所有顶点之间的最短路径，可以以每个顶点为源点调用迪杰斯特拉算法实现，弗洛伊德算法和迪杰斯特拉算法相比有什么优势？

1. 邻接矩阵和邻接表。

2. 利用普里姆算法构造的最小生成树是唯一的。这是因为在普里姆算法的每一步中，都选择与当前最小生成树连接的具有最小权重的边，确保了选择的边是唯一的。因此，通过普里姆算法构造的最小生成树是唯一的。

3. 迪杰斯特拉算法用于求单源最短路径，而弗洛伊德算法用于求解图中所有顶点之间的最短路径。它们之间的主要区别和优势包括：

   迪杰斯特拉算法适用于解决单源最短路径问题，而弗洛伊德算法适用于解决所有顶点对之间的最短路径问题。

   迪杰斯特拉算法的时间复杂度较低，是O(V^2)或O((V + E) log V)，其中V是顶点数，E是边数。而弗洛伊德算法的时间复杂度是O(V^3)，其中V是顶点数。

八、实验总结（经验教训，遇到的问题及解决方法，待解决的问题）