算法实习报告.docx

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

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

2、前所形成的最小生成的所有，其初始状空，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。避免重复入度零的点，可另一表将所有入度零的点到一起，每当出便除，反之，当有新的入度零的点插入，相当于一个。算法：1、接表中

3、入度零的点，并；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、s(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、长度为D(j)=Min{D(i)

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

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

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

9、新增设的光纤线路越少越好。A公司请求Dr.Kong来完成这个任务输入有多组测试数据，以EOF为结束标志。第一行：N表示有N个基站接下来有N-1行：XY表示第X个基站与第Y个基站直连1<=N<=10000输出输出一个整数，表示至少需新铺设的光纤线路数样例输入813325354562728样例输出3#include#include#includeusingnamespacestd;#definemax10001intresult[max];intmain(){intn,i,a,b;while(scanf("%

10、d",&n)!=EOF){memset(result