最小生成树：这算是最简单的图论算法之一了吧,常用的有Prim和Kruskal算法，对于Prim算法，它 和求最短路径的O(N^2)算法Dijkstra是有相通之处 的。Prim和Kruskal算法的时间效率相差不多，个 人感觉Prim算法容易理解，可以视作涨水的模型来看，的却显得巧妙异常。（以USACO 3.1 Agri-Net 为例） 这道题目是一个标准的最小生成树，不用任何转化 或者优化，Prim算法思想就是不断找点，更新，再找点….算法实现代码如下：
fori:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if (f[j]0) then beginmin:=f[j]; k:=j; end; zong:=zong+min; f[k]:=0; for j:=1 to n do iff[j]>map[k,j] then f[j]:=map[k,j]; end; 事实上，图论算法的代码都是相当死的，若不能理 解，你完全可以将它记下来，做过更难的图论算法 后你才会发现，图论算法的精髓在于建图，而不是 在于算法。
最短路径：最短路径是使用极为频繁的一种图论模 型，其解题主要实现方式是松弛操作，即是先将两 点距离视为极大值，然后用其它点作中转进行优 化，常见的算法有SPFA算法，Dijkstra算法以及 Floyed算法，前两者的时间复杂度为O(N^2)， Floyed算法为O(N^3)，为什么要把一个N^3的算法 放在这里呢，因为其代码极为简洁，如果数据规模 允许的情况下通常采用Floyed算法，事实上， SPFA算法和Dijkstra算法是求单点的距离，Floyed 算法求的是任意两点距离，所以说Floyed的效率与 这两者相比哪个更好还有待讨论啊。 因为spfa可以处理权值为负的情况，所以建议使用spfa算法，spfa算法的模块与宽搜（bfs）的模块 大致相似，也较容易理解： l:=0;r:=1;line[r]:=a;h[a]:=true; repeatinc(l); h[line[l]]:=false; t:=line[l]; for i:=1 to n do begin if(i<>t)and（连接） thenbegin if 松弛 thenbegin 松弛 if h=falsethen begin inc(r); line[r]:=i; h:=true; end;end; end; end; until l>=r; 代码很简单的，至于代码的解释就引用资料上的一 段话“我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是 动态逼近法：设立一个先进先出的队列用来保存待 优化的结点，优化时每次取出队首结点u，并且用u 点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调 整，且v点不在当前的队列中，就将v点放入队尾。 这样不断从队列中取出结点来进行松弛操作，直至 队列空为止。 ” ，具体内容请自行揣摩。 第N短路算法：有了最短路算法，自然要有第N短 路算法，虽然我不知道这在实际应用中有什么用 处，实际上这种变形是很好求解的： *第二最短路径：枚举最短路径上的每条边，每次 删除一条，然后求新图的最短路径，取这些路径中 最短的一条即为第二最短路径。 *同理，第n最短路径可在求解第n-1最短路径的基 础上求解。 那么，怎样枚举最短路的每条边呢，可以想到如果F[1,N]=F[1,K]+F[K,N]，那么K点一定在1到N的最短 路上，那么重复枚举此过程，就可以求得每一条 边，然后再根据上面的步骤求解第N短路即可。代 码就不给了。
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |