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

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

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

思路：一旦我们找到了一条有向边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];
	onStac