지시 된 그래프가 acyclic인지 어떻게 확인합니까?

StackOverflow https://stackoverflow.com/questions/583876

문제

지시 된 그래프가 acyclic인지 어떻게 확인합니까? 그리고 알고리즘은 어떻게 호출됩니까? 나는 참조에 감사드립니다.

도움이 되었습니까?

해결책

나는 노력할 것이다 토폴로지로 그래프를 정렬하십시오, 그리고 당신이 할 수 없다면, 그것은주기가 있습니다.

다른 팁

간단한 깊이 우선 검색을 수행하는 것이 있습니다 ~ 아니다 주기를 찾을만큼 충분합니다. 사이클이없는 DFS에서 노드를 여러 번 방문 할 수 있습니다. 시작 위치에 따라 전체 그래프를 방문하지 않을 수도 있습니다.

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

Rutger Prins가 지적한 것처럼 그래프가 연결되어 있지 않으면 각 연결된 구성 요소에서 검색을 반복해야합니다.

참조로서 Tarjan의 강력하게 연결된 구성 요소 알고리즘 밀접하게 관련되어 있습니다. 또한 사이클을 찾는 데 도움이 될뿐만 아니라 존재 여부를보고하는 것이 아닙니다.

이 책의 Lemma 22.11 Introduction to Algorithms (제 2 판)는 다음을 나타냅니다.

G의 깊이 우선 검색이 뒤쪽 가장자리가없는 경우에만 지시 된 그래프 G는 acyclic입니다.

솔루션 1： 사이클을 확인하기위한 Kahn 알고리즘. 메인 아이디어 : 큐에 큐에 추가되는 노드가 추가되는 대기열을 유지하십시오. 그런 다음 대기열이 비어있을 때까지 노드를 하나씩 껍질을 벗기십시오. 노드의 내부가 존재하는지 확인하십시오.

솔루션 2: 타잔 알고리즘 강력한 연결 구성 요소를 확인합니다.

솔루션 3: DFS. 정수 배열을 사용하여 노드의 현재 상태를 태그하십시오. 즉 0- 평균이 노드는 전에 방문하지 않았습니다. -1-이 노드가 방문되었고 어린이 노드가 방문되고 있음을 의미합니다. 1-이 노드가 방문되었고 완료되었음을 의미합니다. 따라서 노드의 상태가 -1 인 경우 DFS를 수행하는 경우주기가 있어야합니다.

Shuggycouk가 제공 한 솔루션은 모든 노드를 확인하지 않기 때문에 불완전합니다.


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

이것은 Timecomplexity 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)

아이디어는 다음과 같습니다. 방문 된 노드를 추적하기위한 배열이있는 일반 DFS 알고리즘과 현재 노드로 이어진 노드의 마커 역할을하는 추가 배열이므로 노드에 대한 DFS를 실행할 때 우리는 마커 배열에 해당 항목을 true로 설정하여 이미 방문한 노드가 발생했을 때 마커 배열의 해당 항목이 사실인지 확인합니다. 사실이라면 그 자체로 보낸 노드 중 하나입니다 (따라서 사이클), 그리고 트릭은 노드의 DFS가 반환 될 때마다 해당 마커를 다시 False로 설정하므로 다른 경로에서 다시 방문하면 속지 않습니다.

다음은 저의 루비 구현입니다 잎 잎 노드 알고리즘 껍질을 벗기십시오.

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

Google 인터뷰 에서이 질문이있었습니다.

토폴로지 정렬

v는 정점의 수이고 e는 가장자리 수입니다. 이 작업을 수행 할 수있는 경우에만 지시 된 그래프는 acyclic입니다.

재귀 잎 제거

남은 것이 없을 때까지 잎 노드를 재귀 적으로 제거하고 단일 노드 이상이 남은 경우 사이클이 있습니다. 내가 착각하지 않는 한, 이것은 O (v^2 + ve)입니다.

DFS 스타일 ~ O (N + M)

그러나 효율적인 DFS-esque 알고리즘, 최악의 O (V + E)는 다음과 같습니다.

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);
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top