Question

数据结构里"树"和"森林"的定义是什么?

Answer 1

树是一种特殊的图，这种图是连通的，并且边数恰好比顶点数少一
即
树集=
{
G=(V,E)
:
|V|=0
或
G连通且|E|=|V|-1}
森林是很多棵树组成的图
严格定义
森林集
=
{
G=(V,E)
:
存在V的划分(V1,V2,...,Vn)，使
对于任意i!=j,u属于Vi且v属于Vj，有(u,v)不属于E
且
G1=(V1,E1)、G2=(V2,E2)、...Gn=(Vn,En)都属于树集(Ei={(u,v)
:
u,v属于Vi
且
(u,v)属于E})
}