通过DFS求解有向图(邻接表存储)中所有简单回路

释放双眼,带上耳机,听听看~!

前言

查阅了网上许多关于通过DFS算法对有向图中所有简单回路的查找,发现有很多关于使用DFS求解有向回路中所有简单回路的帖子,(在按照节点编号情况下)但大多数仅仅寻找了编号递增的回路。又或者未对结果去重。P.S.下述有向图中所有节点均使用数字进行编号,如节点0、节点1 \\(\\cdots\\)

1. 算法描述

本算法基于DFS,思路与传统DFS基本类似,只不过在遍历过程中对所经过的路径通过一个栈进行保存,当找到回路时,检测此条回路是否已经在结果集中出现,若未出现,则将其放入结果集。本过程中比较关键的两步是DFS结果集去重

关于DFS。每当从一个新的顶点出发对其进行递归的深度遍历时,我们维护一个新的节点已访问数组visited[]以及一个一维的回路栈loopStack。当访问到节点v时,若v已经被访问,即visited[v]==true时,扫描栈中是节点v是否已经出现过,当节点v已经在栈中出现过,则说明此时出现一条回路,我们将其加入结果集。若节点v未被访问,此时置visited[v]=true并将节点v入栈,并对v的所有邻接点进行访问,重复以上操作。到最深处(即已无邻接点未遍历)进行回溯处理,即将栈顶元素退栈。

关于去重。当需要在结果集中加入新找到的一条回路时,需要对结果集扫描,判断此条回路是否已经出现过。但在一个有向图中很容易发现回路\\(0\\rightarrow1\\rightarrow2\\rightarrow3(\\rightarrow0)\\)与回路\\(2\\rightarrow3\\rightarrow1\\rightarrow0(\\rightarrow0)\\)是两条相同的回路,那么在结果集中我们需要对此类回路进行去重,此处我的具体做法是使用两个指针i、j对将要比较的两条回路同时进行扫描比较,指针i指向第一条回路的起始位置,指针j指向第二条回路中,与指针i指向位置元素相等的位置,记录两个回路中相等的元素个数count,当count==loop.size()时,我们称这两条回路为同一条回路,否则将新回路加入结果集。

算法具体步骤:

  1. 从v出发对图进行深度遍历若此节点已访问则转2,否则转3。
  2. 若此节点已经在loopStack中出现,表明有回路存在,判断回路是否已经在结果集loopStacks中出现,若没出现过,则放入结果集。
  3. 置Visited[v]=true,节点v入栈,对v的邻接顶点继续进行深搜。当搜索完所有邻接顶点,栈顶元素退栈。

2. 算法实现

完整代码在github,请点击这里
DFS部分实现

void DFS(int v) {
    if (visited[v] == 1) {
        int position = FindInVector(loopStack, v);
        if (position >=0) {
            vector<int> loop;
            //将环单独拿出并放入结果集
            for (int i = position; i < loopStack.size(); i++) {
                loop.push_back(loopStack[i]);
            }
            AddLoopStack(loop);
            return;
        }
        return;
    }
    visited[v] = true;
    loopStack.push_back(v);
    
    for (int j = 0; j < adjMatrixSize; j++) {
        if (adjMatrix[v][j] == 1)
            DFS(j);
    }
    
    loopStack.pop_back();
}

结果集去重部分

void AddLoopStack(vector<int> loop) {
    bool haveThisLoop = false;
    int count,begin;
    if (loopStacks.size() == 0)
        loopStacks.push_back(loop);
    else {
        for (int i = 0; i < loopStacks.size(); i++) {//遍历结果集中的每一个回路
            count = 0;
            begin = 0;
            if (loop.size() == loopStacks[i].size()) {//若长度相等则进一步比较
                //为方便比较,找到结果集中第i条回路中与loop进行匹配的起点
                for (int k = 0; k < loopStacks[i].size(); k++) {
                    if (loop[0] == loopStacks[i][k])
                        begin = k;
                }
                //j指针从待添加结果集的loop数组的头部开始扫描
                //k指针从上述所找出的与loop数组比较的起点开始扫描
                for (int j =0,k=begin; j < loop.size(); j++, k = (k + 1) % (loopStacks[i].size())) {
                    if (loop[j] == loopStacks[i][k])
                        count++;
                }
                if (count == loop.size()) {
                    //haveThisLoop = true;
                    //break;
                    return;
                }
            }
        }//end else
        
        loopStacks.push_back(loop);
    }
}

3. 算法复杂度分析

假设存在n个顶点,考虑最坏情况下,有向图为有向完全图,那么可能的回路个数就是\\(C_n^2+C_n^3+\\cdots+C_n^n=2^n-n-1\\)个回路,另外需要对n个顶点均需要DFS,而每条边都需要经过,加上去重的部分,所以时间复杂度为\\(O(n^32^n)\\),需要保存所有回路的空间,故空间复杂度为\\(O(2^n)\\)

参考资料

严蔚敏数据结构(C语言版)

人已赞赏
随笔日记

ELK(elasticsearch+kibana+logstash)搜索引擎(一): 环境搭建

2020-11-9 4:17:18

随笔日记

需求火爆!沙特阿美首发国际债券认购规模超1000亿美元

2020-11-9 4:17:20

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索