有向图(3)--寻找有向环

一时失言乱红尘 2022-08-18 02:35 190阅读 0赞

在和有向图相关的实际应用中，有向环特别重要。

从原则上来说，一幅有向图可能含有大量的环，在实际应用中，我们一般只会重点关注其中一小部分，或者只想知道它们是否存在。

思路：一旦我们找到了一条有向边v->w且w已经存在于栈中，就找到了一个环，因为栈表示的是一条由w到v的有向路径，而v->w正好补全了这个环。同时，如果没有找到这样的边，那就意味着这幅有向图是无环的。

#ifndef __DIRECTED_CYCLE_H__
    #define __DIRECTED_CYCLE_H__
    
    #include "Digraph.h"
    #include <stack>
    
    class DirectedCycle {
    private:
    	bool* marked;
    	int* edgeTo;
    	std::stack<int> cycle;	// 有向环中的所有顶点(如果存在)
    	bool* onStack;			// 递归调用的栈上的所有顶点
    
    public:
    	DirectedCycle(const Digraph& G);
    	~DirectedCycle() { delete[] marked; delete[] edgeTo; delete[] onStack; }
    
    	bool hasCycle()const { return !cycle.empty(); }
    	std::stack<int> getCycle()const { return cycle; }
    	
    private:
    	void dfs(const Digraph& G, int v);
    
    };
    
    // constructor
    DirectedCycle::DirectedCycle(const Digraph& G) {
    	int vNum = G.getV();
    	marked = new bool[vNum];
    	onStack = new bool[vNum];
    	edgeTo = new int[vNum];
    	for (int i = 0; i < vNum; ++i) {
    		marked[i] = onStack[i] = false;
    		edgeTo[i] = i;
    	}
    	for (int v = 0; v < vNum; ++v) {
    		if (!marked[v])
    			dfs(G, v);
    	}
    }
    
    void DirectedCycle::dfs(const Digraph& G, int v) {
    	onStack[v] = true;
    	marked[v] = true;
    	for (int w : G.getAdj(v)) {
    		// 如果判断存在环之后就不用执行以下的else,直接return
    		if (hasCycle()) return;
    		else if (!marked[w]) {
    			edgeTo[w] = v;
    			dfs(G, w);
    		}
    		// 存在有向环
    		else if (onStack[w]) {
    			for (int x = v; x != w; x = edgeTo[x])
    				cycle.push(x);
    			cycle.push(w);
    			cycle.push(v);
    		}
    	}
    	// 在有向子图中搜索完毕后将onStack置为false
    	onStack[v] = false;
    }
    
    
    #endif

测试 -main.cpp

#include "DirectedCycle.h"
    #include "Digraph.h"
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int vNum, eNum;
    	cin >> vNum >> eNum;
    	Digraph G(vNum);
    
    	int v, w;
    	for (int i = 0; i < eNum; ++i) {
    		cin >> v >> w;
    		G.addEdge(v, w);
    	}
    
    	DirectedCycle dc(G);
    
    	if (dc.hasCycle()) {
    		cout << "该有向图中存在环，其中一个环为：";
    		stack<int> stk = dc.getCycle();
    		while (!stk.empty()) {
    			cout << stk.top() << " ";
    			stk.pop();
    		}
    	}
    	else
    		cout << "该有向图中不存在环" << endl;
    
    	return 0;
    }

![SouthEast][]

[SouthEast]: /images/20220731/a8103310b5304bbdb1f31fef00cee5de.png