Dijkstra算法实现与分析

1、第第1414页Dijkstrs 算法设计与分析实验Dijkstrs 算法的实现。（英文版Microsoft Visual C+ 6.0实现，并且图的存储结构为邻接表。 本项目的组成结构如图所示 各对应模块的功能如下：asjacent(VNOde v,int belong(int A,int n,int p):dijkstra(Vnode G,int length(Vnode v,int a):main():主函数。min(int r,int Y,int n): 找 出 最 小 的 元 素 的 下 标 . shanchu(int A,int sum,int p): 删除数组中值为p 的元素(覆盖

2、). 对应完整程序： #include #include #define N 6/ 图的接点个数typedef struct ANodeint adjvex;struct ANode *nextarc; int distance; ArcNode;typedef struct VnodeArcNode *firstarc;VNode;int adjacent(VNode v,int a) /判断二接点是否相邻ArcNode *arc=v.firstarc; while(arc!=NULL)if(arc-adjvex=a) return 1;arc=arc-nextarc;return 0;in

3、t length(VNode v,int a) /找出二相邻接点的长度ArcNode *arc=v.firstarc; while(arc!=NULL)if(arc-adjvex=a) return arc-distance; arc=arc-nextarc;return 0;int min(int r,int Y,int n) /找出最小的元素的下标int min=rY0,k=Y0; for(int i=1;in;i+)if(rYimin) min=rYi;k=Yi; return k;void shanchu(int A,int sum,int p) /删除数组中值为 p 的元素(覆盖)

4、for(int i=0;isum;i+)if(p=Ai)if(p!=Asum-1)for(int j=i;jsum-1;j+ Aj=Aj+1;int belong(int A,int n,int p) /判断一个元素是否在指定数组中for(int i=0;in;i+) if(p=Ai) return return 0;void dijkstra(VNode G,int n)int XN=0,YN-1,rN,m=1,q=n-1; /m,qArcNode *arc;for(int Yi-1=i;r0=0;for(int y=1;yn;y+)if(adjacent(G0,y)else ry=6353

5、5;for(int j=0;jadjvex)&(ry+length(Gy,arc-adjvex)adjvex)rarc-adjvex=ry+length(Gy,arc-adjvex); arc=arc-nextarc;for(i=0;in;i+) coutri coutadjvex=2;p-distance=12;p-nextarc=NULL; G0.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=1;p-distance=1;p-nextarc=G0.firstarc; G0.firstarc=p;1 *)malloc(size

6、of(ArcNode);p-adjvex=3;p-distance=3;p-nextarc=NULL; G1.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=2;p-distance=9;p-nextarc=G1.firstarc;G1.firstarc=p;2 *)malloc(sizeof(ArcNode);p-adjvex=4;p-distance=5;p-nextarc=NULL; G2.firstarc=p; 3 *)malloc(sizeof(ArcNode);p-adjvex=5;p-distance=15;p-ne

7、xtarc=NULL; G3.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=4;p-distance=13;p-nextarc=G3.firstarc; G3.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=2;p-distance=4;p-nextarc=G3.firstarc;G3.firstarc=p;/4 *)malloc(sizeof(ArcNode);p-adjvex=5;p-distance=4;p-nextarc=NULL; G4.firstarc=

8、p;/5 6cout0:endl; dijkstra(G,N); 程序执行结果如下：该程序采用教材第 233 页例题作为测试用例，可见能够得到正确结果。 算法分析：采用 Dijkstra 算法求解，其基本思想是：设G（V，E）是一个带权有向图，把图中顶点集合V 分成两组， 第一组为已求出最短路径的顶点集合（用S 表示，初始时Sv,vk 就将vk 加入到集合sS中，算法就结束了，第2次序依次把第二组的顶点加入到sv 到sv 到 U 中任何顶点的最短路径长度。算法的时间的复杂度为O(n2).Prim（英文版Microsoft Visual C+ 6.0 实现，并且图的存储结构为邻接表。 本项目的组

9、成结构如图所示 各对应模块的功能如下：asjacent(VNOde v,int belong(int A,int n,int p): 判断一个元素是否在指定数组中。c(Vnode H,int x,int y):yX,nXprim(Vnode G,int n):main():主函数。min(int c,int Y,int n): 找 出 最 小 的 元 素 的 下 标 . shanchu(int A,int sum,int p): 删除数组中值为p 的元素(覆盖). 对应完整程序： #include #include #define N 6/ 图的接点个数typedef struct ANode

10、int adjvex;struct ANode *nextarc; int distance; ArcNode;typedef struct VnodeArcNode *firstarc;VNode; typedef int int end;elge;int belong(int A,int n,int p) /判断一个元素是否在指定数组中for(int i=0;iadjvex=a) return 1;arc=arc-nextarc;return 0;int c(VNode H,int x,int y) /yX,nXArcNode *arc=Hy.firstarc; while(arc!=NU

11、LL)if(arc-adjvex=x) return arc-distance; arc=arc-nextarc;return 0;int min(int c,int Y,int n) /找出最小的元素的下标int min=cY0,k=Y0; for(int i=1;in;i+)if(cYimin) min=cYi;k=Yi; return k;void shanchu(int A,int sum,int p) /删除数组中值为 p 的元素(覆盖) for(int i=0;isum;i+)if(p=Ai)if(p!=Asum-1)for(int j=i;jsum-1;j+ Aj=Aj+1;vo

12、id prim(VNode G,int n)elge T15;int NeiN,C15,m=1,q=n-1,t=0;/m,q,t素的个数int XN=0,YN-1;ArcNode *arc; for(int i=1;in;i+)Yi-1=i;for(int y=1;y=n-1;y+)if(adjacent(G0,y)Neiy=0;Cy=c(G,0,y);elseCy=63535;for(int j=1;j=n-1;j+)y=min(C,Y,q);t+;Tt-1.source=y;Tt-1.end=Neiy; m+;Xm-1=y;shanchu(Y,q,y);q-; for(i=0;iq;i+)

13、if(adjacent(Gy,Yi)if(c(G,y,Yi)CYi)NeiYi=y;CYi=c(G,y,Yi); for(i=0;it;i+)coutTi.sourceTi.end coutadjvex=2;p-distance=2;p-nextarc=NULL; G0.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=1;p-distance=1;p-nextarc=G0.firstarc; G0.firstarc=p;1 *)malloc(sizeof(ArcNode);p-adjvex=3;p-distance=11;p-ne

14、xtarc=NULL; G1.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=2;p-distance=6;p-nextarc=G1.firstarc; G1.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=0;p-distance=1;p-nextarc=G1.firstarc; G1.firstarc=p;2p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=3;p-distance=9;p-nextarc=NULL; G2.

15、firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=1;p-distance=6;p-nextarc=G2.firstarc; G2.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=0;p-distance=2;p-nextarc=G2.firstarc;G2.firstarc=p; 3 *)malloc(sizeof(ArcNode);p-adjvex=5;p-distance=3;p-nextarc=NULL; G3.firstarc=p;p=(ArcNode *)m

16、alloc(sizeof(ArcNode);p-adjvex=4;p-distance=7;p-nextarc=G3.firstarc; G3.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=2;p-distance=9;p-nextarc=G3.firstarc; G3.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=1;p-distance=11;p-nextarc=G3.firstarc;G3.firstarc=p;4 *)malloc(sizeof(ArcNo

17、de);p-adjvex=5;p-distance=4;p-nextarc=NULL; G4.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=3;p-distance=7;p-nextarc=G4.firstarc; G4.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=2;p-distance=13;p-nextarc=G4.firstarc;G4.firstarc=p; 5 *)malloc(sizeof(ArcNode);p-adjvex=4;p-distanc

18、e=4;p-nextarc=NULL; G5.firstarc=p;p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=4;p-distance=4;p-nextarc=G5.firstarc;G5.firstarc=p; 6prim(G,N); 程序执行结果如下：本题是采用教材第 243 页例题作为测试用例，同时应该注意，对应结点的序号从 0 开始，不是从 1 开始，可见得到正确结果。算法分析经过分析，Prim 算法找到一个具用n 个结点的最小生成树的时间复杂度是（n*n）;KRUSKAL注：本算法来自教材（英文版），在此就省略了，只给出具体实现的程序代

19、码，采用Microsoft Visual C+ 6.0 实现。 本项目的组成结构如图所示 各 对 应 模 块 的 功 能 如 下 ： insertsort(elge A,int kruskal(elge A,int n,int main()：主函数。 对应完整程序： #include #include #define N 6typedef struct int u; /边的起始顶点int v; /边的终止顶点int w; /边的权值elge; /边的数据结构void insertsort(elge A,int n)int i,j;double x;for(i=1;i=0 & Aj.wx)Aj+

20、1.w=Aj.w;j-;Aj+1.w=x;void kruskal(elge E,int n,int e)insertsort(E,n); /Eint i,j,m1,m2,sn1,sn2,k;int vsetN;for(i=0;in;i+)k=1;j=0;while(kn)m1=Ej.u;m2=Ej.v;sn1=vsetm1;sn2=vsetm2; if(sn1!=sn2)/ printf(%d,%d):%dn,m1,m2,Ej.w); coutm1m2 ;k+;for(i=0;in;i+) if(vseti=sn2)vseti=sn1; j+;coutendl;void main(void)

21、elge E9=0,2,2,0,1,1,3,5,3,4,5,4,1,2,6,2,3,9,3,1,11,3,4,7,2,4,13;/elge E10=0,2,1,3,5,2,1,4,3,2,5,4,1,2,5,0,3,5,2,3,5,0,1,6,2,4,6,4,5,6;kruskal(E,N,9); 程序执行结果如下:可以通过修改主函数中数组中那些值来进行测试，同样可以得到正确结果。 算法分析：Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。实现Kruskal 算法的关键是如何判断选取的边是否与生成树中已保留的边形成回路，这可以通过判断边的两个顶点所在的连通分量的方

22、法来解决。Gefron，while en-1O(n2+en-1Kruskal最小生成树的时间复杂度为O(elog2 e).文件压缩算法的实现。注：本算法来自教材（英文版），在此就省略了，只给出具体实现的程序代码，采用Microsoft Visual C+ 6.0 实现，涉及数组存储的都是从下标0 开始。 本项目的组成结构如图所示 各 对 应 模 块 的 功 能 如 下 ： display(Hufnode hf,int huffman(Hufnode hf,int main():主函数。 对应完整程序： #include #define N 5typedef structint fren;/int parent;int lchild; int rchild;Hufnode;/void display(Hufnode hf,int n)for(int i=0;i2*n-1;i+) cout结点的频率：hfi.frenendl;cout结点的父结点：hfhfi.parent.frenendl; cout结点的左孩子：hfhfi.lchild.frenendl; cout结点的右孩子：hfhfi.rchild.frenendl; coutendl;void huffman(Hufnode hf,int n)int