DFS和BFS用来干什么.ppt

DFS和BFS用来干什么?
连通性
拓扑排序
关键路径
连通分量(ponent)
当无向图为非连通图时, 从图中某一顶点出发, 利用DFS或BFS不可能遍历到图中的所有顶点, 只能访问到该顶点所在的极大连通子图(连通分量)的所有顶点。
若从无向图的每一个连通分量中的一个顶点出发进行遍历, 可求得无向图的所有连通分量。
图的连通性问题
求连通分量的算法需要对图的每一个顶点进行检测:若已被访问过,则该顶点一定是落在图中已求得的连通分量上;若还未被访问,则从该顶点出发遍历图,可求得图的另一个连通分量。
对于非连通的无向图,所有连通分量的生成树组成了非连通图的生成森林。
A
C
D
E
I
B
F
O
G
H
J
N
M
L
K
非连通无向图
A
H
K
C
D
E
I
B
F
O
G
J
N
M
L
非连通图的连通分量
最小生成树( Minimum Cost Spanning Tree )
使用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。
按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
构造最小生成树的准则
必须使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点;
不能使用产生回路的边;
各边上的权值的总和达到最小。
MST 性质
假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中uU,v V-U,则必存在一棵包含边(u,v)的最小生成树。
u
v
V- U
U
u’
v’
普里姆(Prim)算法
普里姆算法的基本思想:
从连通网络 N = ( V, {E} )中的某一顶点 u0 出发, U={u0}。选择与u0关联的具有最小权值的边( u0, v0 ), 将其顶点v0加入到生成树顶点集合U中。
以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把顶点加入v到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。
采用邻接矩阵作为图的存储表示。
5
10
0
4
6
1
3
2
原图(a) (b)
(c) (d) (e) (f)
22
22
5
0
4
6
1
2
10
25
14
16
12
3
5
0
4
6
1
3
2
10
25
25
5
0
4
6
1
3
2
10
22
25
5
0
4
6
1
3
2
10
12
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
12
在构造过程中,设置一个辅助数组:
closedge[0..vexnum-1 ]: 记录从U到V-U具有最小代价的边;
对每个顶点vi V-U :
closedge[ i-1 ].lowcost=Min{cost(u, vi)|u U},
closedge[i-1].adjvex: 对应这条边依附的U中的顶点;
例子
5
0
4
6
1
3
2
28
10
25
14
24
22
16
18
12
void MiniSpanTree_PRIM ( MGraph G, VertexType u ) {
struct{ VertexType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];
k=LocateVex(G,u);
for (j=0;j<;++j)
if (j !=k) closedge[j]={u,[k][j].adj};
closedge[k].lowcost =0; //初始,U={u}
for (i=1;i<;++){ //-1个顶点
k=minimum(closedge); //求出T的下个顶点:第k顶点
printf(closedge[k].adjvex,[k]);
closedge[k].lowcost = 0; //第k顶点并入U集
for ( j=0;j<;++j) //调整
if ([k][j].adj < closedge[j].lowcost)
closedge [j] = {[k],[k][j].adj};
}
}
算法
Prim 算法