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