算法实习报告.doc

《算法实习报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、普里姆(Prim)算法：假设N=（V，{E}）是连通网，V={V1，V2，…，Vn}是网的顶点集合，{E}是N上最小生成树中边的集合。引入顶点集合U和边的集合TE，U的初试状态为{V1}，它存放的是当前所得到的（还未完成的）最小代价生成树上所有顶点，TE的初始状态为{}。在Prim算法的每一步，都从所有的边{(u,v),uÎU,vÎV}中找出所有代价最小的边(u，v)，同时将v并入U，（u，v）并入集合TE，直到U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树。克鲁斯卡尔(Kruskal)算法：假设G=（V，{E}）是一个连通的无向图，其中V={1，2，…，n}，引

2、入辅助集合T，来存放当前所形成的最小生成树的所有边，其初始状态为空，Kruskal算法是逐步给T添加不和T中的边构成回路的当前最小代价边。具体步骤：1、初始化T={};2、当T的边小于n-1时，做如下工作；3、从E(G)中选取代价最小的边(v,u)并删除之；4、若(v,u)不和T中的边一起构成回路，则将边(v,u)并入T中。5、循环2~4步，直到T中所有顶点都在同一个连通图上为止。拓扑排序的计算机实现：方法：采用邻接表作为有向图的存储结构，且在头结点中增加一个有效顶点的入度，入度为零的顶点既为滑有前趋的顶点，删除顶点及弧可以使入度减1。为避免重复检测入度为零的顶点，可另设一链表将所有入度为零的

3、顶点链结到一起，每当输出便删除，反之，当有新的入度为零的顶点则插入，这相当于一个栈。算法：1、查邻接表中入度为零的顶点，并进栈；2、当栈非空时，进行拓扑排序；（1）输出栈顶的顶点Vj并退栈；（2）输出栈顶的顶点Vj的直接后继Vk(k=1,2,…)，将Vk的入度减1，并将入度为0的顶点进栈。（3）若栈空时输出的顶点数不足AOV-网中顶点数n，则说明有向图中存在有向环，否则拓扑排序完毕。StatusTopologicalSort(ALGraphG){FindInDegree(G,indegree);InitStack(S);for(i=0;i

4、))push(S,i);count=0;if(!StachEmpty(s)){pop(S,i);printf(i,G.vertices(i),data);count++;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree(k)))push(S,K);}}if(count

5、Vi的最短路径的长度。其初态为：若从V到Vi有弧，则D(i)为弧上权，否则为无穷大；显然，长度为D(j)=Min{D(i)

6、ViÎV}的路径是从V出发的最短一条路径，此路径为(V,Vj)。网络的可靠性时间限制：3000ms

7、内存限制：65535KB难度：3描述A公司是全球依靠的互联网解决方案提供商，也是2010年世博会的高级赞助商。它将提供先进的网络协作技术，展示其”智能+互联“的生活概念，同时为参观者提供高品质的个人体验和互动，以”信息通信，尽情城市梦想”为主题贯穿。借助奇幻的剧场大屏幕和特效，展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前景。为此，A公司为

8、世博园的N个区域建立了视频通信系统，其中每个区域建立一个基站，编号依次为1，2，3...,N。通过基站之间的通信线路为各区域的参观者提供视频服务。已知在各基站之间已铺设了一些光纤通讯线路，这些线路覆盖了所有的区域，即任意两个区域都可以进行视频传递。但为了节约成本开支，目前只铺设了N-1条线路，同时为了减轻各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。但在通信系统试运行期间，A公司发现当某个基站发生故障时，会导致其它区域之间无法进行信息传递。为了提高该通信网络的可靠性，A公司准备在基站之间再新铺设一些光纤线路，使得任意一个基站故障后，其它基站之间仍然可以通讯。由于铺设线路的成本昂

9、贵，A公司希望新增设的光纤线路越少越好。A公司请求Dr.Kong来完成这个任务输入有多组测试数据，以EOF为结束标志。第一行：N表示有N个基站接下来有N-1行：XY表示第X个基站与第Y个基站直连1<=N<=10000输出输出一个整数，表示至少需新铺设的光纤线路数样例输入813325354562728样例输出3#include#include#include