1．最小生成树
A.Prim算法：
procedure prim(v0: Integer);
var
lowcost, closest: array[1..maxn] of Integer;
i, j, k, Min: Integer;
begin
for i := 1 to n do
begin
lowcost[i] := cost[v0, i];
closest[i] := v0;
end;
for i := 1 to n - 1 do
begin
{寻找离生成树最近的未加入顶点k}
Min := MaxLongint;
for j := 1 to n do
if (lowcost[j] < Min) and (lowcost[j] <> 0) then
begin
Min := lowcost[j];
k := j;
end;
lowcost[k] := 0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j := 1 to n do
if cost[k, j] < lwocost[j] then
begin
lowcost[j] := cost[k, j];
closest[j] := k;
end;
end;
end;{prim}
B.Kruskal算法：(贪心) 按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v: Integer): Integer; {返回顶点v所在的集合}
var i: Integer;
begin
i := 1;
while (i <= n) and (not v in vset[i]) do
Inc(i);
if i <= n then
find := i
else find := 0;
end;
procedure kruskal;
var tot, i, j: Integer;
begin
for i := 1 to n do
vset[i] := [i];{初始化定义n个集合，第I个集合包含一个元素I}
p := n - 1;
q := 1;
tot := 0;
{p为尚待加入的边数，q为边集指针}
Sort;
{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
while p > 0 do
begin
i := find(e[q].v1);
j := find(e[q].v2);
if i <> j then
begin
Inc(tot, e[q].Len);
vset[i] := vset[i] + vset[j]; vset[j] := [];
Dec(p);
end;
Inc(q);
end;
Writeln(tot);
end;
2.最短路径
A.标号法求解单源点最短路径：
var
a: array[1..maxn, 1..maxn] of Integer;
b: array[1..maxn] of Integer;
{b[i]指顶点i到源点的最短路径}
mark: array[1..maxn] of Boolean;
procedure bhf;
var best, best_j: Integer;
begin
FillChar(mark, SizeOf(mark), false);
mark[1] := true; b[1] := 0;{1为源点}
repeat
best := 0;
for i := 1 to n do
if mark[i] then {对每一个已计算出最短路径的点}
for j := 1 to n do
if (not mark[j]) and (a[i, j] > 0) then
if (best = 0) or (b[i] + a[i, j] < best) then
begin
best := b[i] + a[i, j];
best_j := j;
end;
if best > 0 then
begin
b[best_j] := best；mark[best_j] := true;
end;
until best = 0;
end;{bhf}
B.Floyed算法求解所有顶点对之间的最短路径：
procedure floyed;
begin
for I := 1 to n do for j := 1 to n do
if a[I, j] > 0 then
p[I, j] := I
else p[I, j] := 0;{p[I,j]表示I到j的最短路径上j的前驱结点}
for k := 1 to n do {枚举中间结点}
for i := 1 to n do for j := 1 to n do
if a[i, k] + a[j, k] < a[i, j] then
begin
a[i, j] := a[i, k] + a[k, j];
p[I, j] := p[k, j];
end;
end;
C.Dijkstra 算法：
var
a: array[1..maxn, 1..maxn] of Integer;
b, pre: array[1..maxn] of Integer; {pre[i]指最短路径上I的前驱结点}
mark: array[1..maxn] of Boolean; procedure dijkstra(v0: Integer);
begin
FillChar(mark, SizeOf(mark), false);
for i := 1 to n do
begin
d[i] := a[v0, i];
if d[i] <> 0 then
pre[i] := v0
else pre[i] := 0;
end;
mark[v0] := true;
repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
Min := MaxInt; u := 0; {u记录离1集合最近的结点}
for i := 1 to n do if (not mark[i]) and (d[i] < Min) then
begin
u := i;
Min := d[i];
end;
if u <> 0 then
begin
mark[u] := true;
for i := 1 to n do
if (not mark[i]) and (a[u, i] + d[u] < d[i]) then
begin
d[i] := a[u, i] + d[u];
pre[i] := u;
end;
end;
until u = 0;
end;
3.计算图的传递闭包
procedure Longlink;
var T: array[1..maxn, 1..maxn] of Boolean;
beginFillChar(t, SizeOf(t), false);
for k := 1 to n do
for I := 1 to n do
for j := 1 to n do
T[I, j] := t[I, j] or (t[I, k] and t[k, j]);
end;
4．无向图的连通分量
A.深度优先
procedure dfs(Now, Color: Integer);
begin
for i := 1 to n do
if a[Now, i] and c[i] = 0 then
begin
{对结点I染色}
c[i] := Color;
dfs(I, Color);
end;
end;
B 宽度优先（种子染色法）
5．关键路径几个定义： 顶点1为源点，n为汇点。
a.顶点事件最早发生时间Ve[j], Ve[j] = Max{ Ve [j] + w[I,j] },b,其中Ve(1) = 0;
b.顶点事件最晚发生时间 Vl[j], Vl[j] = Min{ Vl[j] – w[I,j] }, 其中 Vl(n) = Ve(n);
c.边活动最早开始时间 Ee[I], 若边I由<j, k>表示，则Ee[I] = Ve[j];
d.边活动最晚开始时间 El[I], 若边I由<j, k>表示，则El[I] = Vl[k] – w[j, k];
若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。求解方法：
a.从源点起topsort, 判断是否有回路并计算Ve;
b.从汇点起topsort, 求Vl;
c.算Ee 和 El;
6．拓扑排序找入度为0的点，删去与其相连的所有边，不断重复这一过程。例
寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.
7. 回路问题Euler回路(DFS)
定义：经过图的每条边仅一次的回路。(充要条件：图连同且无奇点）Hamilton
回路定义：经过图的每个顶点仅一次的回路。一笔画充要条件：图连通且奇点个数为0
个或2个。
9．判断图中是否有负权回路 Bellman - ford 算法 x[I], y[I],
t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。
procedure bellman-ford
begin
for I := 0 to n - 1 do
d[I]:= +infinitive;
d[0] := 0;
for I := 1 to n - 1 do
for j := 1 to m do {枚举每一条边}
if d[x[j]] + t[j] < d[y[j]] then
d[y[j]] := d[x[j]] + t[j];
for I := 1 to m do
if d[x[j]] + t[j] < d[y[j]] then
return false
else return true;
end;
10．第n最短路径问题 *
第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。
* 同理，第n最短路径可在求解第n - 1最短路径的基础上求解
|
