有向图环检测、拓扑排序和有向欧拉图
内容概要：
- DAG图及有向图环检测
- 拓扑排序与环检测
- 有向欧拉图的欧拉回路Hierholzer算法
有向图环检测
在某些实际问题抽象出的图论问题中，要保证研究的图是一个有向无环图(Directed Acyclic Graph)，如程序模块的引用，任务调度，学习计划等等图模型，所以研究有向无环图是很有意义的。
有向图环检测思路
无向图进行遍历过程中如果一个被访问的顶点再次被访问到，且这个顶点不是它前一个节点，则说明该无向图图中存在环。而有向图由于边带有方向，所以和无向图环检测略有不同，在有向图中，可以加入当前路径标记，如果遍历到的顶点在当前路径上出现过，则说明图中存在环。
环检测算法实现
public class DirectedCycleDetection {
private Graph G;
private boolean hasCycle;
private boolean onPath[];// 有向图环检测辅助数据
private boolean[] visited;
public DirectedCycleDetection(Graph G){
this.G = G;
visited = new boolean[G.V()];
onPath = new boolean[G.V()];
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
if(dfs(v)) {
hasCycle = true;
break;
}
}
// 从 v 开始检测是否存在环
private boolean dfs(int v){
visited[v] = true;
onPath[v] = true;
for(int w: G.adj(v))
if(!visited[w]) {
if (dfs(w))
return true;
}
else if(onPath[w])
return true;
onPath[v] = false; // 回溯
return false;
}
public boolean hasCycle(){
return hasCycle;
}
public static void main(String args[]){
Graph g = new Graph("g2.txt", true);
DirectedCycleDetection cd = new DirectedCycleDetection(g);
System.out.println(cd.hasCycle());
}
}
拓扑排序
在图论中，一个有向无环图的顶点组成的序列，当且仅当满足下列条件时称为该图的一个拓扑排序：
- 每个顶点出现且仅出现一次
- 若顶点A在序列中排在B的前面，则在图中不存在从顶点B到顶点A的路径
拓扑排序算法
从拓扑排序的定义中可以看到，拓扑排序实际上是一种前驱后继关系，只有DAG图才有拓扑排序序列，所以可以这样来找到图的拓扑排序序列：
（1）从DAG图中选择一个没有前驱(入度为0)的顶点并输出
（2）从图中删除该顶点和该顶点的所有出边
（3）重复（1）和（2）直到DAG图为空则选择顶点的顺序就是拓扑排序序列
按照拓扑排序算法的过程同样可以做有向图环检测，如果拓扑排序算法进行到最后不存在无前驱的顶点时图仍不为空，说明图中存在环。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class TopoSort {
private Graph G;
private ArrayList<Integer> res;
private boolean hasCycle = false;
public TopoSort(Graph G){
if(!G.directed)
throw new IllegalArgumentException("TopoSort only works in directed graph!");
this.G = G;
res = new ArrayList<>();
int[] indegrees = new int[G.V()]; // 对入度的赋值数组操作不影响原图
Queue<Integer> q = new LinkedList<>();
for(int v = 0; v < G.V(); v ++) {
indegrees[v] = G.indegree(v);
if(indegrees[v] == 0) q.add(v);
}
while(!q.isEmpty()){
int cur = q.remove();
res.add(cur);
for(int w: G.adj(cur)){
indegrees[w] --;
if(indegrees[w] == 0) q.add(w);
}
}
if(res.size() != G.V()) {
hasCycle = true;
res.clear(); // 有环拓扑排序不存在
}
}
public boolean hasCycle(){
return hasCycle;
}
public ArrayList<Integer> result(){
return res;
}
public static void main(String args[]){
Graph g = new Graph("g2.txt", true);
TopoSort ts = new TopoSort(g);
System.out.println(ts.result());
}
}
拓扑排序的应用：课程学习顺序
LeetCode210
LeetCode210
这道题目就是一个典型的拓扑排序问题，构造好题目给定条件下图的邻接集合表示，然后按照拓扑排序算法，代码如下：
// C++
class Solution {
public:
vector<set<int>>g;
vector<int>res;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
g = vector<set<int>>(numCourses);
int *indegrees = new int[numCourses];
memset(indegrees, 0, sizeof(int) * numCourses);
for(int i=0;i<numCourses;i++)
indegrees[i] = 0;
for (int i = 0; i < prerequisites.size(); i++) {
g[prerequisites[i][1]].insert(prerequisites[i][0]);
indegrees[prerequisites[i][0]] ++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++)
if (indegrees[i] == 0)
q.push(i);
while (!q.empty()) {
int cur = q.front(); q.pop();
res.push_back(cur);
for (auto x : g[cur]) {
indegrees[x] --;
if (indegrees[x] == 0) {
q.push(x);
}
}
}
if (res.size() != numCourses) return {};
return res;
}
};
有向欧拉图的欧拉回路
入度和出度：顶点的出边条数称为该顶点的出度，顶点的入边条数称为该顶点的入度
初级回路：即简单回路，回路不经过重复的顶点
有向欧拉图与半欧拉图的判定：
- G是欧拉图
G中所有顶点的入度等于出度
- G是半欧拉图
求解有向欧拉回路Hierholzer算法
同无向欧拉回路的求解类似，有向欧拉回路的求解也是一步步构造出回路，最终找到欧拉回路。由有向欧拉图的充要条件：G是欧拉图G是若干个边不重的有向初级回路的并，我们可以先找到一个初级回路，而剩下的边一定还有初级回路，且这两个回路必有公共点，从而可以形成更大的回路，这样直到包括所有边，即可找到欧拉回路。时间复杂度为
，非常高效。
设置两个栈，curPath和loop。算法过程：
（1）选择任一顶点为起点，入栈curPath，深度搜索访问顶点，将经过的边都删除，经过的顶点入栈curPath。
（2）如果当前顶点没有相邻边，则将该顶点从curPath出栈到loop。
（3）最后loop栈中的顶点的出栈顺序，就是从起点出发的欧拉回路。
(注意和无向图的区别，无向图的欧拉回路逆序仍是欧拉回路，但有向图不是。)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
public class DirectedEulerLoop {
private Graph G;
public DirectedEulerLoop(Graph G){
this.G = G;
}
public boolean hasEulerLoop(){
for(int v = 0; v < G.V(); v ++)
if(G.indegree(v) != G.outdegree(v))
return false;
return true;
}
public ArrayList<Integer> result(){
// 返回欧拉回路结果
ArrayList<Integer> res = new ArrayList<>();// 充当Loop栈
if(!hasEulerLoop()) return res;
Graph g = (Graph) G.clone();// 用 G 的副本 g 寻找欧拉回路
// 删除 g 的边不会影响 G
Stack<Integer> stack = new Stack<>(); // curPath 栈
int curv = 0;
stack.push(curv);
while (!stack.isEmpty()){
if(g.outdegree(curv) != 0){
// 出度不为0说明当前顶点连的还有边，也就是还有路可走
stack.push(curv);
int w = g.adj(curv).iterator().next(); // 可迭代列表的第一个元素,即取g的任意邻点
g.removeEdge(curv, w);
curv = w;
}else {
// curv 到不了其它顶点，则已经找到一个环
res.add(curv);
curv = stack.pop();
}
}
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g3.txt", true);
DirectedEulerLoop el = new DirectedEulerLoop(g);
System.out.println(el.result());
}
}
