图论中的常用经典算法

图论中的常用经典算法

第一节最小生成树算法

一、生成树的概念

若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。

对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。

由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。如下图：

但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

二、求图的最小生成树算法

严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。

对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。

求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。

例1、城市公交网

[问题描述]

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。

[输入]

n（城市数，1<=n<=100）

e（边数）

以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。

[输出]

n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。

[举例]

下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。

[问题分析]

出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim 算法和Kruskal算法。

1、用Prim算法求最小生成树的思想如下：

①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；

②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；

③重复下列操作，直到选取了n-1条边：

选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)；

将顶点Y加入集合S，边（X，Y）加入集合TE；

④得到最小生成树T =（S，TE）

上图是按照Prim算法，给出了例题中的图（A）最小生成树的生成过程（从顶点1开始）。其中图（E）中的4条粗线将5个顶点连通成了一棵最小生成树。Prim算法的正确性可以通过反证法证明。

因为操作是沿着边进行的，所以数据结构采用边集数组表示法，下面给出Prim算法构造图的最小生成树的具体算法框架。

①从文件中读入图的邻接矩阵g；

②边集数组elist初始化；

For i:=1 To n-1 Do

Begin

elist[i].fromv:=1；elist[i].endv:=i+1；elist[i].weight:=g[1,i+1]；

End；

③求出最小生成树的n-1条边；

For k:=1 To n-1 Do

Begin

min:=maxint；m:=k；

For j:=k To n-1 Do {查找权值最小的一条边}

If elist[j].weight

If m<>k Then Begin t:=elist[k]；elist[k]:=elist[m]；elist[m]:=t；End；

{把权值最小的边调到第k个单元}

j:=elist[k].endv； {j为新加入的顶点}

For i:=k+1 To n-1 Do {修改未加入的边集}

Begin s:=elist[i].endv； w:=g[j,s]；

If w

Then Begin elist[i].weight:=w；elist[i].fromv:=j；End；

End；

End；

④输出；

2、用Kruskal算法求最小生成树的思想如下：

设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE 中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE 中包含n-1条边为止。最后的T即为最小生成树。如何证明呢？

下图是按照Kruskal算法给出了例题中图（A）最小生成树的生成过程：

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。

下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。

①将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序；

②设数组C[1..n-1]用来存储最小生成树的所有边，C[i]是第i次选取的可行边在排好序的

elist中的下标；

③设一个数组S[1..n]，S[i]都是集合，初始时S[i]= [ i ]。

i:=1；{获取的第i条最小生成树的边}

j:=1；{边集数组的下标}

While i<=n-1 Do

Begin

For k:=1 To n Do Begin {取出第j条边，记下两个顶点分属的集合序号}

If elist[j].fromv in s[k] Then m1:=k；

If elist[j].endv in s[k] Then m2:=k；

End；

If m1<>m2 Then Begin {找到的elist第j条边满足条件，作为第i条边保留}

C[i]:=j；

i:=i+1；

s[m1]:=s[m1]+s[m2]；{合并两个集合}

s[m2]:=[ ]； {另一集合置空}

End；

j:=j+1； {取下条边，继续判断}

End；

④输出最小生成树的各边：elist[C[i]]

3、总结

以上两个算法的时间复杂度均为O（n*n）。参考程序见Prim.pas和Kruskal.pas。

请大家用以上两种算法完成例1。

三、应用举例

例2、最优布线问题（wire.pas，wire.exe）

[问题描述]

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接

是指它们时间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往

往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们

采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另

一台计算机的连接。

现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。

[输入格式]

输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n

个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

[输出格式]

输出文件wire.out，一个整数，表示最小的连接费用。

[样例输入]

3

0 1 2

1 0 1

2 1 0

[样例输出]

2（注：表示连接1和2，2和3，费用为2）

[问题分析]

本题是典型的求图的最小生成树问题，我们可以利用Prim算法或者Kruskal算法求出，下面

的程序在数据结构上对Kruskal算法做了一点修改，具体细节请看程序及注解。

[参考程序]

Program wire(Input, Output)；

var g : Array [1..100, 1..100] Of Integer；{邻接矩阵}

l : Array [0..100] Of Integer； {l[i]存放顶点i到当前已建成的生成树中

任意一顶点j的权值g[i,j]的最小值} u : Array [0..100] Of Boolean； { u[i]=True，表示顶点i还未加入到生成树中；

u[i]=False，表示顶点I已加入到生成树中 } n, i, j, k, total : Integer；

Begin

Assign(Input, 'wire.in')；

Reset(Input)；

Assign(Output, 'wire.out')；

Rewrite(Output)；

Readln(n)；

For i := 1 To n Do Begin

For j := 1 To n Do Read(g[i，j])；

Readln；

End；

Fillchar(l, sizeof(l), $7F)； {初始化为maxint}

l[1] := 0； {开始时生成树中只有第1个顶点}

Fillchar(u, sizeof(u), 1)； {初始化为True，表示所有顶点均未加入}

For i := 1 To n Do

Begin

k := 0；

For j := 1 To n Do {找一个未加入到生成树中的顶点，记为k，

要求k到当前生成树中所有顶点的代价最小}

If u[j] And (l[j] < l[k]) Then k := j；

u[k] := False； {顶点k加入生成树}

For j := 1 To n Do {找到生成树中的顶点j，要求g[k,j]最小}

If u[j] And (g[k，j] < l[j]) Then l[j] := g[k，j]；

End；

total := 0；

For i := 1 To n Do Inc(total, l[i])； {累加}

Writeln(total)；

Close(Input)；

Close(Output)；

End.

第二节最短路径算法

最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生的建模能力，反映出学生的创造性思维，因为有些看似跟最短路径毫无关系的问题也可以归结为最短路径问题来求解。本文就简要分析一下此类问题的模型、特点和常用算法。

在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。

对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。

例1、假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用旅费最少，试编程输出结果。

[问题分析]

解这类问题时，很多同学往往不得要领，采用穷举法把所有可能的情况全部列出，再找出其中旅费最少的那条路径；或者采用递归（深搜）找出所有路径，再找出旅费最少的那条。但这两种方法都是费时非常多的解法，如果城市数目多的话则很可能要超时了。

实际上我们知道，递归（深搜）之类的算法一般用于求所有解问题（例如求从A出发每个城市都要走一遍一共有哪几种走法？），所以这些算法对于求最短路径这类最优解问题显然是不合适的。

首先，对于这类图，我们都应该先建立一个邻接矩阵，存放任意两点间的数据（距离、费用、时间等），以便在程序中方便调用，上图的邻接矩阵如下：

const dis:array[1..5,1..5] of integer =( ( 0, 7, 3,10,15),

( 7, 0, 5,13,12),

( 3, 5, 0, 6, 5),

(10,13, 6, 0,11),

(15,12, 5,11, 0) )；

以下介绍几种常见的、更好的算法。

一、宽度优先搜索

宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后面的优秀算法做个铺垫。具体如下：

1、从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其旅费；

2、再次由AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然由AD可以展开得到ADB、ADC、ADE，由AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其旅费；

3、再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、……、AEDB、AEDC，每个结点也需记录下其旅费；

4、再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其旅费；

5、到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。

由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那条，显而易见也是一种很费时的算法。

二、 A＊算法

A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。

这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能越快找到答案。A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找相关资料学习A*算法。

三、等代价搜索法

等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A＊算法的一种简化版本。它的大体思路是：

1、从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）；

2、把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；

3、再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；

4、再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点，……；

5、每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。

由上可见，A＊算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。

例2、题目基本同例1，现在把权定义成距离，现在要求A点到E点的最短路径，但并不要求每个城市都要走一遍。

[问题分析]

既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，实际上就是穷举。那么等代价搜索能不能再用在这题上呢？答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。

是不是搜索到一个结点是以E结束时就停止呢？显然不对。

那么是不是要把所有以E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。

实际上，应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是E时，这个结点就是我们所要求的答案！因为比这个结点大的点再

展开得到的解显然不可能比这个结点优！

那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍这种求最短路径问题的其它几种成熟算法。

四、宽度优先搜索+剪枝

搜索之所以低效，是因为在搜索过程中存在着大量的重复和不必要的搜索。因此，提高搜索效率的关键在于减少无意义的搜索。假如在搜索时已经搜出从起点A到点B的某一条路径的长度是X，那么我们就可以知道，从A到B的最短路径长度必定≤X，因此，其他从A到B的长度大于或等于X的路径可以一律剔除。具体实现时，可以开一个数组h[1..n]，n是结点总数，h[i]表示从起点到结点i的最短路径长度。算法流程如下：

1、初始化：

将起点start入队，h[start]:=0，h[k]:=maxlongint(1<=k<=n，且k≠start)。

2、repeat

取出队头结点赋给t；

while t有相邻的结点没被扩展

begin

t扩展出新的结点newp；

如果 h[t]+w[t,newp]

则将newp入队，把h[newp]的值更新为h[t]+w[t,newp]；

end

until 队列空；

以上算法实现的程序如下：

const maxn=100;

maxint=maxlongint div 4;

maxq=10000;

var h:array[1..maxn] of longint;

g:array[1..maxn,1..maxn] of longint;

n,i,j:longint;

procedure bfs;

var head,tail,i,t:longint;

q:array[1..maxq] of longint;

begin

for i:=1 to n do h[i]:=maxint;

h[1]:=0;

q[1]:=1;

head:=0;tail:=1;

repeat

head:=head+1;

t:=q[head];

for i:=1 to n do

if (g[t,i]<>maxint)and(h[t]+g[t,i]

begin

tail:=tail+1;

q[tail]:=i;

h[i]:=h[t]+g[t,i];

end;

until head=tail;

end;

begin

assign(input,'data.in');

reset(input);

read(n);

for i:=1 to n do

for j:=1 to n do

begin

read(g[i,j]);

if (g[i,j]<=0)and(i<>j) then g[i,j]:=maxint;

end;

bfs;

for i:=2 to n do

writeln('From 1 To ',i,' Weigh ',h[i]);

close(input);

end.

五、迭代法

该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：

Dij = min { Dij , Dik+Dkj }，1<=k<=n。

这样，我们就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径。

算法流程如下：

D[i]表示从起点到i的最短路的长度，g是邻接矩阵，s表示起点；

1、D[i]:=g[s,i] (1<=i<=n)；

2、repeat

c:=false; {用以判断某一步是否有某个Dij值被修改过}

for j:=1 to n do

for k:=1 to n do

if D[j]>D[k]+g[k,j] then

begin D[j]:= D[k]+g[k,j]; c:=true; end;

Until not c；

这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。

这个算法实现的程序如下：

const maxn=100;

maxint=maxlongint div 4;

var D:array[1..maxn] of longint;

g:array[1..maxn,1..maxn] of longint;

n,i,j,k:longint;

c:boolean;

begin

assign(input,'data.in');

reset(input);

read(n);

for i:=1 to n do

for j:=1 to n do

begin

read(g[i,j]);

if (g[i,j]<=0)and(i<>j) then g[i,j]:=maxint;

end;

for i:=1 to n do D[i]:=g[1,i];

repeat

c:=false;

for j:=1 to n do

for k:=1 to n do {k是中转点}

if D[j]>D[k]+g[k,j] then

begin

D[j]:=D[k]+g[k,j];

c:=true;

end;

until not c;

for i:=2 to n do

writeln('From 1 To ',i,' Weigh ',D[i]);

close(input);

end.

六、动态规划

动态规划算法已经成为了许多难题的首选算法。某些最短路径问题也可以用动态规划来解决，通常这类最短路径问题所对应的图必须是有向无回路图。因为如果存在回路，动态规划的无后效性就无法满足。

我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：

递归：类似f(n)=x1*f(n-1)+x2*f(n-2)………，即可以找到一个确定的关系的表达式； 动态规划：类似f(n)=min(f(n-1)+x1,f(n-2)+x2……)，即我们无法找到确定关系的表达式，只能找到这样一个不确定关系的表达式，f(n)的值是动态的，随着f(n-1),f(n-2)等值的改变而确定跟谁相关。

为了给问题划分阶段，必须对图进行一次拓扑排序（见下一节内容），然后按照拓扑排序的结果来动态规划。

譬如，有如下两个有向图：

右图因为存在回路而不能用动态规划。而左图是无回路的，所以可以用动态规划解决。

对左图拓扑排序，得到的序列是A 、B 、D 、C 、E 。

设F(E)表示从A 到E 的最短路径长度，然后按照拓扑序列的先后顺序进行动态规划： F(A)=0

F(B)=min{ F(A) }+3=3

F(D)=min{ F(A)+8, F(B)+2 }=5 F(C)=min{ F(B)+9, F(D)+5 }=10

F(E)=min{ F(D)+1, F(C)+4 }=6 总的式子是：F(i)=min{ F(k)+dis(i,k) }，k 与i 必须相连，且在拓扑序列中，k 在i 之前。

这个算法的参考程序如下： const maxn=100;

maxint=maxlongint div 4;

var g:array[1..maxn,1..maxn] of longint;{有向图的邻接矩阵} pre:array[1..maxn] of longint; {pre[i]记录结点i 的入度} tp:array[1..maxn] of longint; {拓扑排序得到的序列} s:array[1..maxn] of longint; {记录最短路径长度} n,i,j,k:longint;

begin

assign(input,'data.in'); reset(input); read(n);

fillchar(pre,sizeof(pre),0); for i:=1 to n do for j:=1 to n do begin

read(g[i,j]); if g[i,j]>0 then

pre[j]:=pre[j]+1; {如果存在一条有向边i→j，就把j的入度加1}

end;

for i:=1 to n do {拓扑排序}

begin

j:=1;

while (pre[j]<>0) do j:=j+1; {找入度为0的结点}

pre[j]:=-1;

tp[i]:=j;

for k:=1 to n do

if g[j,k]>0 then

pre[k]:=pre[k]-1;

end;

filldword(s,sizeof(s)div 4,maxint); {s数组中的单元初始化为maxint}

s[1]:=0; {默认起点是1号结点}

for i:=2 to n do {动态规划}

for j:=1 to i do

if (g[tp[j],tp[i]]>0)and

(s[tp[j]]+g[tp[j],tp[i]]

s[tp[i]]:=s[tp[j]]+g[tp[j],tp[i]];

for i:=2 to n do

writeln('From 1 To ',i,' Weigh ',s[i]);

close(input);

end.

七、标号法

标号法是一种非常直观的求最短路径的算法，单从分析过程来看，我们可以用一个数轴简单地表示这种算法：

1、以A点为0点，展开与其相邻的点，并在数轴中标出。

2、因为C点离起点A最近，因此可以断定C点一定是由A直接到C点这条路径是最短的（因为A、C两点间没有其它的点，所以C点可以确定是由A点直接到达为最短路径）。因而就可以以已经确定的C点为当前展开点，展开与C点想连的所有点A'、B'、D'、E'。

3、由数轴可见，A与A'点相比，A点离原点近，因而保留A点，删除A'点，相应的，B、B'点保留B点，D、D'保留D'，E、E'保留E'，得到下图：

4、此时再以离原点最近的未展开的点B联接的所有点，处理后，再展开离原点最近未展开的D点，处理后得到如下图的最终结果：

5、由上图可以得出结论：点C、B、D、E就是点A到它们的最短路径（注意：这些路径并不是经过了所有点，而是只经过了其中的若干个点，而且到每一个点的那条路径不一定相同）。因而A到E的最短距离就是13。至于它经过了哪几个点大家可在上述过程中加以记录即可。

标号法的参考程序如下：

const maxn=100;

maxint=maxlongint div 4;

var g:array[1..maxn,1..maxn] of longint; {邻接矩阵}

mark:array[1..maxn] of boolean; {用来标志某个点是否已被扩展}

s:array[1..maxn] of longint; {存储最短路径长度}

n,i,j,k:longint;

begin

assign(input,'data.in');

reset(input);

read(n);

for i:=1 to n do

for j:=1 to n do

begin

read(g[i,j]);

if (i<>j)and(g[i,j]=0) then g[i,j]:=maxint;

end;

fillchar(mark,sizeof(mark),false); {mark初始化为false}

mark[1]:=true; {将起点标志为已扩展}

for i:=1 to n do s[i]:=g[1,i]; {s数组初始化}

repeat

k:=0;

for j:=1 to n do {挑选离原点最近的点}

if (not mark[j])and((k=0)or(s[k]>s[j])) then

k:=j;

if k<>0 then

begin

mark[k]:=true;

for j:=1 to n do {扩展结点k}

if (not mark[j])and(s[k]+g[k,j]

s[j]:=s[k]+g[k,j];

end;

until k=0;

for i:=2 to n do

writeln('From 1 To ',i,' Weigh ',s[i]);

close(input);

end.

八、Dijkstra算法（从一个顶点到其余各顶点的最短路径，单源最短路径）

例3、如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到C i的最短路径(2≤i≤6)，输出路径序列及最短路径的路程长度。

[问题分析]

对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。

设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权

值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。

执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。

对于上图，采用Dijkstra算法找出C1到C i之间的最短路径(2≤i≤6)的过程如下：

第一次：选择m=2，则S=[C1,C2]，计算比较dist[2]+GA[2,j]与dist[j]的大小

123

1234

第四次：选择m=5，则S=[C1,C2,C3,C4,C5]，计算比较dist[5]+GA[5,j]与dist[j]的大小

因为该图的度n=6，所以执行n-2=4次后结束，此时通过dist和path数组可以看出：C1到C2的最短路径为：C1——C2，长度为：4；

C1到C3的最短路径为：C1——C2——C3，长度为：7；

C1到C4的最短路径为：C1——C2——C4，长度为：8；

C1到C5的最短路径为：C1——C2——C3——C5，长度为：9；

C1到C6的最短路径为：C1——C2——C3——C5——C6，长度为：13；

下面给出具体的Dijkstra算法框架（注：为了实现上的方便，我们用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。

Procedure Dijkstra(GA,dist,path,i)； {表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合} Begin

For j:=1 To n Do Begin {初始化}

If j<>i Then s[j]:=0

Else s[j]:=1；

dist[j]:=GA[i,j]；

If dist[j]

Then path[j]:=[i]+[j]

Else path[j]:=[ ]；

End；

For k:=1 To n-2 Do

Begin

w:=maxint；m:=i；

For j:=1 To n Do {求出第k个终点Vm}

If (s[j]=0) and (dist[j]

If m<>i Then s[m]:=1 else exit；{若条件成立，则把Vm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去} For j:=1 To n Do {对s[j]=0的更优元素作必要修改}

If (s[j]=0) and (dist[m]+GA[m,j]

Then Begin

Dist[j]:=dist[m]+GA[m,j]；

path[j]:=path[m]+[j]；

End；

End；

End；

九、Floyed算法

例4、求任意一对顶点之间的最短路径。

[问题分析]

这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyed算法，它的思路简单，但时间复杂度仍然为O（n3），下面介绍Floyed算法。

设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每次以V k（1≤k≤n）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素A[i，j]就是图G中从顶点V i到顶点V j的最短路径长度。再设一个二维数组P[1..n,1..n]，记录最短路径，其元素类型为集合类型set of 1..n。

Floyed算法的具体描述如下：

Procedure Floyed(GA，A，P)；

Begin

For i:=1 To n Do {最短路径长度数组和最短路径数组初始化}

For j:=1 To n Do

Begin

A[i,j]:=GA[i,j]；

If A[i,j]

Else p[i,j]:=[ ]；

End；

For k:=1 To n Do {n次运算}

For i:=1 To n Do

For j:=1 To n Do

Begin

If (i=k)or(j=k)or(i=j) Then Continue；

{无需计算，直接进入下一轮循环}

If A[i,k]+A[k,j]

A[i,j]：= A[i,k]+A[k,j]；

P[i,j]：= P[i,k]+P[k,j]；

End；

End；

End；

对于上图，大家可以运用Floyed算法，手工或编程试着找出任意一对顶点之间的最短路径及其长度。

十、总结与思考

最短路径问题的求解还不止这几种算法，比如还有分枝定界等等，而且大家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。

在学习完最短路径后，有没有人想到：能不能修改这些算法，实现求最长路径的问题呢？这种发散性的思维是值得称赞的，对于不存在回路的有向图，这种算法是可行的。但需要提醒的是：如果有向图出现了回路，按照最长路径的思想和判断要求，则计算可能沿着回路无限制的循环下去。这就引出了一个问题：如何判断一个有向图中是否存在回路？可以用bfs或dfs在搜的过程检查这个点是否在前面出现过；当然也可以用下面的拓扑排序算法。

第三节拓扑排序算法

在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。

在AOV网中，有向边代表子工程（活动）的先后关系，即有向边的起点活动是终点活动的前

驱活动，只有当起点活动完成之后终点活动才能进行。如果有一条从顶点Vi到Vj的路径，则说Vi是Vj的前驱，Vj是Vi的后继。如果有弧，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。

一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。

把不带回路的AOV网中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。

需要注意的是AOV网的拓扑序列是不唯一的，如对下图进行拓扑排序至少可以得到如下几种拓扑序列：02143567、01243657、02143657、01243567。

在上图所示的AOV网中，工程1和过程2显然可以同时进行，先后无所谓；但工程4却要等工程1和工程2都完成以后才可进行；工程3要等到工程1和工程4完成以后才可进行；工程5又要等到工程3、工程4完成以后才可进行；工程6则要等到工程4完成后才能进行；工程7要等到工程3、工程5、过程6都完成后才能进行。可见由AOV网构造拓扑序列具有很高的实际应用价值。

其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。

对上图进行拓扑排序的过程如下：

1、选择顶点0（唯一），输出0，删除边<0，1>，<0，2>；

2、选择顶点1（不唯一，可选顶点2），输出1，删除边<1，3>，<1，4>；

3、选择顶点2（唯一），输出2，删除边<2，4>；

4、选择顶点4（唯一），输出4，删除边<4，3>，<4，5>，<4,6>；

5、选择顶点3（不唯一，可选顶点6），输出3，删除边<3，5>，<3，7>；

6、选择顶点5（不唯一，可选顶点6），输出5，删除边<5，7>；

7、选择顶点6（唯一），输出6，删除边<6，7>；

8、选择顶点7（唯一），输出7，结束。

输出的顶点数m=8，与AOV网中的顶点数n=8相等，所以输出一种拓扑序列：01243567。

为了算法实现上的方便，我们采用邻接表存储AOV网，不过稍做修改，在顶点表中增加一个记录顶点入度的域id，具体的拓扑排序算法描述如下：

Procedure TopSort(dig:graphlist)；{用邻接表dig存储图G}

Var n,top,i,j,k,m: Integer；

P:graphlist；

Begin

n:=dig.adjv； {取顶点总个数}

top:=0； {堆栈、初始化}

For i:=1 To n Do {对入度为0的所有顶点进行访问，序号压栈}

If dig.adj[i].id = 0 Then Begin

dig.adj[i].id:=top；

top:=i；

End；

m:=0； {记录输出的顶点个数}

While top<>0 Do {栈不空}

Begin

j:=top； {取一个入度为0的顶点序号}

top:=dig.adj[top].id； {出栈、删除当前处理的顶点、指向下个入度为0的顶点} Write(dig.adj[top].v)； {输出顶点序号}

m:=m+1；

p:=dig.adj[j].link； {指向V j邻接表的第一个邻接点}

While p<>nil Do {删除所有与V j相关边}

Begin

k:=p^.adjv； {下一个邻接点}

dig.adj[k].id:= dig.adj[k].id - 1； {修正相应点的入度}

If dig.adj[k].id = 0 Then Begin {入度为0的顶点入栈}

dig.adj[k].id:=top；

top:=k；

End；

p:=p^.next； {沿边表找下一个邻接点}

End；

End；

If m

End；

思考：拓扑排序一般用在哪些场合呢？

解答：如判回路或图的动态规划过程中分阶段。

例1、士兵排队（soldier）

问题描述：

有n个士兵（1≤n≤26），编号依次为A、B、C，……队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果（p1，p2∈{'A'，…，'Z'}），记为p1>p2。例如A>B，B>D，F>D。士兵的身高关系如图所示：

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

图论算法详解(C++版)

1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】连通所有城市的公路最小造价。 【输入样例】 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 【输出样例】50 原图 最小生成树 #include #include #include #include using namespace std; int i,j,k,n,m,mi,t,s,a[1000][1000]; void prim() { int mi,p,f,k,d[1000]; bool v[1000]; memset(v,false,sizeof(v)); f=1; for (i=2;i<=n;i++) {

d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j]

算法初步比较经典的教案

算法初步与框图 一、知识网络 二、考纲要求 1.算法的含义、程序框图 （1）了解算法的含义，了解算法的思想. （2）理解程序框图的三种基本逻辑结构：顺序、条件分支、循环. 2.基本算法语句 理解几种基本算法语句――输入语句、输出语句、赋值语句、条件语句、循环语句的含义. 三、复习指南 本章是新增内容，多以选择题或填空题形式考查，常与数列、函数等知识联系密切.考查的重点是算法语句与程序框图,以基础知识为主,如给出程序框图或算法语句,求输出结果或说明算法的功能;或写出程序框图的算法语句,判断框内的填空等考查题型.难度层次属中偏低. 第一节 算法与程序框图 ※知识回顾 1 2..

3. 4. 5.算法的基本特征：①明确性：算法的每一步执行什么是明确的；②顺序性：算法的“前一步”是“后一步”的前提，“后一步”是“前一步”的继续；③有限性：算法必须在有限步内完成任务，不能无限制的持续进行；④通用性：算法应能解决某一类问题. ※典例精析 例1.如图所示是一个算法的程序框图，则该程序框图所表示的功能是 解析：首先要理解各程序框的含义,输入a,b,c三个数之后,接着判断a,b的大小,若b小，则把b赋给a,否则执行下一步，即判断a与c的大小，若c小，则把c赋给a, 否则执行下一步，这样输出的a是a,b,c三个数中的最小值.所以该程序框图所表示的功能是求a,b,c三个数中的最小值. 评注: 求a,b,c三个数中的最小值的算法设计也可以用下面程序框图来表示. 例2.下列程序框图表示的算法功能是（） （1）计算小于100的奇数的连乘积 （2）计算从1开始的连续奇数的连乘积 （3）计算从1开始的连续奇数的连乘积， 当乘积大于100时，计算奇数的个数 （4）计算L≥ 1×3×5××n100成立时n的最小值 解析：为了正确地理解程序框图表示的算法，可以将执行过程分解，分析每一步执行的结果.可以看出程序框图中含有当型的循环结构,故分析每一次循环的情况,列表如下: 第一次:13,5 =?=； S i 第二次:135,7 =??=； S i 第三次:1357,9 S<不成立,输出结果是7,程序框图表示的算法功能是求使=???=,此时100 S i

各种排序算法的总结和比较

各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort）

归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。

数学建模10种常用算法

数学建模10种常用算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行

编程的话，那一些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关， 即使与图形无关，论文中也应该要不乏图片的，这些 图形如何展示以及如何处理就是需要解决的问题，通 常使用Matlab进行处 参数估计 C.F. 20世纪60年代,随着电子计算机的 。参数估计有多种方法，有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下，后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍 参数估计（parameter 尽可能接近的参数 误差 平方和　 θ,使已知数据Y 最大,这里P(Y│θ)是数据Y P(Y│θ)。在实践中这是困难的，一般可假设P（Y│θ

几种常见内部排序算法比较

常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.

详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key

C语言经典算法大全

C语言经典算法大全 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题（Knapsack Problem） 数、运算 蒙地卡罗法求PI Eratosthenes筛选求质数 超长整数运算（大数运算） 长PI 最大公因数、最小公倍数、因式分解 完美数 阿姆斯壮数 最大访客数 中序式转后序式（前序式） 后序式的运算 关于赌博 洗扑克牌（乱数排列） Craps赌博游戏 约瑟夫问题（Josephus Problem） 集合问题 排列组合 格雷码（Gray Code） 产生可能的集合

m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法- 改良的插入排序Shaker 排序法- 改良的气泡排序Heap 排序法- 改良的选择排序快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 搜寻 循序搜寻法（使用卫兵） 二分搜寻法（搜寻原则的代表）插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵

1.河内之塔 说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越 战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。 解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘 子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 #include void hanoi(int n, char A, char B, char C) { if(n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); } else { hanoi(n-1, A, C, B); printf("Move sheet %d from %c to %c\n", n, A, C); hanoi(n-1, B, A, C); } } int main() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; }

经典图论问题

5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。

二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s

5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：

常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排

常见经典排序算法（C语言） 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法*/ #include void sort(int v[],int n) { int gap,i,j,temp; for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ { for(i=gap;i= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换*/ { temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } }

} } 二.二分插入法 /* 二分插入法*/ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i temp) /* 如果中间元素比但前元素大，当前元素要插入到中间元素的左侧*/ { high = mid-1; } else /* 如果中间元素比当前元素小，但前元素要插入到中间元素的右侧*/ { low = mid+1; } } /* 找到当前元素的位置，在low和high之间*/ for (j=i-1; j>high; j--)/* 元素后移*/ { a[j+1] = a[j]; } a[high+1] = temp; /* 插入*/ } }

c语言经典算法100例

60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/

f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1;

C#实现所有经典排序算法

C#实现所有经典排序算法 //选择排序 class SelectionSorter { private int min; public void Sort(int[] arr) { for (int i = 0; i < arr.Length - 1; ++i) { min = i; for (int j = i + 1; j < arr.Length; ++j) { if (arr[j] < arr[min]) min = j; } int t = arr[min]; arr[min] = arr[i]; arr[i] = t; } } static void Main(string[] args) { int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 }; SelectionSorter s = new SelectionSorter(); s.Sort(array); foreach (int m in array) Console.WriteLine("{0}", m); } } //冒泡排序 class EbullitionSorter { public void Sort(int[] arr) { int i, j, temp; bool done = false; j = 1; while ((j < arr.Length) && (!done))//判断长度 { done = true; for (i = 0; i < arr.Length - j; i++) { if (arr[i] > arr[i + 1]) {

C常用经典算法及其实现

C常用经典算法及其实 现 集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289-

常用算法经典代码（C++版） 一、快速排序 voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中 {inth=x,r=y; intm=a[(x+y)>>1];//取中间的那个位置的值 while(hm)r--;//比中间那个位置的值大，循环直到找一个比中间那个值小的 if(h<=r) {inttemp=a[h];//如果此时h<=r，交换a[h]和a[r] a[h]=a[r]; a[r]=temp; h++;r--;//这两句必不可少哦 } } if(r>x)qsort(x,r);//注意此处，尾指针跑到前半部分了

if(h=1;j--)//相邻的两两比较 if(a[j]

离散数学图论部分经典试题及答案

离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v V v 2)deg(=∑∈ D ．E v V v =∑∈)deg( 4．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集 5．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集 6．如图三所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集 C ．{(a, e ) ,(b, c )}是边割集 D ．{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

图论算法

Dijkstra 算法： 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量 pb 、1index 、2index 、d 分别用 来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ? ?=顶点未标号当第顶点已标号 当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2 index=index(1); end index2(temp)=index; end d, index1, index2 %dijkstra 最短路算法通用程序，用于求从起始点s 到其它各点的最短路 %D 为赋权邻接矩阵，d 为s 到其它各点最短路径的长度，DD 记载了最短路径生成树 function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0;

C常用经典算法及其实现修订稿

C常用经典算法及其实 现 公司标准化编码 [QQX96QT-XQQB89Q8-NQQJ6Q8-MQM9N]

常用算法经典代码（C++版） 一、快速排序 void qsort(int x,int y) a[n]数组中 {int h=x,r=y; int m=a[(x+y)>>1]; a[n]数组中 {for(int i=1;ia[s].da)&&(a[s].father==0)) ather=0,说明这个结点还不是别个结点 mins=s; ather==0) {a[x].code=”“;}ather].lchild==x) a[x].code=a[a[x].father].code+'0'; if(a[a[x].father].rchild==x) a[x].code=a[a[x].father].code+'1'; if(a[x].lchild!=0) inorder(a[x].lchild);child==0)&&(a[x].rchild==0))a<<':'<a[elist[i].to][elist[j].to]) elist[j].w=a[elist[i].to][elist[j].to];} } for(int i=1;i<=n-1;i++); } ?

C常用经典算法及其实现

常用算法经典代码（C++版） 一、快速排序 void qsort(int x,int y) //待排序的数据存放在a[1]..a[n]数组中 {int h=x,r=y; int m=a[(x+y)>>1]; //取中间的那个位置的值 while(hm) r--; //比中间那个位置的值大，循环直到找一个比中间那个值小的if(h<=r) {int temp=a[h];//如果此时h<=r，交换a[h]和a[r] a[h]=a[r]; a[r]=temp; h++;r--; //这两句必不可少哦 } } if(r>x) qsort(x,r);//注意此处，尾指针跑到前半部分了 if(h

{for(int i=1;i=1;j--) //相邻的两两比较 if(a[j]>a; tong[a]++;}//相应的桶号计数器加1 for(int i=1;i<=cmax;i++) {if(tong[i]>0) //当桶中装的树大于0，说明i出现过tong[i]次，否则没出现过i while (tong[i]!=0) {tong[i]--; cout<

图论经典问题

常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树