【Python数据结构】学习笔记-六：树林、图、最小生成树

一、树林 1.概念：

• 树林是由零个或多个不相交的树组成的集合
• 树林中的树是有序的，彼此称为兄弟

推论：树林可以是一个空集，也可以只有一棵树；在一棵树中将根节点删除（边也删除）得到的也是一个树林

2.树林的遍历（周游）

• 先根次序周游：
  • 首先访问树林中第一棵树的根节点
  • 然后按照先根次序周游第一棵树除去根节点剩下所有子树构成的树林
  • 最后按照先根次序周游剩下的树林
• 后根次序周游：
  • 首先按后根次序周游第一棵树的根节点的所有子树构成的树林
  • 然后访问第一棵树的根节点
  • 最后按后根次序周游剩下的树林

3.树林的存储表示

        所有树的表示方法都可以推广到树林

树林的父节点表示：

(b)中每个节点都有指向其父节点的指针，用-1指示不同树的根节点，

树林的子表表示：

 (c)中指针指向了该节点所有子节点，按顺序成链表

树林的长子-兄弟表示：

 节点前面的指针指向长子，后面的指针指向其下一个兄弟

4.树林与二叉树的转换

• 树林（包括树）与二叉树一一对应
  • 任何树林唯一地对应一棵二叉树
  • 任何二叉树唯一地对应一个树林

树林转换为二叉树：

1. 所有相邻的兄弟节点之间连线
2. 对于每一个非终端节点，只保留它与其最左子节点的连线，其余连线删去
3. 以根节点为旋转轴，将整棵树顺时针旋转一定角度（如45°）使层次分明

set Forest F as Sequence: F = T1, T2, ..., Tn
to create Binary Tree B(F) recursively:
    if n = 0 --> B(F) is empty
    if n > 0 --> B(F).root = T1.root = w1
        B(F).left = B(T11, T12, ...,T1m)   # T11, ...,T1m are children of T1
        B(F).right = B(T2, ..., Tn)

二叉树转换为森林：

1.  如果一个节点是其父节点的左子节点，则把该节点的右子节点、右子节点的右子节点......都与该结点的父母连线（图b中的虚线）
2. 去掉原二叉树中所有父节点到右子节点的连线（图b中的实线）
3. 整理得到树林，使结构层次分明

set Binary Tree B:
    B.root = r
    B.L = r.left
    B.R = r.right

create Forest F(B) recursively:
    if B is empty --> F(B) is empty
    if B is not empty -->
        F(B) = T1 + F(R)  # T1.root = r, r.children = F(L)

---

二、图 1.概念

图是比树更一般、更复杂的结构：图中的节点（通常称作顶点）之间的关系是任意的，不再限制其前驱和后继的个数

• 图有顶点的非空有穷集合V和边的集合E组成，记为
• 每条边就是一个顶点的偶对，所以E也是V上的关系，

2.有向图和无向图

• 有向图：边有方向，边是顶点的有序对
• 无向图：边没有方向，边是顶点的无序对
• 完全图：任意两个顶点之间都有边的有向图
  • n个顶点的无向完全图有n*(n-1)/2条边
  • n个顶点的有向完全图有n*(n-1)条边

3.数据结构对简单图的两个限制

①不考虑顶点到自身的边；②顶点间没有重复的边

4.顶点的度

• 顶点的度：与一个顶点邻接的边的条数
• 对于有向图，度分为入度和出度
  • 入度：从其他顶点到该点的边的条数
  • 出度：从该点出发的边的条数
• 无论对有向图还是无向图，顶点数n、边数e和顶点度数满足如下关系：

5.路径与路径长度

• 路径：两点之间有若干条边相连，则存在一条路径
• 路径长度：路径上的边数
• 回路（环）：起点和终点相同的路径；如果回路中其他顶点均不相同，则为简单回路
• 简单路径：内部不含有环的路径

6.子图

对于两个图G1，G2，如果G2的顶点集合时G1的顶点集合的子集；边集合也是G1边集合的子集；那么G2是G1的子图

7.有根图

若有向图G中存在一顶点v，可以通过路径到达其他所有顶点，则G为有根图，v称为图G的根

• 根不一定唯一
• 树是有唯一根的有根图（且所有顶点入度最多为1）

8.连通图

• 连通：若⽆向图G中存在从vi到vj的路径（显然它也是从vj到vi的路径)，则称vi与vj连通
• 连通图：如果⽆向图G中的任意两个不同顶点vi和vj都连通（即存在路径），则称G为连通图
• 连通分量：⽆向图G中的⼀个极⼤连通⼦图（不存在包含它的更⼤的连通⼦图）称为G的⼀个连通分量。若G不连通，它的连通分量将多于⼀个
• 强连通图：如果有向图G中任意两个不同顶点vi和vj之间都存在从vi到vj以及从vj和vi的路径，则称G是强连通图;
• 强连通分量：有向图G的极⼤强连通⼦图称为其强连通分量。

9.带权图和网络

每条边被赋予权值的图称为带权图；带权的连通无向图称为网络

 10.图的抽象数据类型

图是⼀种⼗分⼴泛的结构，图的抽象数据类型难以给出统⼀的定义。

下面列举一些可能的 *** 作：

• 创建图，创建空图，基于顶点和边的数据创建图
• 判断是否为空
• 顶点个数和边的条数
• 所有顶点的集合，所有边的集合
• 增加一条边；是否存在边；访问一条边
• 顶点的入度和出度
• 顶点的邻居
• 图的遍历
• 图的连通性

11.图的存储表示 邻接矩阵表示法：

• 顶点表：顺序存储顶点信息
• 关系矩阵：表示顶点之间相互关系

•  ⽆向图的关系矩阵⼀定是⼀对称矩阵。
• ⽆向图的关系矩阵的第 i ⾏(或第 i 列)⾮零元素个数为第 i 个顶点的度 D(vi)。
• 有向图的关系矩阵的第 i ⾏⾮零元素个数为第 i 个顶点的出度 OD(vi)，第 i 列⾮零元素个数就是第 i 个顶点的⼊度ID(vi)。
• 从图的邻接矩阵表示，很容易确定图中任意两个顶点之间是否有边相连。

邻接表表示法：

• 顶点表：顺序存储顶点信息
• 边表：与每个顶点相关联的（n个）链式存储的边表

 两种表示的空间开销：

若图中有n个顶点，e条边，则邻接矩阵的空间代价为

无向图的邻接表为；有向图为

12.图算法 12.1 图的周游

从图中某个顶点出发，按照某种⽅式系统访问图中所有顶点，且每个顶点仅访问⼀次。也称图的遍历。这种周游的基本部分是访问⼀个顶点所在的（强）连通分量⾥的全部结点。如果不是（强）连通图，还需要去访问其他（强）连通分量。

• 深度优先周游
• 广度优先周游

①深度优先周游（Depth-First Traversal）/深度优先搜索

• 从指定顶点v出发，并将其标记为已访问过
• 依次从v的未被访问过的各邻接顶点w出发，进行深度优先搜索，知道图中与v连通的所有顶点都访问过
• 如果图中还有未访问顶点，则选一个未访问顶点，由它出发重复上述过程，直到图中所有顶点都被访问为止

对图进⾏深度优先周游时，按访问顶点的先后次序所得到的顶点序列，称为该图的深度优先周游序列，简称 DFS 序列

 DFS：v1→v2→ v4 → v8→v5→v3→v6→v7

def dfs_graph(graph, v0):
    vnum = graph.vertex_num()  # 图中的顶点数
    visited = [0] * vnum  # 初始化访问状态
    visited[v0] = 1  # 标记起始顶点
    dfs_seq = [v0]  # 初始化周游序列
    st = SStack()  # 自定义栈，见第三讲
    st.push((0, graph.out_edges(v0)))  # out_edges图方法，从初始节点引出的边
    # (i, edges)入栈，说明下次访问的是edges[i]
    while not st.is_empty():  # 直到空栈，循环结束
        i, edges = st.pop()  # 访问第一条边
        if i < len(edges):
            v, e = edges[i]  # 该边的起点和终点
            st.push((i + 1, edges))  # 把下一个访问的压入栈中
            if not visited[v]:  # 如果起点没被访问过
                dfs_seq.append(v)  # 加入深度优先序列
                visited[v] = 1  # 标记改点为访问
                st.push((0, graph.out_edges(v)))  # 把该点引出的边压入栈中
    return dfs_seq  # 空栈则遍历结束

• 时间复杂度：
  • 邻接矩阵实现：
  • 邻接表实现：
• 空间复杂度：

②广度优先周游（Breadth-First Traversal）/广度优先搜索

• 从顶点v出发，标记为已访问
• 依次访问v的所有未被访问的相邻节点w1, w2,...， wx；然后依次访问与w1，w2，...，wx邻接的所有未访问顶点；知道所有已访问节点的相邻节点都被访问为止
• 如果还存在未被访问顶点，则选择一个进行广度优先搜索，直到所有的顶点都被访问过

对图进⾏⼴度优先周游时，按访问顶点的先后次序所得到的顶点序列，称为该图的⼴度优先周游序列，简称BFS 序列

 BFS：v1→v2→ v3 → v4→v5→v6→v7→v8

12.2图的生成树

• 对于连通的⽆向图或强连通的有向图从任⼀顶点出发周游，或是对于有根的有向图，从图的根顶点出发周游，可以访问到图中所有的顶点。
• 周游时经过的边加上所有顶点构成了图的⼀个连通⼦图，称为图的⼀棵⽣成树

生成树的构造：

• 深度优先生成树
• 广度优先生成树

 生成树林：

非连通图往往只能得到由各连通分量的生成树；或各个有根子图的生成树组成的生成树林

最小生成树：

• 图的⽣成树不唯⼀，从不同顶点出发，或从同⼀顶点出发，周游的路径不⼀样，则得到的⽣成树都可能不同。
• ⽹络的⽣成树中的边也带权，将⽣成树各边的权值加起来称为⽣成树的权，把权值最⼩的⽣成树称为最⼩⽣成树(Minimum Spanning Tree，简称为MST)。

最小生成树的性质：

在图G中，若U是顶点集V的任意真子集；

假设有边e = (u,v)，顶点u在U中，v在V-U中，且e是G中所有两端在U和V-U的边中权值最小的边；

则一定存在G的一棵包括边e的最小生成树

本讲小结：

①树林与二叉树的互相转换

树林转二叉树：兄弟节点连线；删去除最左连线外的连线；旋转

二叉树转树林：若为左子节点，则把该节点的所有右子节点、右子节点的右子节点全部与根节点相连；断开原始根节点与右子节点的连线；整理

②图的基本概念

③图的存储表示

邻接矩阵表示法

邻接表表示法

④图的周游

深度优先周游

广度优先周游

⑤最小生成树的概念及性质