图论算法有哪些 [图论算法(经典)]
图论算法
最小生成树算法(Prim算法)
单源最短路径算法(Dijkstra算法)
任意结点最短路径算法(Floyd算法)
求有向带权图的所有环
Bellman-Ford 算法
计算图的连通性
计算最佳连通分支
计算拓扑序列
图论算法习题
网络建设问题
最短变换问题
挖地雷
乌托邦城市
乌托邦交通中心
某大学准备在校园网中构建校园网络，已知在校园网中选好了N （N
【输入】network.in
输入文件的第一行为一个正整数N(1≤N≤100)。
接下来N 行，每行2个数U,V ，表示坐标。
【输出】network.out
输出最短路径距离（保留两位小数）
【样例数据】
【输入】
5
0 0
0 1
0 -1
1 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]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 算法思想】
任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。
【最小生成树算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？
【输入】 第一行两个数v(v
【输出】 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]0)
then begin
min:=w[k,j]; {记下最小值}
nextk:=j;
prevk:=k;
end;
if minmaxint
then begin
flag[nextk]:=true; {最小值对应顶点进入集合} writeln(prevk," ",nextk,‘ ",min);
end;
end;{for}
end;{prim}
begin
assign(input,"prim.in");
reset(input);
assign(output,"prim.out");
rewrite(output);
fillchar(w,sizeof(w),0);
readln(v,e);
for k:=1 to e do
begin
read(i,j);
readln(w[i,j]);
w[j,i]:=w[i,j];
end;
prim(1);
close(input);
close(output);
end.
设图G=(V,E)是一个有向图, 它的每一条边(U,V)都有一个非负权W(U,V)，在G 中指定一个结点V0，要求从V0到G 的每一个结点Vj 的最短路径找出来（或指出不存在）。 由于源结点V0是给定的，所谓称为单源最短路径。
【Dijkstra 算法思想】
把所有结点分为两组。
第一组：包含已确定最短路径的结点。
第二组：包含尚未确定最短路径的结点。
按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。
【单源最短路径算法实例】
现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。
【输入】 第一行一个整数v ，代表城镇数，县城编号为1。 第二行是一个整数e ，表示有向边数。 以下e 行，每行为两个城镇编号和它们之间的公路造价。
【输出】 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
2 3
2 4
1 5
1 6
原 图 从第1点出发的最短路径
program dijkstra_example;
const
vmax=100;
type
path=record {此记录类型用于记录每一个结点与v0的距离和其父结点}
length:integer;
pre:0..vmax;
end;
var
w:array[1..vmax,1..vmax] of integer;
dist:array[1..vmax] of path;
v,e,u,i,j,x,y:integer;
procedure init;
begin
assign(input,"dijkstra.in");
reset(input);
assign(output,"dijkstra.out");
rewrite(output);
readln(v);
readln(e);
for i:=1 to v do
for j:=1 to v do
if ij
then w[i,j]:=30000
{30000只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数}
else w[i,j]:=0;
for i:=1 to e do
begin
read(x,y);
readln(w[x,y]);
w[y,x]:=w[x,y];
end;
end;
procedure dijkstra(v0:integer);
var
min:integer;
begin
w[v0,v0]:=1; {v0首先进入第一组}
for i:=1 to v do
begin
dist[i].length:=w[v0,i]; {计算每个结点的距离值}
if dist[i].length30000
then dist[i].pre:=v0 {如和v0直接有路，则置前驱结点为v0} else dist[i].pre:=0;
end;
repeat
min:=30000;
u:=0;
for i:=1 to v do {找最短距离}
if (w[i,i]=0) and (dist[i].length
then begin
u:=i;
min:=dist[i].length;
end;
if u0
then begin
w[u,u]:=1;
for i:=1 to v do {重新计算其他结点的距离值}
if (w[i,i]=0) and (dist[i].length>dist[u].length+w[u,i]) then begin
dist[i].length:=dist[u].length+w[u,i];
dist[i].pre:=u;
end;
end;
until u=0;
end;
begin
init;
v0:=1;
dijkstra(v0);
for i:=1 to v do
begin
if (iv0) and (dist[i].length30000)
then write(dist[i].pre," ",i);
end;
close(input);
close(output);
end.
设图G=(V,E)是一个有向图, 对于每对结点(U,V),找出从U 到V 的最短路径。
【Floyd 算法思想】
利用一个三重循环产生一个存储每个结点最短距离的矩阵.
【Floyd 算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离
【输入】 第一行两个数v,e ，分别代表城市数和边数 以下e 行，每行为两个顶点和它们之间的边权。
【输出】 所有可能连接的城市的最短距离。
【输入样例】
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
1 3 15
1 4 16
1 5 19
1 6 21
2 3 5
2 4 6
2 5 24
2 6 11
3 4 6
3 5 24
3 6 16
4 5 18
4 6 14
5 6 32
program floyd_example;
const
maxn=10;
var
n,s,t,i,j:integer;
dist:array[1..maxn,1..maxn] of real;
prev:array[1..maxn,1..maxn] of 0..maxn;
procedure init;
var
m,i,u,v:integer;
begin
assign(input,"floyd.in");
reset(input);
assign(output,"floyd.out");
rewrite(output);
readln(n,m);
fillchar(prev,sizeof(prev),0);
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1e10;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
prev[u,v]:=u;
prev[v,u]:=v;
end;
end;{init}
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]
then begin
dist[i,j]:=dist[i,k]+dist[k,j];
prev[i,j]:=prev[k,j];
end;
end;{floyd}
procedure print(i,j:integer);
begin
if i=j
then write(i)
else if prev[i,j]=0
then write("No Solution!")
else begin
print(i,prev[i,j]);
write("->",j);
end;
end;{print}
begin
init;
floyd;
for i:=1 to n do
for j:=i+1 to n do
begin
write(i," ",j," ");
write(dist[i,j]:0:0," ");
print(i,j);
writeln;
end;
close(input);
close(output);
end.
求有向图的所有环, 此问题包括了求最大环或者最小环。
【输入】
第一行两个数v,e ，分别代表图的顶点数和边数，以下e 行，每行为有连接的两个顶点和权。
【输出】
顶点编号和环的长度以及包含该顶点的环的路径。
【输入样例】 huan.in
5 7
1 2 2
2 1 1
2 5 4
3 2 5
3 4 7
4 1 3
5 4 6
【输出样例】 huan.out
1 3 1->2
2 3 2->1
4 15 4->1->2->5
5 15 5->4->1->2
program huan;
const
maxn=90;
var
n,s,t,i,j:integer;
dist:array[1..maxn,1..maxn] of real;
prev:array[1..maxn,1..maxn] of 0..maxn;
procedure init;
var
m,i,u,v:integer;
begin
assign(input,"huan.in");
reset(input);
assign(output,"huan.out");
rewrite(output);
readln(n,m);
fillchar(prev,sizeof(prev),0);
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1e10;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
prev[u,v]:=u;
end;
end;
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]
then begin
dist[i,j]:=dist[i,k]+dist[k,j];
prev[i,j]:=prev[k,j];
end;
end;{floyd}
procedure print(i,j:integer);
begin
if i=j
then write(i)
else if prev[i,j]=0
then write("No Circle!")
else begin
print(i,prev[i,j]);
write("->",j);
end;
end;{print}
begin
init;
floyd;
for i:=1 to n do
begin
if dist[i,i]1e10
then
begin
write(i," ");
write(dist[i,i]:0:0," ");
print(i,prev[i,i]);
writeln;
end;
end;
close(input);
close(output);
end.
输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传递闭包的计算方法。
【输入】
n(顶点数，1≤n≤20)
e(边数，1≤e≤210)
以下e 行，每行为有边连接的一对顶点
【输出】
k行，每行两个数，为存在通路的顶点对序号i,j(i
【输入样例】
6
5
1 5
1 6
2 3
4 6
5 6
【输出样例】
1 4
1 5
1 6
2 3
4 5
4 6
5 6
program bibao_example;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
v,e,k,i,j:integer;
procedure init;
begin
assign(input,"bibao.in");
reset(input);
assign(output,"bibao.out");
rewrite(output);
fillchar(longlink,sizeof(longlink),0);
fillchar(link,sizeof(link),0);
readln(v);
readln(e);
for k:=1 to e do
begin
readln(i,j);
link[i,j]:=true; {因为没有权，所以有布尔型表示连通关系，能提高运算速度}
link[j,i]:=true;
end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do {枚举中间顶点}
for i:=1 to v do {枚举所有顶点对}
for j:=1 to v do {计算顶点i 和顶点j 的连通情况}
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]); end;{bibao}
procedure out;
begin
for i:=1 to v-1 do
for j:=i+1 to v do
if longlink[i,j]
then writeln(i," ",j);
end;{out}
begin{main}
init;
bibao;
out;
close(input);
close(output);
end.
在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。
【输入】
n(顶点数，1≤n≤20)
以下n 行，其中第i 行是顶点i 的权
e(边数，1≤e≤210)
以下e 行，每行为有边连接的一对顶点
【输出】
含顶点数最多的一个连通分支
顶点权和最大的一个连通分支
【输入样例】
6
2
10
20
8
5
7
5
1 5
1 6
2 3
4 6
5 6
【输出样例】
1->5->6->4->
2->3->
program liantong_example;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
f:array[1..maxv] of boolean;
w:array[1..maxv] of integer;
v,e,k,i,j,s,best,besti,max,maxk:integer;
procedure init;
begin
assign(input,"liantong.in");
reset(input);
assign(output,"liantong.out");
rewrite(output);
fillchar(longlink,sizeof(longlink),0);
fillchar(link,sizeof(link),0);
readln(v);
for i:=1 to v do
readln(w[i]);
readln(e);
for k:=1 to e do
begin
readln(i,j);
link[i,j]:=true;
link[j,i]:=true;
end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do
for i:=1 to v do
for j:=1 to v do
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]); end;{bibao}
procedure dfs(i:integer); {深度优先搜索，用于输出路径}
begin
write(i,"->");
f[i]:=true;
for j:=1 to v do
if (not f[j]) and longlink[i,j]
then dfs(j);
end;{dfs}
begin{main}
init;
bibao;
for i:=1 to v do
begin
k:=0;s:=0;
for j:=1 to v do {计算顶点i 所在连通分支中的顶点总数和顶点的权和} if longlink[i,j]
then begin
k:=k+1;
s:=s+w[j];
end;
if k>best {求出顶点数的最大值}
then begin
best:=k;
besti:=i;
end;
if s>max {求出顶点权和的最大值}
then begin
max:=s;
maxk:=i;
end;
if k=v then peak;
end;
fillchar(f,sizeof(f),false); {结点是否访问数组初始化}
dfs(besti);
writeln;
fillchar(f,sizeof(f),false);
dfs(maxk);
close(input);
close(output);
end.
所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下：
给出有向图G=（V ，E ），若结点的线形序列V1,V2,...Vn 满足条件：对于i,j(1≤j
【拓扑排序主要思想】
有向图可以拓扑排序的条件是：图中没有环。
具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
反复执行这两个步骤，直到所有结点都已经进入拓扑序列。
【实例：士兵排队问题】
有n 个士兵(1≤n≤26)，依次编号为A,B,C,... ，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD ，FABD ，ABFD
【输入】
k行，每行a b，表示a>b
【输出】
一个可行的排队方案
【输入样例】
A B
B D
F D
【输出样例】
ABFD
program soldier_sort;
var
w:array["A".."Z","A".."Z"] of 0..1;
d:array["A".."Z"] of integer; {记录顶点入度的数组}
s:set of "A".."Z";
a,b,ch:char;
m,n:string;
i,j,k:integer;
begin
assign(input,"tuopu.in");
reset(input);
assign(output,"tuopu.out");
rewrite(output);
s:=[];
while not eof(input) do
begin
readln(a,ch,b);
s:=s+[a,b]; {计算士兵名集合}
w[a,b]:=1;
d[b]:=d[b]+1; {累计顶点b 的入度}
end;
m:="";
for a:="A" to "Z" do
if a in s
then m:=m+a; {产生士兵名字符集}
k:=length(m); {求得士兵人数}
n:=""; {拓扑序列初始为空}
for i:=1 to k do
begin
j:=1;
while (d[m[j]]>0) and (j
if j>k {若不存在入度为0的顶点，则无法拓扑排序失败}
then begin
writeln("Fault!");
peak;
end;
n:=n+m[j]; {入度为0的顶点进入拓扑序列n}
a:=m[j]; {删去顶点j}
d[a]:=maxint;
for j:=1 to k do {与a 相连的顶点入度减1}
if w[a,m[j]]>0
then d[m[j]]:=d[m[j]]-1;
end;{for}
writeln(n);
close(input);
close(output);
end.
在一个地图上有n(n≤20)个地窖, 每个地窖中埋有一定数量的地雷, 给出地窖之间的联系路径。当地窖极其连接的数据给出之后, 某人可以从任一处开始挖地雷, 然后可以沿着指出的连接往下挖(仅能选择一条路径) ，挖雷的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。请编程设计一个挖地雷的方案，使某人能挖到的最多的地雷。
【输入文件】miner.in
n(地窖个数)
v1 v2 v3 ... vn (每个地窖的地雷数)
a(1,2) ... a(1,n)
a(2,3) ... a(2,n)
.
.
.
a(n-1,n)
(表示地窖之间连接路径，其中a(i,j)表示地窖i,j 之间是否有通路，若有通路，则a(i,j)=1，若无通路，则a(i,j)=0）
【输出文件】miner.out
R1-R2-...-Rk(挖地雷的顺序)
Max(挖的地雷总数)
【样例数据】
【输入】miner.in
6
2 10 20 8 5 7
0 0 0 1 1
1 0 0 0
0 0 0
0 1
1
【输出】miner.out
2-3
30
{利用计算最佳连通分支算法即可求得}
program miner;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
a:array[1..maxv,1..maxv] of 0..1;
f:array[1..maxv] of boolean;
w:array[1..maxv] of integer;
v,e,k,i,j,s,max,maxk:integer;
procedure init;
begin
assign(input,"miner.in");
reset(input);
assign(output,"miner.out");
rewrite(output);
fillchar(longlink,sizeof(longlink),false);
fillchar(link,sizeof(link),false);
readln(v);
for i:=1 to v do
read(w[i]);
readln;
for i:=1 to v do
begin
for j:=i+1 to v do
begin
read(a[i,j]);
if a[i,j]=1
then begin
link[i,j]:=true;
link[j,i]:=true;
end;
end;{for j}
readln;
end;{for i}
for i:=1 to v do begin
for j:=1 to v do
write(link[i,j]:6);
writeln;end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do
for i:=1 to v do
for j:=1 to v do
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]); end;{bibao}
procedure dfs(i:integer);
begin
write(i," ");
f[i]:=true;
for j:=1 to v do
if (not f[j]) and longlink[i,j]
then dfs(j);
end;{dfs}
begin{main}
init;
bibao;
max:=0;
for i:=1 to v do
begin
s:=0;
for j:=1 to v do
if longlink[i,j]
then s:=s+w[j];
if s>max
then begin
max:=s;
maxk:=i;
end;
end;
fillchar(f,sizeof(f),false);
dfs(maxk);
writeln;
write(max);
close(input);
close(output);
end.
住在乌托邦首都（编号为1）的天凯，开始对首都的交通情况感到不满，因为，他发现首都到某些城市，即使他选择最短的路径，距离也非常远。因此他想让你求一下交通中心城市是哪座城市（也有可能就是首都）。
为了说明交通中心城市的概念，先定义G[i]为距离城市i 最远的城市（到城市i 的最短路径长度最长的城市）到城市i 的距离。那么交通中心城市都是G[i]最小的城市，如果有几个城市的G[i]一样小，则是编号最小的那个。
【输入文件】capital.in
第一行两个整数n,m(n≤100)。下面m 行，每行三个整数，第i+1行的整数表示第i 条高速公路连接的两个城市编号和长度（0
【输出文件】capital.out
仅一个数，表示交通中心城市的编号
【样例数据】
【输入】capital.in
5 5
1 2 1
1 5 6
2 3 2
2 4 1
4 5 2
【输出】capital.out
2
{思路：利用FLOYD 算法求出所有结点的最短路径矩阵，
然后求出每个结点到其他的结点的距离总合，取最小的那个}
program capital;
const
maxn=100;
var
n,m,k,i,j:integer;
min,sum:longint;
dist:array[1..maxn,1..maxn] of longint;
{prev:array[1..maxn,1..maxn] of 0..maxn;} {因为无需知道路径，因此略去计算前驱的数组}
procedure init;
var
m,i,u,v:integer;
begin
assign(input,"capital.in");
reset(input);
assign(output,"capital.out");
rewrite(output);
readln(n,m);
{fillchar(prev,sizeof(prev),0);}
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1000000000;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
{prev[u,v]:=u;
prev[v,u]:=v;}
end;
{readln(s,t);}
end;
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]
begin
dist[i,j]:=dist[i,k]+dist[k,j];
{prev[i,j]:=prev[k,j];}
end;
end;{floyd}
{procedure print(i,j:integer); 打印路径过程也不需要
begin
if i=j
then write(i)
else if prev[i,j]=0
then write("No Solution!")
else begin
print(i,prev[i,j]);
write("->",j);
end;
end;}
begin
init;
floyd;
min:=100000000;
for i:=1 to n do
begin
sum:=0;
for j:=1 to n do
if ij {自己到自己的路径不能计算在内} then sum:=sum+dist[i,j];
if min>sum
then begin
min:=sum;
k:=i;
end; end; write(k); close(input); close(output); end.