算法目标：在一个有向图中寻找出所有长度在3到7之间的环，环的数量可达百万级。
数据结构定义：
#define maxN 500000 vector<int> Vout[maxN]; // 存储每个结点出边所连的所有结点。Vout[i].size()即为所有的出度 vector<int> Vin[maxN]; // 存储每个结点入边所连的所有结点。Vin[i].size()即为所有的入度 vector<int> circles; // 存储构成环的所有结果路径 vector<int> tmpPath; bool visited[maxN];
1. 基本思路：
对图中的每个结点做深度为7的DFS搜索，保存符合条件的每个环。注意这里要搜索的是全部路径，而不是遍历图中的所有点，所以需要回溯。
在栈返回上一层时，得清空结点标记并弹出结点。
void search()
{
for (int i = 0; i < N; i++)
{
if (Vout[i].size() && Vin[i].size()) // 只有出入度不为0的结点才会构成环
{
dfs7(i, i, 1);
}
}
}
void dfs7(int head, int cur, int depth)
{
visited[cur] = true;
tmpPath.push_back(start);
for(int i = 0; i < Vout[cur].size(); ++i) // 遍历所有的出边
{
int v = Vout[cur][i];
if (v == head && depth >= 3 && depth <= 7) // 环的判定条件: Vout[cur]的孩子结点v为起始点head
{
tmpPath.push_back(v);
circles.push_back(tmpPath); // 得到一条结果
tmpPath.pop_back();
}
if (depth < 7) // 继续搜索
{
dfs7(head, v, depth + 1);
}
}
visited[cur] = false;
tmpPath.pop_back();
}
未完待续。。。
原文：https://www.cnblogs.com/yanghh/p/12765079.html