用无向网表示某学校的校园平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，边上标注路径长度信息。 （1）以大连大学校园为例，无向网中至少包含8个景点，如图书馆、新理科楼、新文科楼、机关主楼、科技楼、招生就业中心、大学生博物馆、防火通道等。 （2）查询各景点的相关信息。 （3）查询图中任意两个景点间的所有路径。 （4）根据输入的景点，求出图书馆到指定景点的最短路径。 （5）在主函数中调用菜单函数调试程序。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define FALSE -1
#define TRUE 1
#define MAX 20 //最多顶点个数
/*图的种类：DG表示有向图，DN表示有向网，UDG表示无向图，UDN表示无向网*/
typedef enum {
DG, DN, UDG, UDN
} GraphKind;
typedef char vextype; //假设顶点数据为字符型
typedef float adjtype;
typedef struct ArcNode { //对于无权图，用0和1表示是否相邻；对带权图，则为权值类型
int adj;
char info;
} ArcNode;
typedef struct {
vextype vexs[MAX]; // 顶点向量
int arcs[MAX][MAX]; // 邻接矩阵
int vexnum, arcnum; // 图的顶点数和弧数
int mark[8]; // 表记顶点是否被访问过，访问过设置为1，未被访问设置为
char c[8]; // 用于存放路径中的顶点信息
int sumWeight; // 用于存放路径的权的合计值
int weight[8]; // 存放边的权值
} graph;
typedef struct {
char elem[MAX]; // 用来存放栈中元素的以为数组
int top; // 用来存放栈顶元素的下标，top为-1表示空栈
int sumweight; //存放过程全权值
} SeqStack;
int Menu(); // 功能一菜单
void Information(); // 显示每个景点的相关信息
int MenuSelect(); // 菜单驱动程序
int UpdateGraph(graph* G); // 创建图用邻接矩阵表示
int LocateVex(graph* G, vextype v); // 查找顶点v序号
void PrintVInfo(graph* g); // 打印两点之间路径的顶点信息
void DFS(graph* g, int startV, int endV,int a); // 从起点位置出发深度优先周游图g中能访问的各个顶点
void Distence(graph* g, int startV, int endV, int a); // 从图书馆到其他景点间的最短路径
void InitGInfo(graph* G, char m[8]); // 初始化图中的变量信息
int MenuSelect() //菜单驱动程序
{
int sn;
printf(" 实验四运行系统\n"); //显示菜单
printf("==============================\n");
printf(" 1、显示每个景点的相关信息\n");
printf(" 2、求出两景点间的所有路径\n");
printf(" 3、求出图书馆到其他景点间的最短路径\n");
printf(" 4、重置地图的权\n");
printf(" 5、图的邻接矩阵\n");
printf(" 0、退出实验四运行系统\n");
printf("==============================\n");
printf(" 请选择0--5: ");
//菜单功能选择
for (;;) {
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 5)
printf("\n\t 输入选择错误，请重新选择 0--5： ");
else
break;
}
return sn;
}
//功能一菜单
int Menu() {
int sn;
printf(" 学校各个景点的介绍\n"); //显示菜单
printf("==============================\n");
printf(" 1、图书馆\t2、新理科楼\t3、新文科楼\t4、机关主楼\t\n");
printf(" 5、科技楼\t6、招生就业中心\t7、大学生博物馆\t8、防火通道\n");
printf("当输入0时退出\n");
printf("==============================\n");
printf(" 请选择0--8: ");
//菜单功能选择
for (;;) {
scanf("%d", &sn);
getchar();
if (sn < 0 || sn > 8)
printf("\n\t 输入选择错误，请重新选择 0--8： ");
else
break;
}
return sn;
}
//显示每个景点的相关信息
void Information() {
for (;;) // 无限循环,选择0 退出
{
switch (Menu()) // 调用菜单函数，按返回值选择功能函数
{
case 1:
printf(" 图书馆\n");
printf("大连大学图书馆");
break;
case 2:
printf(" 新理科楼\n");
printf("大连大学新理科楼");
break;
case 3:
printf(" 新文科楼\n");
printf(" 大连大学新文科楼\n");
break;
case 4:
printf(" 机关主楼\n");
printf(" 大连大学机关主楼\n");
break;
case 5:
printf(" 科技楼\n");
printf(" 大连大学科技楼\n");
break;
case 6:
printf(" 招生就业中心\n");
printf(" 大连大学招生就业中心\n");
break;
case 7:
printf(" 大学生博物馆\n");
printf(" 大连大学大学生博物馆\n");
break;
case 8:
printf(" 防火通道\n");
printf(" 大连大学防火通道\n");
break;
case 0:
printf(" 再见！\n"); //退出系统
return;
} // switch语句结束
} // for循环结束
}
//查找顶点v序号，无用函数
int LocateVex(graph* G, vextype v) {
int i = 0;
while (G->vexs[i] != v) {
++i;
}
return i;
}
// 更新图的边和权值信息
int UpdateGraph(graph* G) {
char v1, v2;
int i, j, k, w;
printf("更新图的边和权值信息\n");
printf("请输入无向图G弧数:\n");
scanf("%d", &G->arcnum);
getchar(); //缓冲回车
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->arcs[i][j] = 0;
}
}
for (k = 0; k < G->arcnum; k++) {
printf("输入边所对应的顶点和权:(输入边依附的两个顶点及权值)\n");
scanf("%c %c %d", &v1, &v2, &w); // 输入条边依附两点及权值
getchar(); // 缓冲回车
i = LocateVex(G, v1); // 确定顶点V1V2图位置
j = LocateVex(G, v2);
G->arcs[i][j] = w;
G->arcs[j][i] = w;
}
return G->vexnum;
}
// 打印两点之间路径的顶点信息
void PrintVInfo(graph* g) {
int i;
for (i = 0; i < 8; i++) {
if (g->c[i] == '\0') {
break;
}printf("%c ", g->c[i]);
}
printf("\n");
}
/*TODO：找到两个点之间的所有路径
功能描述：从起点位置出发深度优先遍历图g中能访问的各个顶点，找到指定起点到指定终点的路径信息
调用PrintVInfo(graph *g)方法，打印出路径中的顶点信息。
参数说明：g-graph型指针参数
startV-int型起点位置
endV-终点的位置
返回值说明：无
*/
SeqStack Q;
void DFS(graph* g, int startV, int endV,int a) {
int i, j;
g->mark[startV] = 1;
Q.elem[++Q.top] = g->vexs[startV];
for (i = 0; i < g->vexnum; i++){
if (g->mark[i] != 1){
if (g->arcs[startV][i]&& g->vexs[i] == g->vexs[endV]){
for (j = 0; j <= Q.top; j++){
g->c[j] = Q.elem[j];
}
g->c[j] = g->vexs[endV];
g->c[++j] = '\0';
PrintVInfo(g);
continue;
}
if (g->arcs[startV][i]){
DFS(g, i, endV, a + g->arcs[startV][i]);
Q.elem[Q.top--] = 0;
g->mark[i] = 0;
}
}
}
}
/*TODO: 求出图书馆到其他景点间的最短路径
功能描述：遍历图，找从图书馆到指定景点的路径，计算每个路径的权的合计值，找到合计值最小的路径。
g-graph型指针参数
startV-int型起点位置
endV-int型终点位置信息
d-char[]型参数
a-int 路径对应的权的合计
注：参数中d用来存放最短的路径对应的顶点信息，a用来临时存放每条路径对应权的合计值
返回值说明：无
*/
void Distence(graph* g, int startV, int endV, int a) {
int i,j;
g->mark[startV] = 1;
Q.elem[++Q.top] = g->vexs[startV];
for (i = 0;i<g->vexnum;i++){
if (1!=g->mark[i]){
if (g->arcs[startV][i] && g->vexs[i] == g->vexs[endV]){
if (!g->sumWeight){
g->sumWeight = a + g->arcs[startV][i];
for (j = 0; j <= Q.top; j++){
g->c[j] = Q.elem[j];
}
g->c[j] = g->vexs[endV];
g->c[++j] = '\0';
continue;
}
}
if (g->sumWeight > a + g->arcs[startV][i] && g->vexs[i] == g->vexs[endV]&& g->arcs[startV][i]){
g->sumWeight = a + g->arcs[startV][i];
for (j = 0; j <= Q.top; j++){
g->c[j] = Q.elem[j];
}
g->c[j] = g->vexs[endV];
g->c[++j] = '\0';
continue;
}
if (g->arcs[startV][i]){
Distence(g, i, endV, a + g->arcs[startV][i]);
Q.elem[Q.top--]=0;
g->mark[i] = 0;
}
}
}
}
// 初始化图中变量
void InitGInfo(graph* G, char m[8]) {
int i;
for (i = 0; i < 8; i++) {
G->mark[i] = 0;
G->c[i] = '\0';
m[i] = '\0';
G->weight[i] = 0;
}
}
int main() {
graph G;
int i, j, startV, endV, a;
char m[8];
G.vexnum = 8;
G.arcnum = 8;
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
for (i = 0; i < G.vexnum; i++) {
G.vexs[i] = i + 49;//繁琐操作，多余
}
G.arcs[0][1] = 5;
G.arcs[1][0] = 5;
G.arcs[0][2] = 4;
G.arcs[2][0] = 4;
G.arcs[1][2] = 3;
G.arcs[2][1] = 3;
G.arcs[0][3] = 2;
G.arcs[3][0] = 2;
G.arcs[0][4] = 1;
G.arcs[4][0] = 1;
G.arcs[1][5] = 1;
G.arcs[5][1] = 1;
G.arcs[1][7] = 8;
G.arcs[7][1] = 8;
G.arcs[2][6] = 1;
G.arcs[6][2] = 1;
G.arcs[2][5] = 5;
G.arcs[5][2] = 5;
// 无限循环,选择0 退出
for (;;) {
// 调用菜单函数，按返回值选择功能函数
switch (MenuSelect()) {
case 1:
printf("显示每个景点的相关信息\n");
Information(); // 显示每个景点的相关信息
break;
case 2:
printf(" 求出两景点间的所有路径\n");
printf(" 1、图书馆\t2、新理科楼\t3、新文科楼\t4、机关主楼\t\n");
printf(" 5、科技楼\t6、招生就业中心\t7、大学生博物馆\t8、防火通道\n");
printf("请输入起始点：");
scanf("%d", &startV);
startV = startV - 1;
printf("请输入终点：");
scanf("%d", &endV);
endV = endV - 1;
InitGInfo(&G, m);
// 设定起点的信息
G.c[0] = G.vexs[startV];
printf("\n两景点间的路径为：\n");
Q.top=-1;
DFS(&G, startV, endV,0); // 从指定起点出发深度优先周游图g中能访问的各个顶点
printf("\n");
break;
case 3:
printf(" 求出图书馆到其他景点间的最短路径\n"); // 输出通讯者信息的函数调用
printf(" 1、图书馆\t2、新理科楼\t3、新文科楼\t4、机关主楼\t\n");
printf(" 5、科技楼\t6、招生就业中心\t7、大学生博物馆\t8、防火通道\n");
startV = 0;
printf("请输入终点：");
scanf("%d", &endV);
endV = endV - 1;
InitGInfo(&G, m);//将G.c[]，m[]全初始成‘\n’
a = 0;//储存中间权值
G.c[0] = G.vexs[startV]; // 设定起点到m中
G.sumWeight = 0;
Q.top = -1;
Distence(&G, startV, endV,a); // 从图书馆到其他景点间的最短路径
printf("\n最短路径为:");
for (i = 0; i < 8; i++) {
if (G.c[i] == '\0') {
break;
}
printf("%c ", G.c[i]);
}
printf("\n");
break;
case 4:
printf(" 重置地图的权\n");
UpdateGraph(&G);
printf("=============================\n");
break;
case 5:
printf(" 图的邻接矩阵\n");
printf("=============================\n");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
printf("%3d", G.arcs[i][j]);
}
printf("\n");
}
break;
case 0:
printf(" 再见！\n"); // 退出系统
return 0;
} // switch语句结束
} // for循环结束
} // main()函数结束 打赏
支付宝扫一扫
微信扫一扫
