相关疑难解决方法(0)

检测有向图中所有周期的最有效算法是什么？

我有一个有向图表示需要执行的作业计划,作业是节点,依赖是边缘.我需要检测此图中循环的错误情况,从而导致循环依赖.

我知道进行拓扑排序的常用方法是使用DFS进行递归.但是你怎么用stack<int>而不是递归呢？我需要获得逆转后的订单,但我有点卡住了:

该图是一个vector<vector<int> >邻接列表

以下是我想用于拓扑排序的DFS

bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;

for(int i=0;i<MAX;i++){
    if(visited[i]==false){
        dfs.push(i);
    }   
    while(!dfs.empty()){
        int node=dfs.top();
        dfs.pop();
        visited[node]=true;
        newVec=graph[node]; //vector of neighboors
        for(it=newVec.begin();it!=newVec.end();it++){
            int son=*it;
            if(visited[son]==false){
                dfs.push(son);
            }
        }
    }
}

我发现了这篇SO帖子,建议在有向图中使用DFS进行循环检测由于回溯而更快.在这里我引用该链接:

深度优先搜索比广度优先搜索更有效,因为您可以更快地回溯.如果使用调用堆栈,它也更容易实现,但这依赖于没有溢出堆栈的最长路径.

此外,如果您的图表是定向的,那么您不仅要记住您是否访问过某个节点,还要记得您是如何到达该节点的.否则你可能会认为你找到了一个循环,但实际上你所拥有的是两个独立的路径A-> B,但这并不意味着存在路径B-> A. 通过深度优先搜索,您可以在下降时将节点标记为已访问,并在您回溯时将其标记为未标记.

为什么回溯必不可少？

有人可以用示例图解释给定A->B示例中的含义吗？

最后,我DFS在有向图中有一个循环检测代码,它不使用回溯但仍然检测循环O(E+V).

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited) {
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if (isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  v.setVisited(false);
  return false;
}