图的最短路径(算法与数据结构课程设计)

小程序820 更新时间：2025-06-08 23:37:38

2023年8月1日发(作者：)

图的最短路径

一、问题描述

最小生成树是一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树时，可以采用普里母算法和克鲁斯卡尔算法。

二、基本要求

1、选择合适的储存结构，完成网的建立；

2、利用普里母算法求网的最少生成树，并输出结果；

3、利用克鲁斯卡尔求网的最少生成树，并输出结果；

4、采用邻接矩阵和邻接表两种储存结构；

三、测试数据

对右图进行测试

右图是6个顶点的10个边的连通图

六个顶点分别是

v1 v2 v3 v4 v5 v6

边和边上的权植分别是

v1 v2 6

v1 v3 1

v1 v4 5

v2 v3 5

v2 v5 3

v3 v4 5

v3 v5 6

v3 v6 4

v4 v6 2

v5 v6 6

wilyes11收集博客(与学习无关)：/u/1810231802 四、算法思想

克鲁斯卡尔算法思想是：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{ }），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。

普里母算法思想是：假设N=（Ｖ，｛Ｅ｝）是连通图，ＴＥ是Ｎ上最小生成树中边的集合。算法从Ｕ＝｛u0｝（u0∈V），TE={ }开始，重复执行下述操作：在所有u∈U，v∈V—U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有ｎ－１条边，则Ｔ＝（Ｖ，｛ＴＥ｝）为Ｎ的最小生成树。为实现这个算法需附设辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域，其中lowcost储存该边的权。显然，closedge[i-1].lowcost=Min{cost(u,vi)|u∈U},vex∈U}, vex 域存储该边依附的在U中的顶点。

五、模块

克鲁斯卡尔算法和普里母算法都要用到以下的算法

int LocateVex(Mgraph G,Vertex u)，矩阵求点u所在位置；

void CreateGraph(Mgraph/ ALGraph &G)，建立带权邻接矩阵/邻接表的结构；

void kruskal2(ALGraph G)，邻接链表的克鲁斯卡尔算法；

void kruskal(MGraph G)，邻接矩阵的克鲁斯卡尔算法；

int minimum(ALGraph/ MGraph G,struct arry wq[])，邻接表/邻接矩阵求最小的权值；

void MiniSpanTree_PRIM1(ALGraph G,VertexType u)，邻接表的普里姆算法；

void MiniSpanTree_PRIM2(MGraph G,VertexType u)，邻接矩阵的普里姆算法。

六、数据结构//(ADT)

1、邻接表的储存结构如下

邻接表的结点结构信息

typedef struct ArcNode{/*定义边结点*/

int adjvex;/*该弧指向的顶点的位置*/

int weight;/*该弧的权重*/

struct ArcNode *nextarc;/*指向下一条弧的指针*/

}ArcNode;

邻接表的表头向量的结点结构信息

typedef struct VNode{

VertexType data; /*顶点信息*/

wilyes11收集博客(与学习无关)：/u/1810231802 ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/

}VNode,AdjList[MAX_VERTEX_NUM];//定义图结点

邻接表的表头带权图的结构信息

typedef struct{

AdjList vertices;/*表头向量*/

int vexnum,arcnum;//顶点数和弧数

}ALGraph;//定义图

2、邻接矩阵的储存结构如下

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

邻接矩阵带权图的结构信息

struct MGraph

{ Vertex vexs[MAX_VERTEX_NUM];/*顶点向量*/

AdjMatrix arcs;/*邻接矩阵*/

int vexnum,arcnum;/*顶点数和弧数*/

};

七、源程序

#include

#define MAX_NAME 5 /*顶点值最大字符数*/

#define MAX_VERTEX_NUM 20 /*最大顶点数*/

typedef char Vertex[MAX_NAME];/*(邻接矩阵用)顶点名字串*/

typedef char VertexType[MAX_NAME];/*(邻接链表用)顶点名字串*/

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

/*链表的结点结构信息*/

typedef struct ArcNode{/*定义边结点*/

int adjvex;/*该弧指向的顶点的位置*/

int weight;/*该弧的权重*/

struct ArcNode *nextarc;/*指向下一条弧的指针*/

}ArcNode;

/*表头向量的结点结构信息*/

typedef struct VNode{

VertexType data;/*顶点信息*/

ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/

}VNode,AdjList[MAX_VERTEX_NUM];//定义图结点

wilyes11收集博客(与学习无关)：/u/1810231802 /*链表带权图的结构信息*/

typedef struct{

AdjList vertices;/*表头向量*/

int vexnum,arcnum;//顶点数和弧数

}ALGraph;//定义图

/*矩阵带权图的结构信息*/

struct MGraph

{ Vertex vexs[MAX_VERTEX_NUM];/*顶点向量*/

AdjMatrix arcs;/*邻接距阵*/

int vexnum,arcnum;/*顶点数和弧数*/

};

struct arry

{ VertexType adjvex;

int lowcost;

}closedge[MAX_VERTEX_NUM];

int LocateVex(MGraph G,Vertex u)//矩阵求点u所在位置

{ int i;

for(i=0;i<;++i)

if(strcmp(u,[i])==0)

return i;

return -1;

}

int LocateVe(ALGraph G,VertexType u)//链表求出点u所在位置

{ int i;

}

/*============================================*/

/*===========邻接矩阵的克鲁斯卡尔算法=========*/

/*============================================*/

void CreateGraph(MGraph &G)//建立带权邻接矩阵结构

{ int i,j,k,w;

Vertex va,vb;

for(i=0;i<;++i)

if(strcmp(es[i].data,u) == 0)

return i;

return -1;

wilyes11收集博客(与学习无关)：/u/1810231802 printf("请输入无向网G的顶点数和边数(分别以空格为分隔):n");

scanf("%d %d",&,&);

printf("请输入%d个顶点的值:n",,MAX_NAME);

for(i=0;i<;++i) /* 读入顶点信息*/

scanf("%s",[i]);

for(i=0;i<;++i)/*初始化邻接矩阵*/

for(j=0;j<;++j)

[i][j]=0x7fffffff;

printf("请输入%d条边各自的起点,终点,权值(分别用空格分隔):n",);

for(k=0;k<;++k)/*读入边*/

{ scanf("%s%s%d",va,vb,&w);

i=LocateVex(G,va);

j=LocateVex(G,vb);

[i][j]=[j][i]=w;/*对称*/

}

/*邻接矩阵的克鲁斯卡尔算法*/

void kruskal(MGraph G)

{ int set[MAX_VERTEX_NUM],i,j;/*set数组用来判断两个点是否在同一个集合里*/

int k=0,a=0,b=0,min=[a][b];

for(i=0;i<;i++)

set[i]=i;

printf("最小代价生成树的各条边为:n");

while(k<-1)

{ for(i=0;i<;++i)

for(j=i+1;j<;++j)

if([i][j]

{

min=[i][j];

a=i;

b=j;

}

min=[a][b]=0x7fffffff;//将最小权值改成最大值

if(set[a]!=set[b])/*若a、b两个点不在同一集合里，则输出a、b之间的边*/

{ /*int s1=set[b];*/

wilyes11收集博客(与学习无关)：/u/1810231802 printf("%s-%sn",[a],[b]);

k++;

for(i=0;i<;i++)//将a、b放在同一集合里

if(set[i]==set[b]/*s1*/)

set[i]=set[a];

}

/*邻接矩阵的克鲁斯卡尔算法*/

void k1(){

MGraph g;

CreateGraph(g);

kruskal(g);

}

/*============================================*/

/*===========邻接链表的克鲁斯卡尔算法=========*/

/*============================================*/

void CreateGraph(ALGraph &G){ //邻接链表创建带权图

int i,j,k,w;

VertexType va,vb;

printf("请输入顶点数,边数(请用空格分开):n"); /*输入顶点数、弧数*/

scanf("%d %d",&,&);

printf("请输入各顶点的值:n");

for(i = 0; i < ; ++i)/*初始化顶点值*/

scanf("%s",es[i].data);

for(i = 0; i < ; ++i)//初始化vertices数组

es[i].firstarc=NULL;

printf("请输入各边的起点,终点,权值(分别用空格分开):n");

for(k = 0; k < ; ++k){

scanf("%s%s%d",va,vb,&w);

i = LocateVe(G,va);/*确定va、vb的位置*/

j = LocateVe(G,vb);

ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); //申请一个结点空间

p->adjvex = j;//初始化

p->weight = w;

wilyes11收集博客(与学习无关)：/u/1810231802

}

p->nextarc = es[i].firstarc;//插表头

es[i].firstarc =p;

ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));

q->adjvex = i;

q->weight = w;

q->nextarc = es[j].firstarc;

es[j].firstarc = q;

/*邻接链表的克鲁斯卡尔算法*/

void kruskal2(ALGraph G){

int i,j,min = 0x7fffffff,k = 0;//min用于记录最小权值

int set[MAX_VERTEX_NUM];//用于判断两个点是否在同一集合里

ArcNode *p,*q,*s;

for(i = 0; i < ; ++i) set[i] = i;//初始化，将每个点自身作为一个集合

while(k < - 1){

for(i = 0; i < ; ++i){

if(es[i].firstarc!=NULL){//若第i+1个点没有领边，则下一循环

for(p=es[i].firstarc;p!=NULL;p=p->nextarc)//查找最小权值的边

}

if(es[j].firstarc == q) es[j].firstarc = q->nextarc;

}

if(p->weight < min){

}

min = p->weight;

q = p;

j = i;

//if-else用于删除最小权值的边

else{

}

if(set[j]!=set[q->adjvex]){//判断两点是否在同一集合,若不在，则输出这条边for(p = es[j].firstarc; p != q; p = p->nextarc) s = p;

s->nextarc = q->nextarc;

printf("(%s,%s) %dn",es[j].data,es[q->adjvex].data,q->weight);

k++;

wilyes11收集博客(与学习无关)：/u/1810231802

}

/*int s2=set[j];*/

for(i=0;i<;i++)

if(set[i]==set[j]/*s2*/)

set[i]=set[q->adjvex];

min = 0x7fffffff; //将min置为最大值

void k2(){

ALGraph G;

CreateGraph(G);

kruskal2(G);

}

/*============================================*/

/*===========邻接矩阵的普里姆算法=========*/

/*============================================*/

int minimum2(MGraph G,struct arry wq[])

{ int i,j;

for(i=0;i<;i++)

if(wq[i].lowcost!=0&&wq[i].lowcost!=0x7fffffff)

break; j=i;

for(i=0;i<;i++)

if(wq[j].lowcost>wq[i].lowcost&&wq[i].lowcost!=0)

j=i;

return j;

}

void MiniSpanTree_PRIM2(MGraph G, VertexType u)

{ int i,j,k;

k = LocateVex (G,u);

for ( j=0; j<; ++j ) {

if (j!=k)

{ strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=[k][j]; }

}

closedge[k].lowcost = 0;

wilyes11收集博客(与学习无关)：/u/1810231802 for (i=1; i<; ++i) {

k = minimum2(G,closedge);

closedge[k].lowcost = 0;

printf("%s%s ",closedge[k].adjvex,[k]);

for (j=0; j<; ++j)

if ([k][j]< closedge[j].lowcost&&closedge[j].lowcost!=0) {

strcpy(closedge[j].adjvex,[k]);

closedge[j].lowcost=[k][j];

}

void k3(){

MGraph g;

CreateGraph(g);

MiniSpanTree_PRIM2(g,"v1");

}

/*============================================*/

/*===========邻接表的普里姆算法=========*/

/*============================================*/

int minimum1(ALGraph G,struct arry wq[])

{

int i,j;

for(i=0;i<;i++)

if(wq[i].lowcost!=0&&wq[i].lowcost!=0x7fffffff)

break; j=i;

for(i=0;i<;i++)

if(wq[j].lowcost>wq[i].lowcost&&wq[i].lowcost!=0)

j=i;

return j;

}

void MiniSpanTree_PRIM1(ALGraph G, VertexType u)

{ int i,j,k;ArcNode *p;

p=(ArcNode*)malloc(sizeof(ArcNode));

k=LocateVe(G,u);

for ( j=0; j<; ++j )

wilyes11收集博客(与学习无关)：/u/1810231802 closedge[j].lowcost=0x7fffffff;

for (j=0;j<;++j )

{ if(strcmp(es[j].data,u) == 0)

{

for(p=es[k].firstarc;p!=NULL;p=p->nextarc)

{ closedge[p->adjvex].lowcost=p->weight;

strcpy(closedge[p->adjvex].adjvex,u);} //for

break;

} //if

}//for

closedge[k].lowcost=0;

for (i=1; i<; ++i){

k = minimum1(G,closedge);

closedge[k].lowcost=0;

printf("%s%s ",closedge[k].adjvex,es[k].data);

for (j=0; j<; ++j)

for(p=es[k].firstarc;p!=NULL;p=p->nextarc)

if(p->weightadjvex==j)

{closedge[j].lowcost=p->weight;

strcpy(closedge[j].adjvex,es[k].data);}

}}

void k4(){

ALGraph G;

CreateGraph(G);

MiniSpanTree_PRIM1(G,"v1");

}

int main()

{ int cord;

do

{printf("n====================================");

printf("n 主菜单 ");

printf("n 1.邻接矩阵实现克鲁斯算法 ");

printf("n 2.邻接链表实现克鲁斯算法 ");

printf("n 3.邻接矩阵实现普里姆算法 ");

printf("n 4.邻接链表实现普里姆算法 ");

wilyes11收集博客(与学习无关)：/u/1810231802 printf("n 5.退出程序 ");

printf("n====================================");

printf("n 请输入您的选择(1,2,3,4,5) cord=");

scanf("%d",&cord);

switch(cord)

{

case 1:k1();break;

case 2:k2();break;

case 3:k3();break;

case 4:k4();break;

case 5:exit(0);

}

}while(cord<=5);

system("pause");

}

八、测试情况

程序的测试结果如下：

邻接矩阵实现克鲁斯卡尔运行结果如下

邻接链表实现克鲁斯卡尔如下

wilyes11收集博客(与学习无关)：/u/1810231802

邻接矩阵实现普利姆算法如下

wilyes11收集博客(与学习无关)：/u/1810231802 邻接链表实现普利姆算法如下

人工验证，都正确

九、参考文献

1、严蔚敏，《数据结构 C语言》，清华大学出版社。

2、谭浩强，《c语言程序设计》，清华大学出版社。

wilyes11收集博客(与学习无关)：/u/1810231802 小结

通过本次课程设计，我学到了很多。要写好一个程序必须弄清他的最基本的思路，除此之外要有算法思路，会写一些基本函数，程序不是一个非要一个主要的函数或者程序要写完，最好有几个函数组成，以便于利用。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等。决定程序成功与否的往往既是有程序的整体思路和整体算法，也要特别注重细节，一个程序没有整体思路和整体算法是写不出来的，但是细节错误往往也是程序成功的观念，小细节的错误导致运行不成功，结果错误，感觉所有的功夫都白费了，我在此次课程设计中深有体会。编程不是轻而易举的，必须要考虑什么储存结构更适合那个算法，本次就用邻接矩阵和邻接表，而没用十字链表，十字链表不合适，而且它的操作相对比较复杂，在小程序中没有优势，还有，算法的实现须要哪些变量，变量中信息又需要哪些，中间算法的需要又用到哪些中间变量，这些没有一定的编程语言的基础和编程经验是无法完成的„„

在写程序的过程中我深刻体会到：如果要写程序，一定要有一定的语言基础知识，此外还要有形成的算法思想及一些基本的储存结构都要会写。没有一点点的语言基础理所当然是写不出来的，所以写程序时感觉到当时应该更努力的学习，深刻的体会到“书到用时方恨少”。邻接表和邻接矩阵的储存结构书上给了一个大概的结构，但是要根据需要辨别储存结构中哪些变量要用，哪些不要用，根据需要来取舍，还有一些变量的在不同的地方用不同的用处，要根据所写程序的需要来辨别他的用处不同即它要保存什么变量。当然此次程序设计中普利姆算法书上有一个大致的结构，所以我是根据书上的程序写的，但是中间有好多的函数要自己独立完成，例如求最小权值minimum函数，在写此函数时我多次出错，最后还是在同学的帮助下完成。

此次我领略到以前学习的知识的重要性和分工合作精神的重要性，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如创建带权的邻接矩阵和邻接表时，我是参考以前程序编写的，但是我要知道相应的的算法中需要哪些变量和函数，进而完成编写。还有编程要实用，求最小生成树是为了求图的最短路径，如我编写的两个算法中，带权的图的邻接矩阵和邻接表中的边，我不仅仅要添加边，还要考虑到边的权值，以求最短的路径。

在本次课程设计中，虽然以前我对两种算法只有一个大概的整体思路，但是没有一个具体详细的思路，尤其是中间的许多函数不是很了解，但在我不断的查看书籍和多次虚心求教下我还是顺利地完成了。求最短路径问题看似是一个很简单的问题，但在实际的程序编写时如果没有学好C语言和数据结构知识是很难完成。例如，算法思想是解决本问题的根本关键，数据结构课本175页有它的介绍。

从这次课程设计中，我了解到知识的重要性，不论是书本的，还是人际交往上的，让我感受颇深！

wilyes11收集博客(与学习无关)：/u/1810231802

2023年8月1日发(作者：)

图的最短路径

一、问题描述

最小生成树是一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树时，可以采用普里母算法和克鲁斯卡尔算法。

二、基本要求

1、选择合适的储存结构，完成网的建立；

2、利用普里母算法求网的最少生成树，并输出结果；

3、利用克鲁斯卡尔求网的最少生成树，并输出结果；

4、采用邻接矩阵和邻接表两种储存结构；

三、测试数据

对右图进行测试

右图是6个顶点的10个边的连通图

六个顶点分别是

v1 v2 v3 v4 v5 v6

边和边上的权植分别是

v1 v2 6

v1 v3 1

v1 v4 5

v2 v3 5

v2 v5 3

v3 v4 5

v3 v5 6

v3 v6 4

v4 v6 2

v5 v6 6

wilyes11收集博客(与学习无关)：/u/1810231802 四、算法思想

克鲁斯卡尔算法思想是：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{ }），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。

普里母算法思想是：假设N=（Ｖ，｛Ｅ｝）是连通图，ＴＥ是Ｎ上最小生成树中边的集合。算法从Ｕ＝｛u0｝（u0∈V），TE={ }开始，重复执行下述操作：在所有u∈U，v∈V—U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有ｎ－１条边，则Ｔ＝（Ｖ，｛ＴＥ｝）为Ｎ的最小生成树。为实现这个算法需附设辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域，其中lowcost储存该边的权。显然，closedge[i-1].lowcost=Min{cost(u,vi)|u∈U},vex∈U}, vex 域存储该边依附的在U中的顶点。

五、模块

克鲁斯卡尔算法和普里母算法都要用到以下的算法

int LocateVex(Mgraph G,Vertex u)，矩阵求点u所在位置；

void CreateGraph(Mgraph/ ALGraph &G)，建立带权邻接矩阵/邻接表的结构；

void kruskal2(ALGraph G)，邻接链表的克鲁斯卡尔算法；

void kruskal(MGraph G)，邻接矩阵的克鲁斯卡尔算法；

int minimum(ALGraph/ MGraph G,struct arry wq[])，邻接表/邻接矩阵求最小的权值；

void MiniSpanTree_PRIM1(ALGraph G,VertexType u)，邻接表的普里姆算法；

void MiniSpanTree_PRIM2(MGraph G,VertexType u)，邻接矩阵的普里姆算法。

六、数据结构//(ADT)

1、邻接表的储存结构如下

邻接表的结点结构信息

typedef struct ArcNode{/*定义边结点*/

int adjvex;/*该弧指向的顶点的位置*/

int weight;/*该弧的权重*/

struct ArcNode *nextarc;/*指向下一条弧的指针*/

}ArcNode;

邻接表的表头向量的结点结构信息

typedef struct VNode{

VertexType data; /*顶点信息*/

wilyes11收集博客(与学习无关)：/u/1810231802 ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/

}VNode,AdjList[MAX_VERTEX_NUM];//定义图结点

邻接表的表头带权图的结构信息

typedef struct{

AdjList vertices;/*表头向量*/

int vexnum,arcnum;//顶点数和弧数

}ALGraph;//定义图

2、邻接矩阵的储存结构如下

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

邻接矩阵带权图的结构信息

struct MGraph

{ Vertex vexs[MAX_VERTEX_NUM];/*顶点向量*/

AdjMatrix arcs;/*邻接矩阵*/

int vexnum,arcnum;/*顶点数和弧数*/

};

七、源程序

#include

#define MAX_NAME 5 /*顶点值最大字符数*/

#define MAX_VERTEX_NUM 20 /*最大顶点数*/

typedef char Vertex[MAX_NAME];/*(邻接矩阵用)顶点名字串*/

typedef char VertexType[MAX_NAME];/*(邻接链表用)顶点名字串*/

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

/*链表的结点结构信息*/

typedef struct ArcNode{/*定义边结点*/

int adjvex;/*该弧指向的顶点的位置*/

int weight;/*该弧的权重*/

struct ArcNode *nextarc;/*指向下一条弧的指针*/

}ArcNode;

/*表头向量的结点结构信息*/

typedef struct VNode{

VertexType data;/*顶点信息*/

ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/

}VNode,AdjList[MAX_VERTEX_NUM];//定义图结点

wilyes11收集博客(与学习无关)：/u/1810231802 /*链表带权图的结构信息*/

typedef struct{

AdjList vertices;/*表头向量*/

int vexnum,arcnum;//顶点数和弧数

}ALGraph;//定义图

/*矩阵带权图的结构信息*/

struct MGraph

{ Vertex vexs[MAX_VERTEX_NUM];/*顶点向量*/

AdjMatrix arcs;/*邻接距阵*/

int vexnum,arcnum;/*顶点数和弧数*/

};

struct arry

{ VertexType adjvex;

int lowcost;

}closedge[MAX_VERTEX_NUM];

int LocateVex(MGraph G,Vertex u)//矩阵求点u所在位置

{ int i;

for(i=0;i<;++i)

if(strcmp(u,[i])==0)

return i;

return -1;

}

int LocateVe(ALGraph G,VertexType u)//链表求出点u所在位置

{ int i;

}

/*============================================*/

/*===========邻接矩阵的克鲁斯卡尔算法=========*/

/*============================================*/

void CreateGraph(MGraph &G)//建立带权邻接矩阵结构

{ int i,j,k,w;

Vertex va,vb;

for(i=0;i<;++i)

if(strcmp(es[i].data,u) == 0)

return i;

return -1;

wilyes11收集博客(与学习无关)：/u/1810231802 printf("请输入无向网G的顶点数和边数(分别以空格为分隔):n");

scanf("%d %d",&,&);

printf("请输入%d个顶点的值:n",,MAX_NAME);

for(i=0;i<;++i) /* 读入顶点信息*/

scanf("%s",[i]);

for(i=0;i<;++i)/*初始化邻接矩阵*/

for(j=0;j<;++j)

[i][j]=0x7fffffff;

printf("请输入%d条边各自的起点,终点,权值(分别用空格分隔):n",);

for(k=0;k<;++k)/*读入边*/

{ scanf("%s%s%d",va,vb,&w);

i=LocateVex(G,va);

j=LocateVex(G,vb);

[i][j]=[j][i]=w;/*对称*/

}

/*邻接矩阵的克鲁斯卡尔算法*/

void kruskal(MGraph G)

{ int set[MAX_VERTEX_NUM],i,j;/*set数组用来判断两个点是否在同一个集合里*/

int k=0,a=0,b=0,min=[a][b];

for(i=0;i<;i++)

set[i]=i;

printf("最小代价生成树的各条边为:n");

while(k<-1)

{ for(i=0;i<;++i)

for(j=i+1;j<;++j)

if([i][j]

{

min=[i][j];

a=i;

b=j;

}

min=[a][b]=0x7fffffff;//将最小权值改成最大值

if(set[a]!=set[b])/*若a、b两个点不在同一集合里，则输出a、b之间的边*/

{ /*int s1=set[b];*/

wilyes11收集博客(与学习无关)：/u/1810231802 printf("%s-%sn",[a],[b]);

k++;

for(i=0;i<;i++)//将a、b放在同一集合里

if(set[i]==set[b]/*s1*/)

set[i]=set[a];

}

/*邻接矩阵的克鲁斯卡尔算法*/

void k1(){

MGraph g;

CreateGraph(g);

kruskal(g);

}

/*============================================*/

/*===========邻接链表的克鲁斯卡尔算法=========*/

/*============================================*/

void CreateGraph(ALGraph &G){ //邻接链表创建带权图

int i,j,k,w;

VertexType va,vb;

printf("请输入顶点数,边数(请用空格分开):n"); /*输入顶点数、弧数*/

scanf("%d %d",&,&);

printf("请输入各顶点的值:n");

for(i = 0; i < ; ++i)/*初始化顶点值*/

scanf("%s",es[i].data);

for(i = 0; i < ; ++i)//初始化vertices数组

es[i].firstarc=NULL;

printf("请输入各边的起点,终点,权值(分别用空格分开):n");

for(k = 0; k < ; ++k){

scanf("%s%s%d",va,vb,&w);

i = LocateVe(G,va);/*确定va、vb的位置*/

j = LocateVe(G,vb);

ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); //申请一个结点空间

p->adjvex = j;//初始化

p->weight = w;

wilyes11收集博客(与学习无关)：/u/1810231802

}

p->nextarc = es[i].firstarc;//插表头

es[i].firstarc =p;

ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));

q->adjvex = i;

q->weight = w;

q->nextarc = es[j].firstarc;

es[j].firstarc = q;

/*邻接链表的克鲁斯卡尔算法*/

void kruskal2(ALGraph G){

int i,j,min = 0x7fffffff,k = 0;//min用于记录最小权值

int set[MAX_VERTEX_NUM];//用于判断两个点是否在同一集合里

ArcNode *p,*q,*s;

for(i = 0; i < ; ++i) set[i] = i;//初始化，将每个点自身作为一个集合

while(k < - 1){

for(i = 0; i < ; ++i){

if(es[i].firstarc!=NULL){//若第i+1个点没有领边，则下一循环

for(p=es[i].firstarc;p!=NULL;p=p->nextarc)//查找最小权值的边

}

if(es[j].firstarc == q) es[j].firstarc = q->nextarc;

}

if(p->weight < min){

}

min = p->weight;

q = p;

j = i;

//if-else用于删除最小权值的边

else{

}

if(set[j]!=set[q->adjvex]){//判断两点是否在同一集合,若不在，则输出这条边for(p = es[j].firstarc; p != q; p = p->nextarc) s = p;

s->nextarc = q->nextarc;

printf("(%s,%s) %dn",es[j].data,es[q->adjvex].data,q->weight);

k++;

wilyes11收集博客(与学习无关)：/u/1810231802

}

/*int s2=set[j];*/

for(i=0;i<;i++)

if(set[i]==set[j]/*s2*/)

set[i]=set[q->adjvex];

min = 0x7fffffff; //将min置为最大值

void k2(){

ALGraph G;

CreateGraph(G);

kruskal2(G);

}

/*============================================*/

/*===========邻接矩阵的普里姆算法=========*/

/*============================================*/

int minimum2(MGraph G,struct arry wq[])

{ int i,j;

for(i=0;i<;i++)

if(wq[i].lowcost!=0&&wq[i].lowcost!=0x7fffffff)

break; j=i;

for(i=0;i<;i++)

if(wq[j].lowcost>wq[i].lowcost&&wq[i].lowcost!=0)

j=i;

return j;

}

void MiniSpanTree_PRIM2(MGraph G, VertexType u)

{ int i,j,k;

k = LocateVex (G,u);

for ( j=0; j<; ++j ) {

if (j!=k)

{ strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=[k][j]; }

}

closedge[k].lowcost = 0;

wilyes11收集博客(与学习无关)：/u/1810231802 for (i=1; i<; ++i) {

k = minimum2(G,closedge);

closedge[k].lowcost = 0;

printf("%s%s ",closedge[k].adjvex,[k]);

for (j=0; j<; ++j)

if ([k][j]< closedge[j].lowcost&&closedge[j].lowcost!=0) {

strcpy(closedge[j].adjvex,[k]);

closedge[j].lowcost=[k][j];

}

void k3(){

MGraph g;

CreateGraph(g);

MiniSpanTree_PRIM2(g,"v1");

}

/*============================================*/

/*===========邻接表的普里姆算法=========*/

/*============================================*/

int minimum1(ALGraph G,struct arry wq[])

{

int i,j;

for(i=0;i<;i++)

if(wq[i].lowcost!=0&&wq[i].lowcost!=0x7fffffff)

break; j=i;

for(i=0;i<;i++)

if(wq[j].lowcost>wq[i].lowcost&&wq[i].lowcost!=0)

j=i;

return j;

}

void MiniSpanTree_PRIM1(ALGraph G, VertexType u)

{ int i,j,k;ArcNode *p;

p=(ArcNode*)malloc(sizeof(ArcNode));

k=LocateVe(G,u);

for ( j=0; j<; ++j )

wilyes11收集博客(与学习无关)：/u/1810231802 closedge[j].lowcost=0x7fffffff;

for (j=0;j<;++j )

{ if(strcmp(es[j].data,u) == 0)

{

for(p=es[k].firstarc;p!=NULL;p=p->nextarc)

{ closedge[p->adjvex].lowcost=p->weight;

strcpy(closedge[p->adjvex].adjvex,u);} //for

break;

} //if

}//for

closedge[k].lowcost=0;

for (i=1; i<; ++i){

k = minimum1(G,closedge);

closedge[k].lowcost=0;

printf("%s%s ",closedge[k].adjvex,es[k].data);

for (j=0; j<; ++j)

for(p=es[k].firstarc;p!=NULL;p=p->nextarc)

if(p->weightadjvex==j)

{closedge[j].lowcost=p->weight;

strcpy(closedge[j].adjvex,es[k].data);}

}}

void k4(){

ALGraph G;

CreateGraph(G);

MiniSpanTree_PRIM1(G,"v1");

}

int main()

{ int cord;

do

{printf("n====================================");

printf("n 主菜单 ");

printf("n 1.邻接矩阵实现克鲁斯算法 ");

printf("n 2.邻接链表实现克鲁斯算法 ");

printf("n 3.邻接矩阵实现普里姆算法 ");

printf("n 4.邻接链表实现普里姆算法 ");

wilyes11收集博客(与学习无关)：/u/1810231802 printf("n 5.退出程序 ");

printf("n====================================");

printf("n 请输入您的选择(1,2,3,4,5) cord=");

scanf("%d",&cord);

switch(cord)

{

case 1:k1();break;

case 2:k2();break;

case 3:k3();break;

case 4:k4();break;

case 5:exit(0);

}

}while(cord<=5);

system("pause");

}

八、测试情况

程序的测试结果如下：

邻接矩阵实现克鲁斯卡尔运行结果如下

邻接链表实现克鲁斯卡尔如下

wilyes11收集博客(与学习无关)：/u/1810231802

邻接矩阵实现普利姆算法如下

wilyes11收集博客(与学习无关)：/u/1810231802 邻接链表实现普利姆算法如下

人工验证，都正确

九、参考文献

1、严蔚敏，《数据结构 C语言》，清华大学出版社。

2、谭浩强，《c语言程序设计》，清华大学出版社。

wilyes11收集博客(与学习无关)：/u/1810231802 小结

通过本次课程设计，我学到了很多。要写好一个程序必须弄清他的最基本的思路，除此之外要有算法思路，会写一些基本函数，程序不是一个非要一个主要的函数或者程序要写完，最好有几个函数组成，以便于利用。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等。决定程序成功与否的往往既是有程序的整体思路和整体算法，也要特别注重细节，一个程序没有整体思路和整体算法是写不出来的，但是细节错误往往也是程序成功的观念，小细节的错误导致运行不成功，结果错误，感觉所有的功夫都白费了，我在此次课程设计中深有体会。编程不是轻而易举的，必须要考虑什么储存结构更适合那个算法，本次就用邻接矩阵和邻接表，而没用十字链表，十字链表不合适，而且它的操作相对比较复杂，在小程序中没有优势，还有，算法的实现须要哪些变量，变量中信息又需要哪些，中间算法的需要又用到哪些中间变量，这些没有一定的编程语言的基础和编程经验是无法完成的„„

在写程序的过程中我深刻体会到：如果要写程序，一定要有一定的语言基础知识，此外还要有形成的算法思想及一些基本的储存结构都要会写。没有一点点的语言基础理所当然是写不出来的，所以写程序时感觉到当时应该更努力的学习，深刻的体会到“书到用时方恨少”。邻接表和邻接矩阵的储存结构书上给了一个大概的结构，但是要根据需要辨别储存结构中哪些变量要用，哪些不要用，根据需要来取舍，还有一些变量的在不同的地方用不同的用处，要根据所写程序的需要来辨别他的用处不同即它要保存什么变量。当然此次程序设计中普利姆算法书上有一个大致的结构，所以我是根据书上的程序写的，但是中间有好多的函数要自己独立完成，例如求最小权值minimum函数，在写此函数时我多次出错，最后还是在同学的帮助下完成。

此次我领略到以前学习的知识的重要性和分工合作精神的重要性，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如创建带权的邻接矩阵和邻接表时，我是参考以前程序编写的，但是我要知道相应的的算法中需要哪些变量和函数，进而完成编写。还有编程要实用，求最小生成树是为了求图的最短路径，如我编写的两个算法中，带权的图的邻接矩阵和邻接表中的边，我不仅仅要添加边，还要考虑到边的权值，以求最短的路径。

在本次课程设计中，虽然以前我对两种算法只有一个大概的整体思路，但是没有一个具体详细的思路，尤其是中间的许多函数不是很了解，但在我不断的查看书籍和多次虚心求教下我还是顺利地完成了。求最短路径问题看似是一个很简单的问题，但在实际的程序编写时如果没有学好C语言和数据结构知识是很难完成。例如，算法思想是解决本问题的根本关键，数据结构课本175页有它的介绍。

从这次课程设计中，我了解到知识的重要性，不论是书本的，还是人际交往上的，让我感受颇深！

wilyes11收集博客(与学习无关)：/u/1810231802

本文发布于:2023-08-01，感谢您对本站的认可！

本文链接:http://torson.com.cn/chengxu/1690857785a448279.html