数据结构5 最小生成树.ppt

最小生成树
生成树和生成森林
最小生成树
小结和作业
.
生成树
一、定义
图G的生成树是G的极小连通子图，即包含G中的所有顶点（n）和n-1条边的连通子图
.
生成树
V1
V2
V3
V4
V5
V8
V6
V7
V1
V2
V4
V8
V5
V3
V6
V7
V1
V2
V3
V4
V5
V8
V6
V7
深度优先：
广度优先：
.
生成树
二、算法
图的遍历算法访问了图中的每个顶点一次且仅一次。
访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。
因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。
.
生成树算法
void DFSTree(Graph G,int v,CSNode T){ =true; first=true; for(w=FirstAdjVex(G,v);w>=0;
w=NextAdjVex(G,v,w)) if(!){  p= new CSNode(v);
if(first){ =p;first=false; } else{ =p;} q=p; DFSTree(G,);
}
}
SG1
SG2
SG3
V
w1
w3
w2
算法以孩子兄弟链表作为生成森林的存储结构
.
生成森林
一、定义
非连通图G的每个连通分量的生成树，构成了图G的生成森林
.
生成森林
a
b
c
h
d
e
k
f
g
8
1
2
3
4
5
6
7
0
8
1
2
3
4
5
6
7
0
a
b
c
h
d
e
k
f
g
非连通图G：
G的深度优先搜索生成森林：
a
c
h
d
f
e
k
b
g
.
生成森林算法
算法以孩子兄弟链表作为生成森林的存储结构
void DFSForest(Graph G, CSNode T){T=null;for(v=0;v=;++v) =false;for(v=0;v=;++v) if(!){ p=new CSNode(v)
if(!T) T=p; else =p; q=p; DFSTree(G,v,p);}}
.
最小生成树
假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？
问题：
.
最小生成树
连通网：n个城市和城市间可能的通信线路
网的顶点：表示城市
网的边：表示两个城市之间的线路
网的边上的权值：通信代价
2
4
5
2
7
10
6
1
4
v4
v5
v1
v3
v2
v6
v7
1
3
8
.