1. 前言
對于基環(huán)樹的講解，分上、下 2 篇，上篇以理解連通分量、環(huán)以及使用深度搜索算法檢查連通性和環(huán)為主，下篇以基于基環(huán)樹結(jié)構(gòu)的應(yīng)用為主。
什么是基環(huán)樹？
所謂基環(huán)樹指由n個節(jié)點n條邊所構(gòu)建而成的連通圖。
如下圖所示，樹結(jié)構(gòu)中共有 7 個節(jié)點， 6 條邊。此時在樹結(jié)構(gòu)上添加一條邊，必然會形成一個樹環(huán)。因樹結(jié)構(gòu)中有環(huán)，故得此名?；h(huán)樹也稱為環(huán)套樹。
如下圖基環(huán)樹結(jié)構(gòu)中有 7 個節(jié)點，7 條邊。
上述為無向邊基環(huán)樹。針對于有向邊，基環(huán)樹分：
-
內(nèi)向樹：樹中每個點有且僅有一條出邊(或者說每個節(jié)點的出度為
1)。
-
外向樹：樹中每個點有且僅有一條入邊(或者說每個點的入度為
1)。
基于基環(huán)樹有一項基本操作，尋找基環(huán)樹上的環(huán)。
下文將深入講解如何使用深度搜索算法在無向圖中查找環(huán)結(jié)構(gòu)。
2. 查找環(huán)
在圖中查找環(huán)的常用的算法有：
- 深度搜索算法。
- 廣度搜索算法。
- 并查集。
- 拓?fù)渑判蛩惴ā?/li>
廣度和深度搜索是原生算法，面對較復(fù)雜的圖結(jié)構(gòu)時，略顯拙劣。較優(yōu)的方案是使用優(yōu)化過的并查集和拓?fù)渑判蛩惴?/code>，其在性能和技巧上都很精妙。
Tips： 關(guān)于并查集和拓?fù)渑判蛩惴刹殚單业南嚓P(guān)博文。
2.1 問題分析
起點和終點相同的路徑稱為回路或稱為環(huán)（Cycle），除第一個頂點與最后一個頂點之外，其他頂點不重復(fù)出現(xiàn)的回路稱為簡單回路，本文僅對簡單回路進行討論。
Tips： 一般而言，回路至少需要
3個頂點。
圖中是否有環(huán)的前提條件：邊數(shù)至少要等于頂點數(shù)。
所以對于有 n個頂點的無向（有向）圖，是否存在環(huán)，可以先檢查邊的數(shù)量 m與頂點數(shù)量之間的關(guān)系。
Tips： 本文主要以無向圖為討論對象。
- 如果
m=n-1。可以是下面的幾種情況。
-
一個連通分量圖情況?？梢岳斫鉃橐匀魏我粋€頂點為根節(jié)點構(gòu)建成的樹結(jié)構(gòu)，此時連通分量為
1，顯然此情況無法成環(huán)。Tips： 所謂連通圖，指任意兩個頂點之間都有路徑的圖。
-
上文說過，如果存在回路，頂點數(shù)量和邊數(shù)至少要相等，這句話不能狹義地詮釋為如果邊數(shù)小于頂點數(shù)，則圖中無環(huán)。
當(dāng)
m=n-1時，頂點數(shù)可以拆分成n=m+1。這里遵循一個拆分原則，盡可能在已有邊數(shù)的基礎(chǔ)上成全圖中某些頂點成環(huán)的要求。如下圖所示，連通分量有
2個，其中一個子圖中存在一個環(huán)。所以當(dāng)邊數(shù)少于頂點數(shù)時，需要討論是否存在子圖。
也可以是如下幾種圖形：
-
m<n-1時，如果m<=2則無法構(gòu)建成環(huán)。其它情況下都能構(gòu)建出一個有環(huán)的子圖。
- 當(dāng)
m>=n因為邊數(shù)已經(jīng)大于頂點數(shù)，顯然圖中有環(huán)。
2.2 深度搜索算法思想
2.2.1 連通分量
可以使用深度搜索算法查找圖中是否有環(huán)，先了解一下深度搜索算法的搜索流程。
Tips： 深度搜索算法可以使用遞歸和非遞歸實現(xiàn)。本質(zhì)是使用棧進行數(shù)據(jù)存儲。
- 先創(chuàng)建一個棧(非遞歸實現(xiàn))，用來存儲搜索到的頂點。
- 以
A頂點為出發(fā)點，且把A頂點壓入棧中，用于初始化棧。并在圖的A頂點上做已入棧的標(biāo)志。
- 查詢出與
A頂點相鄰的頂點B、E，并且壓入棧中。
- 繼續(xù)查詢與
E頂點相鄰的頂點（即入棧操作完成后，再查詢與棧頂元素相鄰的頂點）D，且壓入棧中。
- 檢查與
D頂點相鄰的頂點C，且壓入棧中。
經(jīng)過上述操作后，可發(fā)現(xiàn)圖結(jié)構(gòu)中所有頂點全部被壓入棧中，此時，能證明什么？
至少有一點是可以證明的：棧中的頂點在一個集合或在一個連通分量上。
使用如上搜索方案時，是否能找到此連通分量上的所有頂點？
先看下圖的搜索結(jié)果：
當(dāng)查詢與 D頂點相鄰的頂點時，因 D和C沒有連通性，故C無法入棧。棧中的頂點在一個連通分量上，是不容質(zhì)疑的，而實際上 C也是此連通分量上的一份子。
所以，使用僅入棧不出棧的搜索方案，無法找到同一個連通分量上的所有頂點。
可以把深度搜索方案改一下，采用入棧、出棧形式。
- 初始
A入棧。
-
A出棧，找到與A相鄰的頂點B、E，且入棧。
-
E出棧，找到與E相鄰的D頂點，且讓其入棧。
-
D出棧，因沒有與D相鄰的頂點（每個頂點只能入一次棧）可入棧。繼續(xù)B出棧，因C是與之相鄰的頂點且沒有入過棧，C入棧。
- 最后
C出棧，?？铡?/li>
至此，可以得到一個結(jié)論：
- 在一次深度搜索過程中，入過棧的頂點都在一個集合中（或一個連通分量上）。
- 使用出棧、入棧方案時，可以保證搜索到一個連通分量上的所有頂點。
**Tips： **使用廣度搜索一樣能找到一個連通分量上的所有頂點。
原理很簡單，深度搜索是按縱深方式進行搜索的(類似于一條線上的螞蚱)，在互相有關(guān)聯(lián)的縱深線上的頂點能被搜索到。
如下圖所示：從A開始，有左、右兩條縱深線，在搜索完左邊的縱深線后。
可以繼續(xù)搜索另一條縱深線。
一次深度搜索只能檢查到一條連通分量。如果圖中存在多個連通分量時，需要使用多次深度搜索算法。如下圖所示：
連通分量與找環(huán)有什么關(guān)系？
連通分量與環(huán)之間有很一個簡單的關(guān)系：環(huán)一定是存在一個連通分量上。找環(huán)之前，先要確定目標(biāo)頂點是不是在一個連通分量上。否則，都不在一起，還找什么環(huán)？
是否在一個連通分量上的頂點一定有環(huán)？
如下圖，所有頂點都在一個連通分量中，實際情況是，圖沒有環(huán)。所以，僅憑頂點全部在一個連通分量上，是無法得到圖中一定有環(huán)的結(jié)論。
那么，使用深度搜索算法在圖中搜索時，怎么證明圖中有環(huán)？
根據(jù)前面的推斷，可以得出結(jié)論：
- 所有搜索的頂點在一個連通分量上，且圖或子圖邊數(shù)大于或等于頂點數(shù)時，那么圖或子圖中必然存在環(huán)。
那么？環(huán)上的頂點有什么特點？
如果圖中存在環(huán)，那么，環(huán)上每個頂點必然至少有 2條邊分別和環(huán)上另 2 個頂點相連，邊的數(shù)量決定與其相鄰頂點的數(shù)量。
Tips：道理很簡單，如果有
n個人通過手牽手圍成一個圈，如果其中有一個人只原意出一只手，則圈是無法形成的。 可以把此人移走，剩余人可以圍成一個圈。
2.2.2 小結(jié)
查詢環(huán)上的頂點時，需要滿足如下幾個要求：
- 所有頂點在一個連通分量上。
- 連通分量上的邊數(shù)要大于或等于頂點數(shù)。
- 環(huán)上至少有
2條邊的頂點可認(rèn)定是環(huán)上的頂點。
2.3 編碼實現(xiàn)
頂點類：
#include <iostream>
#include <vector>
#define MAXVERTEX 10
using namespace std;
/*
*頂點類
*/
struct Vertex {
//編號
int vid;
//數(shù)據(jù)
char val;
//與之相鄰的邊數(shù)
int edges;
//是否訪問過
bool isVisited;
//前驅(qū)節(jié)點編號
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;
}
};
圖類： 先在圖類提供常規(guī)API（對頂點的維護函數(shù)，添加頂點和添加頂點之間的關(guān)系）。
/*
* 圖類
*/
class Graph {
private:
//所有頂點
Vertex allVertex[MAXVERTEX];
//二維矩陣，存儲頂點關(guān)系（邊）
int matrix[MAXVERTEX][MAXVERTEX];
//頂點數(shù)量
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++;
}
/*
*添加頂點之間的關(guān)系
*/
void addEdge(int from,int to) {
//無向圖中，需要雙向添加
this->allVertex[from].edges++;
this->matrix[from][to]=1;
this->allVertex[to].edges++;
this->matrix[to][from]=1;
}
/*
*深度搜索算法找環(huán)
*/
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就是基環(huán)樹?，F(xiàn)使用代碼構(gòu)建下圖：
//測試
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');
//添加頂點之間關(guān)系
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;
}
確認(rèn)圖的構(gòu)建是否正確。
核心函數(shù)： 使用深度搜索算法檢查圖中是否存在環(huán)。
/*
*深度搜索算法找環(huán)
*/
void findCycle(int from) {
//記錄連通分量中的邊數(shù)
int sides=0;
//棧
stack<int> myStack;
//初始化棧
myStack.push(from);
//標(biāo)志已經(jīng)入過棧
this->allVertex[from].isVisited=true;
//存儲搜索過的頂點
vector<int> vers;
//出棧操作
while( !myStack.empty() ) {
//出棧
int vid= myStack.top();
//存儲搜索頂點
vers.push_back(vid);
//刪除
myStack.pop();
//檢查相鄰節(jié)點
for(int i=0; i<this->num; i++ ) {
if( this->matrix[vid][i]==1 ) {
// i 是 from 的相鄰頂點
sides++;
//標(biāo)志此邊已經(jīng)被記錄
this->matrix[vid][i]=-1;
if(this->allVertex[i].isVisited==false ) {
//邊對應(yīng)頂點是否入過棧
myStack.push(i);
this->allVertex[i].isVisited=true;
}
}
}
}
//輸出搜索結(jié)果
cout<<"輸出連通分量中的頂點:"<<endl;
for(int i=0; i<vers.size(); i++)
cout<< this->allVertex[vers[i]].val<<"\t";
cout<<endl;
//存儲搜索結(jié)果
allConns.push_back(vers);
//檢查環(huán)
if(sides>=vers.size() && vers.size()>3 ) {
//邊數(shù)大于或等于搜索過的頂點數(shù)。表示搜索過的頂點在一個集合中，且有環(huán)
cout<<"存在環(huán)："<<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;
//是否已經(jīng)搜索
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;
}
輸出結(jié)果：
3. 總結(jié)
本文講解怎么使用深度搜索算法在無向圖中查找環(huán)，當(dāng)然，也可以使用廣度搜索算法實現(xiàn)。文章來源：http://www.zghlxwxcb.cn/news/detail-430804.html
檢查圖中連通性的最好的方案是使用并查集。文章來源地址http://www.zghlxwxcb.cn/news/detail-430804.html
到了這里，關(guān)于C++ 樹進階系列之探討深度搜索算法查找環(huán)的細(xì)枝末節(jié)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
