文档介绍：图论算法
1最小生成树算法(Prim算法)
2单源最短路径算法(Dijkstra算法)
3任意结点最短路径算法(Floyd算法)
4求有向带权图的所有环
5Bellman-Ford算法
6计算图的连通性
7计算最佳连通分支
8计算拓扑序列
无向图的生成树就是从图的边集中选择一些边,使得这些边构成一个连通无环图,也就是树。如果给每一条边加一个权,所有生成树中权和最小的生成树称为最小生成树。
【Prim算法思想】
任意时刻的中间结果都是一棵树,每次花费最小的代价,用一条边把不在树中的结点加进来。
【最小生成树算法实例】
    现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。在分析了这张图后发现,任一对城市都是连通的。现在要求用公路把所有城市联系起来,如何设计可使得工程的总造价最少?
【输入】第一行两个数v(v<=200),e,分别代表城市数和边数以下e行,每行为两个顶点和它们之间的边权w(w<1000)。
【输出】 v-1行,每行为两个城市的序号,表明这两个城市间建一条公路,再加该公路的造价。
【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
【输出样例】
1 2 10
2 3 5
2 4 6
2 6 11
4 5 18
原  图
最小生成树
program prim_example;
Const
   vmax=200
var
   w:array[1..vmax,1..vmax]of integer;
   i,j,k,v,e:integer;
procedure prim(v0:integer); {v0是开始结点}
  var
    flag:array[1..vmax] of boolean;
    min,prevk,nextk:integer;
  begin
    fillchar(flag,sizeof(flag),false);
    flag[v0]:=true; {先选出v0}
    for i:=1 to v-1 do {一共寻找v-1条边}
      begin
        min:=maxint;
          for k:=1 to v do
            if flag[k] then {找已在集合中的顶点}
              for j:=1 to v do {求满足条件的边的最小值}
                 if (not(flag[j])) and (w[k,j]<min) and (w[k,j]<>0)
                    then begin
                          min:=w[k,j]; {记下最小值}
                          nextk:=j;
                          prevk:=k;
                         end;
           if min<>maxint
               then begin
                     flag[nextk]:=true; {最小值对应顶点进入集合}
                     writeln(prevk,' ',nextk,‘',min);
                    end;
      end;{for}
   end;{prim}
begin
  assign(input,'');
  reset(input);
  assign(output,'');
  rewrite(output)