C树进阶系列中，深度搜索算法查找环的哪些细节值得深入探讨？
- 内容介绍
- 文章标签
- 相关推荐
本文共计3801个文字，预计阅读时间需要16分钟。
1. 前言：针对基环树的讲解 - 上篇：以理解连通分量、环及使用深度优先搜索算法检查连通性和环为主 - 下篇：以基于基环树结构的应用为主
2. 什么是基环树？ - 所谓基环树，指的是...
1. 前言
对于基环树的讲解，分上、下 2 篇，上篇以理解连通分量、环以及使用深度搜索算法检查连通性和环为主，下篇以基于基环树结构的应用为主。
什么是基环树？
所谓基环树指由n个节点n条边所构建而成的连通图。
如下图所示，树结构中共有 7 个节点， 6 条边。此时在树结构上添加一条边，必然会形成一个树环。因树结构中有环，故得此名。基环树也称为环套树。
如下图基环树结构中有 7 个节点，7 条边。
上述为无向边基环树。针对于有向边，基环树分：
- 内向树：树中每个点有且仅有一条出边(或者说每个节点的出度为
1)。
- 外向树：树中每个点有且仅有一条入边(或者说每个点的入度为
1)。
基于基环树有一项基本操作，寻找基环树上的环。
下文将深入讲解如何使用深度搜索算法在无向图中查找环结构。
2. 查找环
在图中查找环的常用的算法有：
- 深度搜索算法。
- 广度搜索算法。
- 并查集。
- 拓扑排序算法。
广度和深度搜索是原生算法，面对较复杂的图结构时，略显拙劣。较优的方案是使用优化过的并查集和拓扑排序算法，其在性能和技巧上都很精妙。
Tips： 关于并查集和拓扑排序算法可查阅我的相关博文。
2.1 问题分析
起点和终点相同的路径称为回路或称为环（Cycle），除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，本文仅对简单回路进行讨论。
Tips： 一般而言，回路至少需要
3个顶点。
图中是否有环的前提条件：边数至少要等于顶点数。
所以对于有 n个顶点的无向（有向）图，是否存在环，可以先检查边的数量 m与顶点数量之间的关系。
Tips： 本文主要以无向图为讨论对象。
- 如果
m=n-1。可以是下面的几种情况。
-
一个连通分量图情况。可以理解为以任何一个顶点为根节点构建成的树结构，此时连通分量为
1，显然此情况无法成环。Tips： 所谓连通图，指任意两个顶点之间都有路径的图。
-
上文说过，如果存在回路，顶点数量和边数至少要相等，这句话不能狭义地诠释为如果边数小于顶点数，则图中无环。
当
m=n-1时，顶点数可以拆分成n=m+1。这里遵循一个拆分原则，尽可能在已有边数的基础上成全图中某些顶点成环的要求。如下图所示，连通分量有
2个，其中一个子图中存在一个环。所以当边数少于顶点数时，需要讨论是否存在子图。
也可以是如下几种图形：
m<n-1时，如果m<=2则无法构建成环。其它情况下都能构建出一个有环的子图。
- 当
m>=n因为边数已经大于顶点数，显然图中有环。
2.2 深度搜索算法思想
2.2.1 连通分量
可以使用深度搜索算法查找图中是否有环，先了解一下深度搜索算法的搜索流程。
Tips： 深度搜索算法可以使用递归和非递归实现。本质是使用栈进行数据存储。
- 先创建一个栈(非递归实现)，用来存储搜索到的顶点。
- 以
A顶点为出发点，且把A顶点压入栈中，用于初始化栈。并在图的A顶点上做已入栈的标志。
- 查询出与
A顶点相邻的顶点B、E，并且压入栈中。
- 继续查询与
E顶点相邻的顶点（即入栈操作完成后，再查询与栈顶元素相邻的顶点）D，且压入栈中。
- 检查与
D顶点相邻的顶点C，且压入栈中。
经过上述操作后，可发现图结构中所有顶点全部被压入栈中，此时，能证明什么？
至少有一点是可以证明的：栈中的顶点在一个集合或在一个连通分量上。
使用如上搜索方案时，是否能找到此连通分量上的所有顶点？
先看下图的搜索结果：
当查询与 D顶点相邻的顶点时，因 D和C没有连通性，故C无法入栈。栈中的顶点在一个连通分量上，是不容质疑的，而实际上 C也是此连通分量上的一份子。
所以，使用仅入栈不出栈的搜索方案，无法找到同一个连通分量上的所有顶点。
可以把深度搜索方案改一下，采用入栈、出栈形式。
- 初始
A入栈。
A出栈，找到与A相邻的顶点B、E，且入栈。
E出栈，找到与E相邻的D顶点，且让其入栈。
D出栈，因没有与D相邻的顶点（每个顶点只能入一次栈）可入栈。继续B出栈，因C是与之相邻的顶点且没有入过栈，C入栈。
- 最后
C出栈，栈空。
至此，可以得到一个结论：
- 在一次深度搜索过程中，入过栈的顶点都在一个集合中（或一个连通分量上）。
- 使用出栈、入栈方案时，可以保证搜索到一个连通分量上的所有顶点。
**Tips： **使用广度搜索一样能找到一个连通分量上的所有顶点。
原理很简单，深度搜索是按纵深方式进行搜索的(类似于一条线上的蚂蚱)，在互相有关联的纵深线上的顶点能被搜索到。
如下图所示：从A开始，有左、右两条纵深线，在搜索完左边的纵深线后。
可以继续搜索另一条纵深线。
一次深度搜索只能检查到一条连通分量。如果图中存在多个连通分量时，需要使用多次深度搜索算法。如下图所示：
连通分量与找环有什么关系？
连通分量与环之间有很一个简单的关系：环一定是存在一个连通分量上。找环之前，先要确定目标顶点是不是在一个连通分量上。否则，都不在一起，还找什么环？
是否在一个连通分量上的顶点一定有环？
如下图，所有顶点都在一个连通分量中，实际情况是，图没有环。所以，仅凭顶点全部在一个连通分量上，是无法得到图中一定有环的结论。
那么，使用深度搜索算法在图中搜索时，怎么证明图中有环？
根据前面的推断，可以得出结论：
- 所有搜索的顶点在一个连通分量上，且图或子图边数大于或等于顶点数时，那么图或子图中必然存在环。
那么？环上的顶点有什么特点？
如果图中存在环，那么，环上每个顶点必然至少有 2条边分别和环上另 2 个顶点相连，边的数量决定与其相邻顶点的数量。
Tips：道理很简单，如果有
n个人通过手牵手围成一个圈，如果其中有一个人只原意出一只手，则圈是无法形成的。 可以把此人移走，剩余人可以围成一个圈。
2.2.2 小结
查询环上的顶点时，需要满足如下几个要求：
- 所有顶点在一个连通分量上。
- 连通分量上的边数要大于或等于顶点数。
- 环上至少有
2条边的顶点可认定是环上的顶点。
2.3 编码实现
顶点类：
#include <iostream>
#include <vector>
#define MAXVERTEX 10
using namespace std;
/*
*顶点类
*/
struct Vertex {
//编号
int vid;
//数据
char val;
//与之相邻的边数
int edges;
//是否访问过
bool isVisited;
//前驱节点编号
int pvid;
Vertex() {
this->vid=-1;
this->edges=0;
this->isVisited=false;
}
Vertex(int vid,char val) {
this->vid=vid;
this->edges=0;
this->val=val;
this->isVisited=false;
}
};
图类： 先在图类提供常规API（对顶点的维护函数，添加顶点和添加顶点之间的关系）。
/*
* 图类
*/
class Graph {
private:
//所有顶点
Vertex allVertex[MAXVERTEX];
//二维矩阵，存储顶点关系（边）
int matrix[MAXVERTEX][MAXVERTEX];
//顶点数量
int num;
public:
Graph() {
this->num=0;
for(int i=0; i<MAXVERTEX; i++) {
for(int j=0; j<MAXVERTEX; j++) {
this->matrix[i][j]=0;
}
}
}
/*
*添加顶点,返回顶点编号
*/
int addVertex(char val) {
Vertex ver(this->num,val);
this->allVertex[this->num]=ver;
return this->num++;
}
/*
*添加顶点之间的关系
*/
void addEdge(int from,int to) {
//无向图中，需要双向添加
this->allVertex[from].edges++;
this->matrix[from][to]=1;
this->allVertex[to].edges++;
this->matrix[to][from]=1;
}
/*
*深度搜索算法找环
*/
void findCycle() { }
/*
*显示矩阵中边信息
*/
void showEdges() {
for(int i=0; i<this->num; i++) {
for(int j=0; j<this->num; j++) {
cout<<this->matrix[i][j]<<"\t";
}
cout<<endl;
}
}
};
下图的子图A、B、E、D就是基环树。现使用代码构建下图：
//测试
int main() {
Graph graph;//=new Graph();
//添加顶点
int aid= graph.addVertex('A');
int bid= graph.addVertex('B');
int cid= graph.addVertex('C');
int did= graph.addVertex('D');
int eid= graph.addVertex('E');
//添加顶点之间关系
graph.addEdge(aid,bid); //A ---- B
graph.addEdge(aid,eid); //A --- E
graph.addEdge(bid,eid); //B ---- E
graph.addEdge(did,eid); // E----D
graph.showEdges();
return 0;
}
确认图的构建是否正确。
核心函数： 使用深度搜索算法检查图中是否存在环。
/*
*深度搜索算法找环
*/
void findCycle(int from) {
//记录连通分量中的边数
int sides=0;
//栈
stack<int> myStack;
//初始化栈
myStack.push(from);
//标志已经入过栈
this->allVertex[from].isVisited=true;
//存储搜索过的顶点
vector<int> vers;
//出栈操作
while( !myStack.empty() ) {
//出栈
int vid= myStack.top();
//存储搜索顶点
vers.push_back(vid);
//删除
myStack.pop();
//检查相邻节点
for(int i=0; i<this->num; i++ ) {
if( this->matrix[vid][i]==1 ) {
// i 是 from 的相邻顶点
sides++;
//标志此边已经被记录
this->matrix[vid][i]=-1;
if(this->allVertex[i].isVisited==false ) {
//边对应顶点是否入过栈
myStack.push(i);
this->allVertex[i].isVisited=true;
}
}
}
}
//输出搜索结果
cout<<"输出连通分量中的顶点:"<<endl;
for(int i=0; i<vers.size(); i++)
cout<< this->allVertex[vers[i]].val<<"\t";
cout<<endl;
//存储搜索结果
allConns.push_back(vers);
//检查环
if(sides>=vers.size() && vers.size()>3 ) {
//边数大于或等于搜索过的顶点数。表示搜索过的顶点在一个集合中，且有环
cout<<"存在环："<<endl;
for(int i=0; i<vers.size(); i++) {
if( this->allVertex[vers[i]].edges>=2 ) {
cout<<this->allVertex[vers[i]].val<<"->\t";
}
}
cout<<endl;
}
//检查是否还有其它连通分量
for(int i=0; i<this->num; i++) {
bool isExist=false;
//是否已经搜索
for(int j=0; j<allConns.size(); j++) {
auto res = find( begin( allConns[j] ), end( allConns[j] ),this->allVertex[i].vid );
if(res!=end(allConns[j] ) ) {
//搜索过
isExist=true;
break;
}
}
if(!isExist) {
findCycle(this->allVertex[i].vid );
}
}
}
//显示图中所有连通分量
void showConn() {
cout<<"图中存在"<<allConns.size()<<"个连通分量"<<endl;
}
测试：
int main() {
//省略……
graph.showEdges();
graph.findCycle(0);
graph.showConn();
graph.showEdges();
return 0;
}
输出结果：
3. 总结
本文讲解怎么使用深度搜索算法在无向图中查找环，当然，也可以使用广度搜索算法实现。
检查图中连通性的最好的方案是使用并查集。
本文共计3801个文字，预计阅读时间需要16分钟。
1. 前言：针对基环树的讲解 - 上篇：以理解连通分量、环及使用深度优先搜索算法检查连通性和环为主 - 下篇：以基于基环树结构的应用为主
2. 什么是基环树？ - 所谓基环树，指的是...
1. 前言
对于基环树的讲解，分上、下 2 篇，上篇以理解连通分量、环以及使用深度搜索算法检查连通性和环为主，下篇以基于基环树结构的应用为主。
什么是基环树？
所谓基环树指由n个节点n条边所构建而成的连通图。
如下图所示，树结构中共有 7 个节点， 6 条边。此时在树结构上添加一条边，必然会形成一个树环。因树结构中有环，故得此名。基环树也称为环套树。
如下图基环树结构中有 7 个节点，7 条边。
上述为无向边基环树。针对于有向边，基环树分：
- 内向树：树中每个点有且仅有一条出边(或者说每个节点的出度为
1)。
- 外向树：树中每个点有且仅有一条入边(或者说每个点的入度为
1)。
基于基环树有一项基本操作，寻找基环树上的环。
下文将深入讲解如何使用深度搜索算法在无向图中查找环结构。
2. 查找环
在图中查找环的常用的算法有：
- 深度搜索算法。
- 广度搜索算法。
- 并查集。
- 拓扑排序算法。
广度和深度搜索是原生算法，面对较复杂的图结构时，略显拙劣。较优的方案是使用优化过的并查集和拓扑排序算法，其在性能和技巧上都很精妙。
Tips： 关于并查集和拓扑排序算法可查阅我的相关博文。
2.1 问题分析
起点和终点相同的路径称为回路或称为环（Cycle），除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，本文仅对简单回路进行讨论。
Tips： 一般而言，回路至少需要
3个顶点。
图中是否有环的前提条件：边数至少要等于顶点数。
所以对于有 n个顶点的无向（有向）图，是否存在环，可以先检查边的数量 m与顶点数量之间的关系。
Tips： 本文主要以无向图为讨论对象。
- 如果
m=n-1。可以是下面的几种情况。
-
一个连通分量图情况。可以理解为以任何一个顶点为根节点构建成的树结构，此时连通分量为
1，显然此情况无法成环。Tips： 所谓连通图，指任意两个顶点之间都有路径的图。
-
上文说过，如果存在回路，顶点数量和边数至少要相等，这句话不能狭义地诠释为如果边数小于顶点数，则图中无环。
当
m=n-1时，顶点数可以拆分成n=m+1。这里遵循一个拆分原则，尽可能在已有边数的基础上成全图中某些顶点成环的要求。如下图所示，连通分量有
2个，其中一个子图中存在一个环。所以当边数少于顶点数时，需要讨论是否存在子图。
也可以是如下几种图形：
m<n-1时，如果m<=2则无法构建成环。其它情况下都能构建出一个有环的子图。
- 当
m>=n因为边数已经大于顶点数，显然图中有环。
2.2 深度搜索算法思想
2.2.1 连通分量
可以使用深度搜索算法查找图中是否有环，先了解一下深度搜索算法的搜索流程。
Tips： 深度搜索算法可以使用递归和非递归实现。本质是使用栈进行数据存储。
- 先创建一个栈(非递归实现)，用来存储搜索到的顶点。
- 以
A顶点为出发点，且把A顶点压入栈中，用于初始化栈。并在图的A顶点上做已入栈的标志。
- 查询出与
A顶点相邻的顶点B、E，并且压入栈中。
- 继续查询与
E顶点相邻的顶点（即入栈操作完成后，再查询与栈顶元素相邻的顶点）D，且压入栈中。
- 检查与
D顶点相邻的顶点C，且压入栈中。
经过上述操作后，可发现图结构中所有顶点全部被压入栈中，此时，能证明什么？
至少有一点是可以证明的：栈中的顶点在一个集合或在一个连通分量上。
使用如上搜索方案时，是否能找到此连通分量上的所有顶点？
先看下图的搜索结果：
当查询与 D顶点相邻的顶点时，因 D和C没有连通性，故C无法入栈。栈中的顶点在一个连通分量上，是不容质疑的，而实际上 C也是此连通分量上的一份子。
所以，使用仅入栈不出栈的搜索方案，无法找到同一个连通分量上的所有顶点。
可以把深度搜索方案改一下，采用入栈、出栈形式。
- 初始
A入栈。
A出栈，找到与A相邻的顶点B、E，且入栈。
E出栈，找到与E相邻的D顶点，且让其入栈。
D出栈，因没有与D相邻的顶点（每个顶点只能入一次栈）可入栈。继续B出栈，因C是与之相邻的顶点且没有入过栈，C入栈。
- 最后
C出栈，栈空。
至此，可以得到一个结论：
- 在一次深度搜索过程中，入过栈的顶点都在一个集合中（或一个连通分量上）。
- 使用出栈、入栈方案时，可以保证搜索到一个连通分量上的所有顶点。
**Tips： **使用广度搜索一样能找到一个连通分量上的所有顶点。
原理很简单，深度搜索是按纵深方式进行搜索的(类似于一条线上的蚂蚱)，在互相有关联的纵深线上的顶点能被搜索到。
如下图所示：从A开始，有左、右两条纵深线，在搜索完左边的纵深线后。
可以继续搜索另一条纵深线。
一次深度搜索只能检查到一条连通分量。如果图中存在多个连通分量时，需要使用多次深度搜索算法。如下图所示：
连通分量与找环有什么关系？
连通分量与环之间有很一个简单的关系：环一定是存在一个连通分量上。找环之前，先要确定目标顶点是不是在一个连通分量上。否则，都不在一起，还找什么环？
是否在一个连通分量上的顶点一定有环？
如下图，所有顶点都在一个连通分量中，实际情况是，图没有环。所以，仅凭顶点全部在一个连通分量上，是无法得到图中一定有环的结论。
那么，使用深度搜索算法在图中搜索时，怎么证明图中有环？
根据前面的推断，可以得出结论：
- 所有搜索的顶点在一个连通分量上，且图或子图边数大于或等于顶点数时，那么图或子图中必然存在环。
那么？环上的顶点有什么特点？
如果图中存在环，那么，环上每个顶点必然至少有 2条边分别和环上另 2 个顶点相连，边的数量决定与其相邻顶点的数量。
Tips：道理很简单，如果有
n个人通过手牵手围成一个圈，如果其中有一个人只原意出一只手，则圈是无法形成的。 可以把此人移走，剩余人可以围成一个圈。
2.2.2 小结
查询环上的顶点时，需要满足如下几个要求：
- 所有顶点在一个连通分量上。
- 连通分量上的边数要大于或等于顶点数。
- 环上至少有
2条边的顶点可认定是环上的顶点。
2.3 编码实现
顶点类：
#include <iostream>
#include <vector>
#define MAXVERTEX 10
using namespace std;
/*
*顶点类
*/
struct Vertex {
//编号
int vid;
//数据
char val;
//与之相邻的边数
int edges;
//是否访问过
bool isVisited;
//前驱节点编号
int pvid;
Vertex() {
this->vid=-1;
this->edges=0;
this->isVisited=false;
}
Vertex(int vid,char val) {
this->vid=vid;
this->edges=0;
this->val=val;
this->isVisited=false;
}
};
图类： 先在图类提供常规API（对顶点的维护函数，添加顶点和添加顶点之间的关系）。
/*
* 图类
*/
class Graph {
private:
//所有顶点
Vertex allVertex[MAXVERTEX];
//二维矩阵，存储顶点关系（边）
int matrix[MAXVERTEX][MAXVERTEX];
//顶点数量
int num;
public:
Graph() {
this->num=0;
for(int i=0; i<MAXVERTEX; i++) {
for(int j=0; j<MAXVERTEX; j++) {
this->matrix[i][j]=0;
}
}
}
/*
*添加顶点,返回顶点编号
*/
int addVertex(char val) {
Vertex ver(this->num,val);
this->allVertex[this->num]=ver;
return this->num++;
}
/*
*添加顶点之间的关系
*/
void addEdge(int from,int to) {
//无向图中，需要双向添加
this->allVertex[from].edges++;
this->matrix[from][to]=1;
this->allVertex[to].edges++;
this->matrix[to][from]=1;
}
/*
*深度搜索算法找环
*/
void findCycle() { }
/*
*显示矩阵中边信息
*/
void showEdges() {
for(int i=0; i<this->num; i++) {
for(int j=0; j<this->num; j++) {
cout<<this->matrix[i][j]<<"\t";
}
cout<<endl;
}
}
};
下图的子图A、B、E、D就是基环树。现使用代码构建下图：
//测试
int main() {
Graph graph;//=new Graph();
//添加顶点
int aid= graph.addVertex('A');
int bid= graph.addVertex('B');
int cid= graph.addVertex('C');
int did= graph.addVertex('D');
int eid= graph.addVertex('E');
//添加顶点之间关系
graph.addEdge(aid,bid); //A ---- B
graph.addEdge(aid,eid); //A --- E
graph.addEdge(bid,eid); //B ---- E
graph.addEdge(did,eid); // E----D
graph.showEdges();
return 0;
}
确认图的构建是否正确。
核心函数： 使用深度搜索算法检查图中是否存在环。
/*
*深度搜索算法找环
*/
void findCycle(int from) {
//记录连通分量中的边数
int sides=0;
//栈
stack<int> myStack;
//初始化栈
myStack.push(from);
//标志已经入过栈
this->allVertex[from].isVisited=true;
//存储搜索过的顶点
vector<int> vers;
//出栈操作
while( !myStack.empty() ) {
//出栈
int vid= myStack.top();
//存储搜索顶点
vers.push_back(vid);
//删除
myStack.pop();
//检查相邻节点
for(int i=0; i<this->num; i++ ) {
if( this->matrix[vid][i]==1 ) {
// i 是 from 的相邻顶点
sides++;
//标志此边已经被记录
this->matrix[vid][i]=-1;
if(this->allVertex[i].isVisited==false ) {
//边对应顶点是否入过栈
myStack.push(i);
this->allVertex[i].isVisited=true;
}
}
}
}
//输出搜索结果
cout<<"输出连通分量中的顶点:"<<endl;
for(int i=0; i<vers.size(); i++)
cout<< this->allVertex[vers[i]].val<<"\t";
cout<<endl;
//存储搜索结果
allConns.push_back(vers);
//检查环
if(sides>=vers.size() && vers.size()>3 ) {
//边数大于或等于搜索过的顶点数。表示搜索过的顶点在一个集合中，且有环
cout<<"存在环："<<endl;
for(int i=0; i<vers.size(); i++) {
if( this->allVertex[vers[i]].edges>=2 ) {
cout<<this->allVertex[vers[i]].val<<"->\t";
}
}
cout<<endl;
}
//检查是否还有其它连通分量
for(int i=0; i<this->num; i++) {
bool isExist=false;
//是否已经搜索
for(int j=0; j<allConns.size(); j++) {
auto res = find( begin( allConns[j] ), end( allConns[j] ),this->allVertex[i].vid );
if(res!=end(allConns[j] ) ) {
//搜索过
isExist=true;
break;
}
}
if(!isExist) {
findCycle(this->allVertex[i].vid );
}
}
}
//显示图中所有连通分量
void showConn() {
cout<<"图中存在"<<allConns.size()<<"个连通分量"<<endl;
}
测试：
int main() {
//省略……
graph.showEdges();
graph.findCycle(0);
graph.showConn();
graph.showEdges();
return 0;
}
输出结果：
3. 总结
本文讲解怎么使用深度搜索算法在无向图中查找环，当然，也可以使用广度搜索算法实现。
检查图中连通性的最好的方案是使用并查集。