数据结构-图-章节3

章节3 生成树（生成森林）

对连通图进行遍历，过程中所经历的边和顶点的组合可看作是一颗普通树，通常称为生成树。

图1

图1a是一张连通图，图1b是其对应的2中生成树

注意：连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应对应。

连通图中的生成树必须满足以下2个条件 1 包含连通图中的所有顶点 2 任意两顶点之间有且只有一条通路

因此，连通图的生成树具有这样的特征，即生成树中边的数量 = 顶点数-1

生成森林

生成图对应连通图来说，而生成树森林是对应非连通图来说的。

非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树，因此整个非连通图相对应的，是由多颗生成树组成的生成森林。

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG