《图的最短路径(算法与数据结构课程设计)》由会员分享，可在线阅读，更多相关《图的最短路径(算法与数据结构课程设计)（14页珍藏版）》请在金锄头文库上搜索。
1、wilyes11 收集 博客(与学习无关) ：http:/ n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树时，可以采用普里母算法和克鲁斯卡尔算法。二、基本要求1、 选择合适的储存结构，完成网的建立；2、 利用普里母算法求网的最少生成树，并输出结果；3、 利用克鲁斯卡尔求网的最少生成树，并输出结果；4、 采用邻接矩阵和邻接表两种储存结构；三、测试数据对右图进行测试右图是 6 个顶点的 10 个边的连通图六个顶点分别是v1 v
2、2 v3 v4 v5 v6边和边上的权植分别是v1 v2 6v1 v3 1v1 v4 5v2 v3 5v2 v5 3v3 v4 5v3 v5 6v3 v6 4v4 v6 2v5 v6 6wilyes11 收集 博客(与学习无关) ：http:/ N=（V，E），则令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T=（V， ），图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。以此类推，直至 T 中所有顶点都在同一连通分量上为止。普里母算法思想是：假设 N=（，）是连通图
3、，是上最小生成树中边的集合。算法从u0（u0V ），TE= 开始，重复执行下述操作：在所有uU，vVU 的边（u，v） E 中找一条代价最小的边（ u0，v0）并入集合 TE，同时 v0并入 U，直至 U=V 为止。此时 TE 中必有条边，则（，）为的最小生成树。为实现这个算法需附设辅助数组 closedge,以记录从 U 到 V-U 具有最小代价的边。对每个顶点 viV-U ，在辅助数组中存在一个相应分量 closedgei-1，它包括两个域，其中 lowcost 储存该边的权。显然，closedgei-1.lowcost=Mincost(u,vi)|uU,vexU,vex 域存储该边依附的
4、在 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(ALGrap
5、h 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 VNodewilyes11 收集 博客(与学习无关) ：h
6、ttp:/ data; /*顶点信息*/ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/VNode,AdjListMAX_VERTEX_NUM;/定义图结点邻接表的表头带权图的结构信息typedef structAdjList vertices;/*表头向量*/int vexnum,arcnum;/顶点数和弧数ALGraph;/定义图2、邻接矩阵的储存结构如下typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/邻接矩阵带权图的结构信息struct MGraph Vertex vexsMAX_VERTEX_
7、NUM;/*顶点向量*/AdjMatrix arcs;/*邻接矩阵*/int vexnum,arcnum;/*顶点数和弧数*/;七、源程序#include#include#include#define MAX_NAME 5 /*顶点值最大字符数*/#define MAX_VERTEX_NUM 20 /*最大顶点数*/typedef char VertexMAX_NAME;/*(邻接矩阵用)顶点名字串*/typedef char VertexTypeMAX_NAME;/*(邻接链表用)顶点名字串*/typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM
8、;/*邻接距阵*/*链表的结点结构信息*/typedef struct ArcNode/*定义边结点*/int adjvex;/*该弧指向的顶点的位置*/int weight;/*该弧的权重*/struct ArcNode *nextarc;/*指向下一条弧的指针*/ArcNode;/*表头向量的结点结构信息*/typedef struct VNodeVertexType data;/*顶点信息*/ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/wilyes11 收集 博客(与学习无关) ：http:/ structAdjList vertices;/*表头向量*/i
9、nt vexnum,arcnum;/顶点数和弧数ALGraph;/定义图/*矩阵带权图的结构信息*/struct MGraph Vertex vexsMAX_VERTEX_NUM;/*顶点向量*/AdjMatrix arcs;/*邻接距阵*/int vexnum,arcnum;/*顶点数和弧数*/;struct arry VertexType adjvex;int lowcost;closedgeMAX_VERTEX_NUM;int LocateVex(MGraph G,Vertex u)/矩阵求点 u 所在位置 int i;for(i=0;iadjvex = j;/初始化p-weight =
10、 w;p-nextarc = G.verticesi.firstarc;/插表头G.verticesi.firstarc =p;ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode);q-adjvex = i;q-weight = w;q-nextarc = G.verticesj.firstarc;G.verticesj.firstarc = q;/*邻接链表的克鲁斯卡尔算法*/void kruskal2(ALGraph G)int i,j,min = 0x7fffffff,k = 0;/min 用于记录最小权值int setMAX_VERTEX_NUM
11、;/用于判断两个点是否在同一集合里ArcNode *p,*q,*s;for(i = 0; i nextarc)/查找最小权值的边if(p-weight weight;q = p;j = i;if(G.verticesj.firstarc = q) G.verticesj.firstarc = q-nextarc; /if-else 用于删除最小权值的边elsefor(p = G.verticesj.firstarc; p != q; p = p-nextarc) s = p;s-nextarc = q-nextarc;if(setj!=setq-adjvex)/判断两点是否在同一集合,若不在，
12、则输出这条wilyes11 收集 博客(与学习无关) ：http:/ printf(%s,%s) %dn,G.verticesj.data,G.verticesq-adjvex.data,q-weight);k+;/*int s2=setj;*/for(i=0;iadjvex;min = 0x7fffffff; /将 min 置为最大值void k2()ALGraph G;CreateGraph(G);kruskal2(G);/*=*/*=邻接矩阵的普里姆算法=*/*=*/ int minimum2(MGraph G,struct arry wq) int i,j;for(i=0;iwqi.l
13、owcost&wqi.lowcost!=0)j=i;return j;void MiniSpanTree_PRIM2(MGraph G, VertexType u) int i,j,k;k = LocateVex (G,u);for ( j=0; jwqi.lowcost&wqi.lowcost!=0)j=i; return j;void MiniSpanTree_PRIM1(ALGraph G, VertexType u) int i,j,k;ArcNode *p;wilyes11 收集 博客(与学习无关) ：http:/ ( j=0; jnextarc) closedgep-adjvex.lowcost=p-weight;strcpy(closedgep-adjvex.adjvex,u); /forbreak; /if/forclosedgek.lowcost=0;for (i=1; inextarc)if(p-weightadjvex=j)closedgej.lowcost=p-weight;strcpy(closedgej.adjvex,G.verticesk.data);void k4()ALGraph G;CreateGraph(G);MiniSpanTree_PRIM1(G,v1);int main() int cord;doprintf(n=);pr
