C树进阶探讨：深度搜索算法在查找环中的具体实现细节？

本文共计3809个文字，预计阅读时间需要16分钟。

1. 前言：对于基环树的讲解，分为上下两篇。上篇以理解连通分量、环以及使用深度优先搜索算法检查连通性和环为主。下篇以基于基环树结构的应为主。

2. 什么是基环树？所谓基环树，指的是...

1. 前言

对于基环树的讲解，分上、下 2 篇，上篇以理解连通分量、环以及使用深度搜索算法检查连通性和环为主，下篇以基于基环树结构的应用为主。

什么是基环树？

所谓基环树指由n个节点n条边所构建而成的连通图。

如下图所示，树结构中共有 7 个节点， 6 条边。此时在树结构上添加一条边，必然会形成一个树环。因树结构中有环，故得此名。基环树也称为环套树。

如下图基环树结构中有 7 个节点，7 条边。

上述为无向边基环树。针对于有向边，基环树分：

• 内向树：树中每个点有且仅有一条出边(或者说每个节点的出度为 1)。

• 外向树：树中每个点有且仅有一条入边(或者说每个点的入度为 1)。

基于基环树有一项基本操作，寻找基环树上的环。

下文将深入讲解如何使用深度搜索算法在无向图中查找环结构。