posts - 12,  comments - 10,  trackbacks - 0

【图论】

 1、Dijkstra算法
 2、Floyd算法
 3、Kruskal算法
 4、Prim算法
 5、欧拉回路

Dijkstra算法
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式,Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致,这里均采用OPEN,CLOSE表的方式。

大概过程:
创建两个表,OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。
1. 访问路网中里起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。
2. 从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。
3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。
4. 重复2,3,步。直到OPEN表为空,或找到目标点。

 

 

Floyd算法
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。

注意单独一条边的路径也不一定是最佳路径。

从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。
对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
不可思议的是,只要按排适当,就能得到结果。
// dist(i,j) 为从节点i到节点j的最短距离
For i←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)

For k←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径?
dist(i,j) = dist(i,k) + dist(k,j)这个算法的效率是O(V3)。它需要邻接矩阵来储存图。
这个算法很容易实现,只要几行。
即使问题是求单源最短路径,还是推荐使用这个算法,如果时间和空间允许(只要有放的下邻接矩阵的空间,时间上就没问题)。
[编辑] 时间复杂度 O(N^3)

 

 

Kruskal算法
基本思想
假设WN=(V,{E})是一个含有n个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有n棵树的一个森林。之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有n-1条边为止。</p>

Procedure kruskal(V,E);
begin
sort(E,1,m);//将边按照权值排序
for t:=1 to n do begin
if getfather(edge[t].u)<>getfather(edge[t].v) then begin //利用并查集判断两个顶点是否在同一集合内
tot:=tot+edge[t].data;//计算权值和
union(edge[t].u,edge[t].v);//合并顶点
inc(k);//合并次数
end;
end;
if k=n-1 then 形成了一棵最小生成树
else 不存在这样的最小生成树;
end;
优化:在判断两个顶点是否在同一集合内时可用并查集  

 


Prim算法

基本思想
1. 在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,这时 U={v0},集合T(E)为空。
2. 从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。
3. 重复2,直到U=V为止。
这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。

PASCAL代码
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]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;

end;{prim}

〖返回顶部〗

 

欧拉回路
定义:
在一个图中,寻找一条只通过每条边一次的路径,这叫做欧拉路径,如果起点和终点是同一点,那么这条回路叫做欧拉回路.
判定一个图中是否存在欧拉回路:并不是每个图都存在欧拉回路.以下分三种情况:
无向图:每个点的度数是偶数,则存在欧拉回路.
有向图:每个结点的入度等于出度,则这个有向图中存在欧拉回路.
总结:以上两种情况很简单,其原理归根结底是每个结点进入和出去的路径条数相等,就存在欧拉回路.还有一种更加复杂的情况.那就是混合图.
混合图:(有时边是单向的,有时边是无向的,就像城市交通网络,有的街道是单向的,有的街道是双向的)找一个给每个无向边定向的策略,这样就可以把图转化成为有向图,使每个顶点的入度与出度是相等的,这样就会存在欧拉回路.
具体过程如下:新建一个图,对于原图中的无向边,在新图中新加一个顶点e(i);对于原图中的每一个顶点j,在新图中建一个顶点v(i),对于原图中每一个顶点j和k之间有一条无向边i,那么在新图中从e(i)出发,添加两条边,分别连向v(j)和v(k),容量都是1.
在新图中,从源点向所有的e(i)都连一条容量为1的边.. 对于原图中每一个顶点j,它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度,从而使它的入度等于总度数的一半,也就是(in + out + un) / 2(显然与此同时出度也是总度数的一半,如果总度数是偶数的话)。当然,如果in已经大于总度数的一半,或者总度数是奇数,那么欧拉回路肯定不存大。如果in小于总度数的一半,并且总度数是偶数,那么我们在新图中从v(j)到汇点连一条边,容量就是(in + out + un) / 2 – in,也就是原图中顶点j还需要多少入度。
按照这个网络模型算出一个最大流,如果每条从v(j)到汇点的边都达到满流量的话,那么欧拉回路成立。

〖返回顶部〗

posted on 2009-05-18 11:06 zhoubaozhong 阅读(234) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(3)

随笔档案

杭电!!

搜索

  •  

最新评论

阅读排行榜

评论排行榜