【图论】

　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)到汇点的边都达到满流量的话，那么欧拉回路成立。

〖返回顶部〗