用无向网表示某学校的校园平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,边上标注路径长度信息。 (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()函数结束
打赏
支付宝扫一扫
微信扫一扫