环和有向无环图
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)
{
}
}
