树与生成树.ppt

树与生成树
第1页，共36页，编辑于2022年，星期六

定理1给定图T, 以下关于树的定义是等价的.
⑴ T无回路的连通图.
⑵T无环且每对结点之间有一条且仅有一条路.
⑶ T无回路但在任一对不相邻的1
2
2
1
3
7
7
2
4
8
6
6
5
3
4
4
3
第8页，共36页，编辑于2022年，星期六
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通图.
|S|=n-1, 说明是树
最后S={a1, a2, a3,… ,an-1}
S=Φ i=0 j=1
将所有边按照权升序排序:
e1, e2, e3,… ,em
|S|=n-1
取ej使得
S∪{ ej}有回路?
j=j+1
i=i+1
ai=ej
S=S∪{ai}
j=j+1
输出S
停
Y
N
Y
N
第9页，共36页，编辑于2022年，星期六
边按升序排序:边(vi, vj)记成eij
边
权
边
权
e28
e34
e23
e38
e17
e24
e45
e57
e16
e78
e56
e35
e46
e67
e58
e12
e18
1 1 2 2 2 3 3 3 4
4 4 5 6 6 7 7 8
v1 
 v5
 v4
v2 
 v3
v8 
 v6
v7 
1
2
2
1
3
7
7
2
4
8
6
6
5
3
4
4
3
v1 
 v5
 v4
v2 
 v3
v8 
 v6
v7 
1
2
1
2
4
3
3
第10页，共36页，编辑于2022年，星期六
Prin算法(边割法)
实质: 在n-1个边割集中, 取每个边割集的一条权最小的边, 构成G的一个生成树.
定义：
Step0. 设v为V的任一顶点. 令S0={v}, E0=, k=0.
Step1. 若Sk=V, 结束. 以Sk为点集, Ek为边集的图即是G的最优树. 否则转Step2.
Step2. 构造 , 若 , 则G不连通, 停止. 否则, 设

令
置k=k+1. 返回Step1.
第11页，共36页，编辑于2022年，星期六
例：求图G的最小生成树。
第12页，共36页，编辑于2022年，星期六
破圈法
----Prin算法的对偶方法. 最适合于在图上作业. 当图比较大时, 还可以几个人同时在各个局部作业.
Step0. 令G0=G. k=0.
Step1. 若Gk不含圈, 转Step2. 若Gk中含有圈C. 设ekE(C), 且
令Gk+1= Gk- ek, 若k=k+1, 返回Step1.
Step2. 结束. Gk为G的最小树.
第13页，共36页，编辑于2022年，星期六
第14页，共36页，编辑于2022年，星期六
结论：最小生成树不唯一。
本节要掌握
树的6个定义,
会画生成树和会求最小生成树.
第15页，共36页，编辑于2022年，星期六
8-10. 根树及其应用
下面讨论有向树,
定树、语法树、分类树、搜索树、目录树等等.

:如果G是个有向图,且若不考虑边的方向时(即看成
无向图时),是一棵树,则称G是有向树.
例如:
v1 
 v6
v4 
v2 
 v3
 v5
v2 
v5 
 v4
v1 
 v3
v6 
v4 
第16页，共36页，编辑于2022年，星期六
:如果一棵有向树,恰有一个结点的入度为0,其余
所有结点的入度均为1,则称此树为根树.
:入度为0的结点.
:出度为0的结点.
(内结点):出度不为0的结点.
:如果<vi,vj>是根树中
的一条边,则称vi是vj的父结点, vj是vi的子结点.
: 在根树中,如果从vi到vj有路,则称
vi是vj的祖先结点, vj是vi的后裔结点.
:从根结点到某个结点的路径的长度,称为该结点的层次