图论算法经典.doc

图论算法 最小生成树算法(Prim算法) 单源最短路径算法(Dijkstra算法) 任意结点最短路径算法(Floyd算法) 求有向带权图的所有环 Bellman-Ford算法 计算图的连通性 计算最佳连通分支 计算拓扑序列 图论算法习题 网络建设问题 最短变换问题 挖地雷 乌托邦城市 乌托邦交通中心 某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。【输入】network.in输入文件的第一行为一个正整数N(1≤N≤100)。接下来N行，每行2个数U,V ，表示坐标。【输出】network.out输出最短路径距离（保留两位小数）【样例数据】? 【输入】50 00 10 -11 0-1 0【输出】4.00 {思路分析：此题可以应用PRIM算法解决，关键是根据输入文件算出图的邻接矩阵，然后可以直接应用PRIM算法。} program network; const vmax=100; var w:array[1..vmax,1..vmax]of real; x,y:array[1..vmax] of real; i,j,k,v,e:integer; sum:real; procedure prim(v0:integer); var flag:array[1..vmax] of boolean; min:real; prevk,nextk:integer; begin fillchar(flag,sizeof(flag),false); flag[v0]:=true; for i:=1 to v-1 do begin min:=1e38; 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 min1e10 then begin flag[nextk]:=true; {writeln(prevk, ,nextk, ,min:0:2); 此部分输出每个结点对的距离，因题目不要求所以不输出。} sum:=sum+min; end; end; end;{prim} begin assign(input,network.in); reset(input); assign(output,network.out); rewrite(output); fillchar(w,sizeof(w),0); readln(v); for i:=1 to v do readln(x[i],y[i]); for i:=1 to v do {计算图的邻接矩阵} begin for j:=i+1 to v do begin w[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); w[j,i]:=w[i,j]; end; end; sum:=0; prim(1); writeln(sum:0:2); close(input); close(output); end. 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】??? 现有一张