题目要求：将如下无向图使用邻接矩阵的方法进行保存，并进行深搜、广搜、建立最小生成树 *** 作。
功能拓展：在实现要求的前提下，进行简单的名称替换、权值替换、找最短路径、删除城市、增加城市、增加航线、删除航线等 *** 作。
模块代码： 1、定位输入城市模块：int LocateVex(AMGraph G, VerTexType u[]) { //查询输入的城市是否在无向图中
for (int i = 0; i < G.vexnum; i++) //在图中循环将输入的城市与顶点一个个对比
if(strcmp(u,G.vexs[i])==0) return i; //如果输入的城市和第i个城市相同，返回i的值
printf("你输入的城市不在该图中n"); //如果输入的城市和顶点城市都不相同，打印"你输入的城市不在该图中",并且返回-1
return -1;
}
2、建立无向图模块：
int CreateUDN(AMGraph& G) { //创建一个无向的航班图
printf("请输入总城市数和总航班数(例如:1 1):");
scanf("%d %d", &(G.vexnum),&(G.arcnum)); //将输入的值分别赋给图中边的个数和顶点个数
for (int i = 0; i < G.vexnum; i++) //利用for循环对图中的顶点进行赋值
{
printf("请输入第%d个城市的名称:",i+1);
scanf("%s", &(G.vexs[i]));
}
for (int i = 0; i < G.vexnum; i++) 将图中所有的边初始化为无穷大
for (int j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
for (int k = 0; k < G.arcnum; k++) { //利用for循环和之前键入的边的个数对边进行赋值
printf("请输入你想输出航班价格的两个城市(例如:北京 哈尔滨):");
char v1[MVNum]; //定义两个字符数组存储输入的城市名称
char v2[MVNum];
scanf("%s %s", &v1,&v2); //将两个城市名称分别赋值给v1,v2数组
int i = LocateVex(G, &v1[0]);
int j = LocateVex(G, &v2[0]);
if(i==-1||j==-1){ //判断输入的城市是否不在图中,若不在图中则退出程序
printf("输入错误,该图中没有这个城市,程序退出执行nnn");
exit(-1);
}
printf("请输入%s和%s两个城市之间的机票价格:",v1,v2);
int w; //定义一个整型变量来存储边的值
scanf("%d",&w); //将输入的值赋给w
G.arcs[i][j] = w; //由于该图是一个无向图,所以要对对称的位置都进行赋值
G.arcs[j][i] = G.arcs[i][j];
}
return OK;
}
3、展示创建的邻接矩阵
char ShowUDN(AMGraph &G){ //展示创建的无向图
printf(" "); //规范格式,使得输出看起来更加整齐
for(int i=0;i
4、深搜模块
int sum;//用来计算机票价格
bool visited[MVNum]; //用来表示结点是否访问过
int DFS(AMGraph G, int v) //对建立的图进行深度优先搜索
{
visited[v]=TRUE; //将本次访问的v对应的位置置为1
printf("%s ",G.vexs[v]); //打印访问的顶点名字
for(int w=0;w
5、广搜模块：
由于广搜需要借助队列，因此将队列也一起放入广搜模块
typedef struct Queue{ //定义队列
int data[MVNum]; //队列大小
int head; //队头
int wei; //队尾
}Queue;
void InitQueue(Queue *q) //初始化队列
{
q->head= 0; //初始化队头、队尾
q->wei = 0;
}
int EmptyQueue(Queue *q) //判断队列是否为空
{
if(q->head == q->wei)
return 1;
else{
return 0;
}
}
void PushQueue(Queue *q,int t) //入队
{
if((q->wei+1)%MVNum == q->head) //说明队列已经满了
return;
else{
q->data[q->wei] = t;
q->wei = (q->wei +1)%MVNum; //队尾后移
}
}
void PopQueue(Queue *q,int *x) //出队
{
if(q->wei == q->head) //出队完毕
return;
else{
*x = q->data[q->head];
q->head = (q->head + 1)%MVNum; //队头后移
}
}
void BFS(AMGraph G) //通过输入的起点城市,对邻接矩阵进行广度优先的遍历
{
int i,j;
int k;
int sum=0;
Queue Q;
for(i=0;i
6、建立最小生成树模块
void prim(AMGraph G,int v) //利用Prim算法,通过输入的起点城市来建立最小生成树
{
int con,row;
int min;
int parent[G.vexnum]={0}; //保存临接顶点下标的数组，所有顶点parent全部赋值为0，将0号顶点（以0号顶点作为第一个顶点）加入生成树
int dist[G.vexnum]; //记录当前生成树到剩余顶点的最小权值
for(row=1;rowNv跳出循环
}
//Graph->Data[parent[b]]为Graph->Data[b]的父母顶点的信息
printf("（%s,%s,%d）n",G.vexs[parent[b]],G.vexs[b],min); //打印信息
dist[b]=0; //将这个顶点加入生成树
//生成树加入了新的顶点从下标为1的顶点开始更新parent数组值
for(a=1;a
7、查找最短路径模块
void shortestway(AMGraph G) //根据输入的两个城市，找到一条机票价格最低的路径并打印
{ int i,j,k;
int a,b;
int d[MVNum][MVNum],path[MVNum][MVNum]; //用来存储最短路径权值和和最短路径的下标
char res1[MVNum],res2[MVNum]; //用来存放输入城市的名称
for(i=0;i%s",G.vexs[a]);
a=path[a-1][b-1];
}
}
8、打印城市模块
void CityShow(AMGraph G){ //打印出所有城市名称
printf("所有城市名称如下:n");
for(int i=0;i
9、查询模块
void CityDirect(AMGraph G){ //查询输入两城市之间是否有直飞航班,若有则输出航班价格
char a[MVNum]; //定义两个字符数组用来记录自己输入的两个城市名称
char b[MVNum];
printf("请输入你想查询的两个城市(例如:北京 成都):");
scanf("%s %s",&a,&b); //将输入的城市名称分别放入a,b中
int i=LocateVex(G,&a[0]); //分别找到a和b对应在邻接矩阵中的下标
int j=LocateVex(G,&b[0]);
if(G.arcs[i][j]!=MaxInt) //如果邻接矩阵中这条边的权值不为定义的无穷大,输出这两个城市间有直飞航班和航班价格
printf("%s和%s两个城市之间有直飞航班,且机票价格为:%d元nnn",G.vexs[i],G.vexs[j],G.arcs[i][j]);
else printf("%s和%s两个城市之间没有直飞航班nnn",a,b); //如果值为无穷大,则输出这两个城市间没直飞航班
}
10、展示航线模块
void ShowDirect(AMGraph G){ //展示所有直飞的航班
for(int i=0;i
11、新增城市模块
void AddVex(AMGraph &G){ //增加一个新城市
char a[MVNum]; //定义用来一个字符数组来记录输入的城市名称
printf("请输入你想增加的城市名称：");
scanf("%s",&a[0]); //将输入的值赋给数组a[]
strcpy(G.vexs[G.vexnum],a); //将新加入的城市名称放在邻接矩阵中
G.vexnum=G.vexnum+1; //使顶点个数增加1
for(int j=0;j
12、删除城市模块
void DelVex(AMGraph &G){ //删除一个城市
char a[MVNum]; //定义用来一个字符数组来记录输入的城市名称
printf("请输入你想删除的城市名称：");
scanf("%s",&a[0]); //将输入的值赋给数组a[]
int i=LocateVex(G,&a[0]); //找到输入城市所在的下标
for(int j=0;j
13、修改航线价格
void Changevalue(AMGraph &G){ //根据输入的城市,修改这两个城市间航班的价格
char a[MVNum]; //创建两个字符数组,用来存放输入的城市名称
char b[MVNum];
int p; //定义一个整型变量,用来存放新机票价格
printf("请输入你想修改航线的城市名称(例如:北京 成都):");
scanf("%s %s",&a,&b); //将输入的城市名称分别赋值给a,b数组
int i=LocateVex(G,&a[0]); //分别找到a,b在图中的位置
int j=LocateVex(G,&b[0]);
printf("请输入修改之后航线的价格:");
scanf("%d",&p); //将新价格赋值给p
G.arcs[i][j]=p; //由于该图双向可通,因此将新航班价格需要放在邻接矩阵的两个位置
G.arcs[j][i]=p;
printf("新航线图的邻接矩阵为:n");
ShowUDN(G); //展示修改航班价格之后的新邻接矩阵
}
14、修改名字模块
void ChangeVexs(AMGraph &G){ //用输入的城市代替之前的城市
char a[MVNum]; //创建一个字符数组,用来存放输入的城市名称
printf("请输入你想修改航线的城市名称:");
scanf("%s",&a); //将输入的城市名称赋值给a数组
int i=LocateVex(G,&a[0]); //找到a在邻接矩阵的位置
printf("请输入修改之后城市的名称:");
scanf("%s",&(G.vexs[i])); //直接将新的城市名称赋给之前的城市名称的位置
printf("新的航线图的邻接矩阵为:n");
ShowUDN(G); //展示改变城市名字之后的邻接矩阵
}
15、增加航线模块
void AddLine(AMGraph &G){ //在现有城市间增加直飞航班
char a[MVNum]; //创建两个字符数组,用来存放输入的城市名称
char b[MVNum];
int p; //定义一个整型变量,用来存放新航班价格
printf("请输入你想增加航线的城市名称(例如:北京 西安):");
scanf("%s %s",&a,&b); //将输入的城市名称分别赋值给a,b数组
int i=LocateVex(G,&a[0]); //分别找到a,b在图中的位置
int j=LocateVex(G,&b[0]);
printf("请输入该航班的价格:");
scanf("%d",&p); //将新价格赋值给p
G.arcs[i][j]=p; //由于该图双向可通,因此将新航班价格需要放在邻接矩阵的两个位置
G.arcs[j][i]=p;
printf("新的航线图的邻接矩阵为:n");
ShowUDN(G); //展示加入新航班之后的邻接矩阵
}
16、删除航线模块
void DeleteLine(AMGraph &G){ //删除现有城市间的直飞航班
char a[MVNum]; //创建两个字符数组,用来存放输入的城市名称
char b[MVNum];
printf("请输入你想删除航线的城市名称(例如:北京 西安):");
scanf("%s %s",&a,&b); //将输入的城市名称分别赋值给a,b数组
int i=LocateVex(G,&a[0]); //分别找到a,b在图中的位置
int j=LocateVex(G,&b[0]);
G.arcs[i][j]=MaxInt; //由于该图双向可通,因此将无穷大的价格需要放在邻接矩阵的两个位置
G.arcs[j][i]=MaxInt;
printf("新的航线图的邻接矩阵为:n");
ShowUDN(G); //展示删除航线之后的新邻接矩阵
}
全部代码：
#include
#include
#include //包含头文件
#define MaxInt 32767 //将无穷大的值定为32767
#define MVNum 10 //设置数组的最大长度为10
#define OK 1 //将OK与TRUE的值定为1
#define TRUE 1
typedef char VerTexType; //将char宏定义为 VerTexType
typedef int ArcType; //将int宏定义为 ArcType
typedef struct { //定义无向图
VerTexType vexs[MVNum][MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
} AMGraph;
int LocateVex(AMGraph G, VerTexType u[]) { //查询输入的城市是否在无向图中
for (int i = 0; i < G.vexnum; i++) //在图中循环将输入的城市与顶点一个个对比
if(strcmp(u,G.vexs[i])==0) return i; //如果输入的城市和第i个城市相同，返回i的值
printf("你输入的城市不在该图中n"); //如果输入的城市和顶点城市都不相同，打印"你输入的城市不在该图中",并且返回-1
return -1;
}
int CreateUDN(AMGraph& G) { //创建一个无向的航班图
printf("请输入总城市数和总航班数(例如:1 1):");
scanf("%d %d", &(G.vexnum),&(G.arcnum)); //将输入的值分别赋给图中边的个数和顶点个数
for (int i = 0; i < G.vexnum; i++) //利用for循环对图中的顶点进行赋值
{
printf("请输入第%d个城市的名称:",i+1);
scanf("%s", &(G.vexs[i]));
}
for (int i = 0; i < G.vexnum; i++) 将图中所有的边初始化为无穷大
for (int j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
for (int k = 0; k < G.arcnum; k++) { //利用for循环和之前键入的边的个数对边进行赋值
printf("请输入你想输出航班价格的两个城市(例如:北京 哈尔滨):");
char v1[MVNum]; //定义两个字符数组存储输入的城市名称
char v2[MVNum];
scanf("%s %s", &v1,&v2); //将两个城市名称分别赋值给v1,v2数组
int i = LocateVex(G, &v1[0]);
int j = LocateVex(G, &v2[0]);
if(i==-1||j==-1){ //判断输入的城市是否不在图中,若不在图中则退出程序
printf("输入错误,该图中没有这个城市,程序退出执行nnn");
exit(-1);
}
printf("请输入%s和%s两个城市之间的机票价格:",v1,v2);
int w; //定义一个整型变量来存储边的值
scanf("%d",&w); //将输入的值赋给w
G.arcs[i][j] = w; //由于该图是一个无向图,所以要对对称的位置都进行赋值
G.arcs[j][i] = G.arcs[i][j];
}
return OK;
}
char ShowUDN(AMGraph &G){ //展示创建的无向图
printf(" "); //规范格式,使得输出看起来更加整齐
for(int i=0;ihead= 0; //初始化队头、队尾
q->wei = 0;
}
int EmptyQueue(Queue *q) //判断队列是否为空
{
if(q->head == q->wei)
return 1;
else{
return 0;
}
}
void PushQueue(Queue *q,int t) //入队
{
if((q->wei+1)%MVNum == q->head) //说明队列已经满了
return;
else{
q->data[q->wei] = t;
q->wei = (q->wei +1)%MVNum; //队尾后移
}
}
void PopQueue(Queue *q,int *x) //出队
{
if(q->wei == q->head) //出队完毕
return;
else{
*x = q->data[q->head];
q->head = (q->head + 1)%MVNum; //队头后移
}
}
void BFS(AMGraph G) //通过输入的起点城市,对邻接矩阵进行广度优先的遍历
{
int i,j;
int k;
int sum=0;
Queue Q;
for(i=0;iNv跳出循环
}
//Graph->Data[parent[b]]为Graph->Data[b]的父母顶点的信息
printf("（%s,%s,%d）n",G.vexs[parent[b]],G.vexs[b],min); //打印信息
dist[b]=0; //将这个顶点加入生成树
//生成树加入了新的顶点从下标为1的顶点开始更新parent数组值
for(a=1;a%s",G.vexs[a]);
a=path[a-1][b-1];
}
}
void CityShow(AMGraph G){ //打印出所有城市名称
printf("所有城市名称如下:n");
for(int i=0;i
代码测试截图：
（1）测试输入航线图：
根据菜单提示，先输入1进行航线图的建立，然后将题目中给的城市个数，航线数，城市名称，航线和航线价格输入进去。
（2）测试查询城市形成的邻接矩阵：
根据菜单提示输入9即可查询城市形成的邻接矩阵。
（3）测试进行深度优先搜索：
根据菜单提示输入4，即可查询深度优先搜索结果。但是由于本系统设置有更改深度优先搜索起点的功能。因此，还要输入深度优先搜索的起点城市，才可展示深度优先搜索的结果。
由于本系统只能输出不考虑返程状态下的总航班费，因此，考虑返程情况下的航线为（海口->昆明->成都->西安->郑州->南京->北京->哈尔滨），总的航班费经过计算可得：520+380+460+220+550+630+860=3620。
因为本次的深度优先搜索并未进行回溯，因此考虑返程和不考虑返程的价格是一样的。
（4）测试进行广度优先搜索：
根据菜单提示，输入11即可进行广度优先搜索。但是由于本系统设置有更改广度优先搜索起点的功能。因此，还要输入广度优先搜索的起点城市，才可展示广度优先搜索的结果。
图20测试进行广度优先搜索的输入和输出
由于本系统只能输出不考虑返程状态下的总航班费，因此，考虑返程情况下航线为（海口->昆明->海口->成都->海口->郑州->海口->南京->海口->成都->西安->成都->海口->郑州->北京->哈尔滨），而总的航班费经过计算可得：
520+520+660+660+830+830+780+780+660+460+460+660+830+220+860=9730。
（5）测试生成最小生成树：
根据菜单提示，输入5即可进行最小生成树查询，由于本系统设置有确定最小生成树起点，因此需要输入起点，之后才能查询最小生成树。
（6）测试查询所有城市名称：
根据菜单提示，输入2，即可查询所有城市名称。
（7）测试查询两城市之间是否有直飞航班：
根据菜单提示输入3即可查询两城市之间是否有直飞航班的程序，再输入两个城市，即可对其进行查询。（该处以一个有直飞航班的测试和一个无直飞测试的截图）
（8）测试查询两城市间的最少航班价格：
根据菜单提醒，输入6即可进入查询两城市间最少航班费用的路线的程序，再输入两个城市名称即可查询。
（9）测试删除一条两城市间的直飞航班：
根据菜单提醒，输入7即可进入删除一条直飞航班的程序，再输入对应航班的城市即可完成这个 *** 作。
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中海口和郑州之间的弧为无穷大。
（10）测试删除一个城市：
根据菜单提醒，输入8即可进入删除一条直飞航班的程序，再输入对应的城市即可完成这个 *** 作。
由图可知，与哈尔滨相连的航班都为无穷大，这就说明哈尔滨成功删除。
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中与哈尔滨有关的弧仍为无穷大。
（11）测试修改城市名称：
根据菜单提醒，输入10即可进入修改城市名称的程序，再输入对应的城市之后输入新城市名称即可完成这个 *** 作。
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中都将只有重庆这个城市没有海口这个城市。
（12）测试显示所有直飞的航班和价格;
根据菜单提醒，输入12即可进入查询所有直飞航班的程序。
（13）测试修改直飞航班的价格：
根据菜单提醒，输入13即可进入修改航班价格的程序，再输入对应的航线的城市之后输入航班的新票价即可完成这个 *** 作。
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中都将显示修改后的价格。
（14）测试增加一条直飞航线
根据菜单提醒，输入14即可进入增加一条直飞航班的程序，再输入对应的航线的城市之后输入新航班的票价即可完成这个 *** 作。
图31测试增加一条直飞航线的输入和输出
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中都将显示含有新航班的图。
（15）测试增加一个新的城市
根据菜单提醒，输入15即可进入增加一个新城市的程序，再输入对应的新城市名称即可完成这个 *** 作。
由于编写的函数将新的图返回给了旧的图，因此在之后的测试中都将显示含有新城市的图。
（16）测试退出系统
根据菜单提醒，输入16即可进入退出系统程序。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）