普里姆(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，引入辅助集合T, 来存放当前所形成的最小生成树的所有边，其初始状态为空，Kruskal算法是逐步给T添加 不和T中的边构成回路的当前最小代价边。具体步骤：1、初始化T= ;2、当T的边小于n-1时，做如下工作；3、从E(G)中选取代价最小的边(v,u)并删除之；4、若(v,u)不和T中的边一起构成回路，贝9将边(v,u)并入T中。5、循环24步，直到T中所有顶点都在同一个连通图上为止。拓扑排序的计算机实现：方法：采用邻接表作为有向图的存储结构，且在头结点中增加一个有效顶点的入度，入度为零的顶点既为滑有前趋的顶点，删除顶点及 弧可以使入度减1。为避免重复检测入度为零的顶点，可另设一链表将所有入度为零的顶点链结到一起，每当输出便删除，反之，当有新的入度为零的顶点则插入，这相当于一个栈。算法：1、查邻接表中入度为零的顶点，并进栈；2、当栈非空时，进行拓扑排序；(1) 输出栈顶的顶点Vj并退栈；(2) 输出栈顶的顶点Vj的直接后继Vk(k=1,2,)，将Vk的入度减1，并将入度为0的顶点进栈。(3) 若栈空时输出的顶点数不足AOV-网中顶点数n,则说明有向图中存在有向环，否则拓扑排序完毕。Status TopologicalSort(ALGraph G)FindInDegree(Gindegree);InitStack(S);for(i=0;ivGVexnum;+i)if(!indegree(i)push(S,i);count=0;if(!StachEmpty(s)pop(S,i);printf(i,Gvertices(i),data);count+;for(p=G.verticesi.firstarc; p ; p=p-nextarc) k=p-adjvex; if(!(-indegree(k) push(S,K);if(countvGvexnum)return ERROR;elsereturn OK;迪杰斯拉特(Dijkstra算法：该算法提出了一个按路径递增的顺序产生最短路径的算法。首先引入一个辅助向量D, 它的分量D(i)表示当前所有找到的从始点V到每个终点Vi的最短路径的长度。其初态为： 若从V到Vi有弧，则D(i)为弧上权，否则为无穷大；显然，长度为D(j)=MinD(i)| Vi V的路径是从V出发的最短一条路径，此路径为(V, Vj )o网络的可靠性时间限制：3000 ms |内存限制：65535 KB难度：3 描述A公司是全球依靠的互联网解决方案提供商，也是2010年世博会的高级赞助商。它将提供 先进的网络协作技术，展示其”智能 +互联“的生活概念，同时为参观者提供高品质的个人 体验和互动，以”信息通信，尽情城市梦想”为主题贯穿。借助奇幻的剧场大屏幕和特效, 展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前 景。为此，A公司为世博园的N个区域建立了视频通信系统，其中每个区域建立一个基站，编 号依次为1, 2, 3.,N。通过基站之间的通信线路为各区域的参观者提供视频服务。已知在各基站之间已铺设了一些光纤通讯线路，这些线路覆盖了所有的区域，即任意两个区 域都可以进行视频传递。但为了节约成本开支，目前只铺设了 N-1条线路，同时为了减轻 各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。但在通信系统试运行期间，A公司发现当某个基站发生故障时，会导致其它区域之间无法进 行信息传递。为了提高该通信网络的可靠性,A公司准备在基站之间再新铺设一些光纤线路, 使得任意一个基站故障后，其它基站之间仍然可以通讯。由于铺设线路的成本昂贵，A公司希望新增设的光纤线路越少越好。A公司请求Dr. Kong 来完成这个任务 输入有多组测试数据，以EOF为结束标志。第一彳丁： N表示有N个基站接下来有N-1行：X Y表示第X个基站与第Y个基站直连lv=Nv=10000输出输出一个整数，表示至少需新铺设的光纤线路数 样例输入81 33 25 35 45 62 72 8样例输出3#includevcstdio#include #includeusing namespace std;#define max 10001int resultmax;int main()int n,i,a,b;while(scanf(%d, &n)!=EOF)memset(result,0,sizeof(result); for(i=0;ivn-1;i+)scanf(%d%d,&a,& b);resulta+; resultb+;int sum=0;for(i=0;iusing namespace std;template Type MaxLoading(Type w,Type c, int n);template class Loadingfriend Type MaxLoading(Type , Type, int);public:void Backtrack(int i); intn;集装箱数量w-集装箱重量数组;c-第一艘轮船的载重量；cw-当前载重量;bestw-当前 最优载重量Type *w,c,cw,bestw;剩余集装箱重量Type r;int main()int *w,c,n,bestw,tc, Maxw=0;输入必要的数据coutvvPlease input the number of Container:; cinn;w=new intn;coutvvPlease input the weight of each container:;for(int i=l;iv=n;i+)cinwi;Maxw+=wi;coutvvPlease input the Maximum weight for the first ship:;cinc;coutvvPlease input the Maximum weight for the second ship:;cintc;调用函数实现回溯法搜索是否可以以最大限度的形式装载集装箱到第一艘船 bestw=MaxLoading(w,c,n);判断第2艘船是否可以装载下剩余的集装箱if(Maxw-bestwtc)coutthe two ship can load all the container:vvendl;elsecoutvvthe two ship cannt load all the containervvendl;return 0;template :Backtrack(int i)如果已到叶子结点if(in)if(cwbestw) bestw=cw;return;搜索子树,减去第i个集装箱的重量为剩余集装箱重量r-=wi;访问左子树if(cw+wibestw)Backtrack(i+1);因为是访问右子树，因此第i个集装箱并不装载到轮船上r+=wi;template Type MaxLoading(Type w,Type c, int n) Loading X;X.w =w;X.c=c;X.n =n;X.bestw=0;X.cw=0;求解剩余集装箱的重量X.r=O;for(int i=l;iv=n;i+)X.r+=wi;X.Backtrack(l);return X.bestw;上述算法只求的了最优解，但具体是元素构成了最优解呢并不知道。因此可通过增加两 个成员变量的方法来记录求解出的最优解。一个是x,另一个是bestx。X用于记录从根到当 前结点的路径，bestx记录当前最优解。/ XModifyMaxLoading.cpp :定义控制台应用程序的入口点。#include stdafx.h#include viostreamusing namespace std;template class TypeType MaxLoading(Type w,Type c, int n,int bestx)