유 방향 그래프가 비순환인지 어떻게 확인합니까?

유 방향 그래프가 비순환인지 어떻게 확인합니까?

---

유 방향 그래프가 비순환인지 어떻게 확인합니까? 그리고 알고리즘은 어떻게 호출됩니까? 참고 부탁드립니다.

---

나는 그래프를 토폴로지 적 으로 정렬 하려고하는데 , 할 수 없다면 사이클이있는 것입니다.

---

단순한 깊이 우선 검색은 주기를 찾기에 충분 하지 않습니다 . 주기가없는 DFS에서 노드를 여러 번 방문 할 수 있습니다. 시작 위치에 따라 전체 그래프를 방문하지 못할 수도 있습니다.

다음과 같이 그래프의 연결된 구성 요소에서주기를 확인할 수 있습니다. 나가는 가장자리 만있는 노드를 찾습니다. 그러한 노드가 없으면주기가 있습니다. 해당 노드에서 DFS를 시작합니다. 각 에지를 순회 할 때 에지가 이미 스택에있는 노드를 가리키는 지 확인하십시오. 이것은주기의 존재를 나타냅니다. 그러한 에지를 찾지 못하면 연결된 구성 요소에 사이클이 없습니다.

Rutger Prins가 지적했듯이 그래프가 연결되어 있지 않으면 연결된 각 구성 요소에 대해 검색을 반복해야합니다.

참고로 Tarjan의 강력한 연결 구성 요소 알고리즘 은 밀접한 관련이 있습니다. 또한주기가 있는지 여부를보고하는 것이 아니라주기를 찾는 데 도움이됩니다.

---

책 Introduction to Algorithms(제 2 판) 의 Lemma 22.11은 다음과 같이 설명합니다.

유 방향 그래프 G는 G의 깊이 우선 검색에서 후면 모서리가없는 경우에만 비순환입니다.

---

Solution1：Kahn 알고리즘은주기를 확인합니다 . 주요 아이디어 : 정도가 0 인 노드가 대기열에 추가되는 대기열을 유지합니다. 그런 다음 대기열이 비워 질 때까지 노드를 하나씩 떼어냅니다. 노드의 인에지가 존재하는지 확인하십시오.

Solution2 : 강력한 연결 구성 요소를 확인하는 Tarjan 알고리즘 .

솔루션 3 : DFS . 정수 배열을 사용하여 노드의 현재 상태에 태그를 지정합니다. 즉 0은이 노드가 이전에 방문한 적이 없음을 의미합니다. -1-이 노드가 방문되었으며 하위 노드가 방문 중임을 의미합니다. 1-이 노드가 방문되었으며 완료되었음을 의미합니다. 따라서 DFS를 수행하는 동안 노드의 상태가 -1이면주기가 존재해야 함을 의미합니다.

---

ShuggyCoUk가 제공하는 솔루션은 모든 노드를 검사하지 않을 수 있으므로 불완전합니다.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

이것은 시간 복잡도 O (n + m) 또는 O (n ^ 2)

---

나는 이것이 오래된 주제라는 것을 알고 있지만 미래의 검색자를 위해 여기에 내가 만든 C # 구현이 있습니다 (가장 효율적이라는 주장은 없습니다!). 이것은 각 노드를 식별하기 위해 간단한 정수를 사용하도록 설계되었습니다. 노드 개체 해시를 제공하고 적절하게 같으면 원하는대로 꾸밀 수 있습니다.

매우 깊은 그래프의 경우 각 노드에서 해시 세트를 생성하므로 오버 헤드가 높을 수 있습니다 (폭에 걸쳐 파괴됨).

검색하려는 노드와 해당 노드로가는 경로를 입력합니다.

• 단일 루트 노드가있는 그래프의 경우 해당 노드와 빈 해시 세트를 보냅니다.
• 루트 노드가 여러 개인 그래프의 경우 해당 노드에 대한 foreach로 래핑하고 각 반복마다 새로운 빈 해시 세트를 전달합니다.

• 주어진 노드 아래의주기를 확인할 때 빈 해시 세트와 함께 해당 노드를 전달하십시오.

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }
  

---

DFS 수행 중에는 백 엣지가 없어야하며 DFS를 수행하는 동안 이미 방문한 노드를 추적하여 현재 노드와 기존 노드 사이에 엣지를 만나면 그래프에주기가 있습니다.

---

다음은 그래프에주기가 있는지 확인하는 빠른 코드입니다.

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

The idea is like this : a normal dfs algorithm with an array to keep track of visited nodes , and an additional array which serves as a marker for the nodes that led to the current node,so that when ever we execute a dfs for a node we set its corresponding item in the marker array as true ,so that when ever an already visited node encountered we check if its corresponding item in the marker array is true , if its true then its one of the nodes that let to itself (hence a cycle) , and the trick is whenever a dfs of a node returns we set its corresponding marker back to false , so that if we visited it again from another route we don't get fooled .

---

Here is my ruby implementation of the peel off leaf node algorithm.

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

---

Just had this question in a Google interview.

Topological Sort

You can try to sort topologically, which is O(V + E) where V is the number of vertices, and E is the number of edges. A directed graph is acyclic if and only if this can be done.

Recursive Leaf Removal

The recursively remove leaf nodes until there are none left, and if there's more than a single node left you've got a cycle. Unless I'm mistaken, this is O(V^2 + VE).

DFS-style ~ O(n + m)

However, an efficient DFS-esque algorithm, worst case O(V + E), is:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}

참고URL : https://stackoverflow.com/questions/583876/how-do-i-check-if-a-directed-graph-is-acyclic