环和有向无环图

1. 概念

• 有向图的可达性：深度优先搜索和广度优先搜索，可应用于内存管理中内存回收
  有向无环图：一幅不含有向环的有向图
  实际应用：用于条件排序，如任务调度、课程安排、继承、排队等
• 拓扑排序：对有向图的所有顶点排序，使所有有向边均从排在前面的元素指向排在后面的元素，只有有向无环图才能实现拓扑排序

2. 有向环的检测问题

思路：深度优先搜索或广度优先搜索，遍历顶点，遇到顶点被标记过则有向图存在环

图片

代码实现：

public class DirecttedCycle
{
    private boolean[] marked;   //标记数组
    private int[] edgeTo;            //从起点到一个顶点的已知路径上的最后一个顶点
    private Stack<Integer> cycle;   // 有向环的所有顶点
    private boolean[] onstack;         // 遍历的所有顶点？
    public DirectedCycle(Digraph G)
    {
        onstack = new boolean[G.V()];
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        for(int v = 0; v < G.V(); v++)
        {
        if(!marked[v]) dfs(G, v);
        }      
   }
   private void dfs(Digraph G, int v)
   {
   }
    
}