Como posso verificar se um grafo direcionado é acíclicos?

Question

Como posso verificar se um grafo direcionado é acíclicos? E como é o algoritmo chamado? Gostaria muito de receber uma referência.

Answer 1

Gostaria de tentar tipo do gráfico topologicamente , e se você não pode, em seguida, ele tem ciclos.

Answer 2

Fazendo uma profundidade-primeiro-busca simples é não bom o suficiente para encontrar um ciclo. É possível visitar um nó várias vezes em um DFS sem um ciclo existente. Dependendo de onde você começa, você também não pode visitar o gráfico inteiro.

Você pode verificar se há ciclos em um componente conectado de um gráfico a seguir. Encontrar um nó que tem bordas única saída. Se não existe tal nó, em seguida, existe um ciclo. Iniciar um DFS naquele nó. Ao atravessar cada aresta, verifique se os pontos de borda de volta a um nó já em seu stack. Isto indica a existência de um ciclo. Se você não encontrar tais borda, não há ciclos em que o componente conectado.

Como Rutger Prins aponta, se o gráfico não está conectado, você precisa repetir a pesquisa em cada componente conectado.

Como referência, Tarjan está fortemente ligado algoritmo componente está intimamente relacionado . Ele também irá ajudar a encontrar os ciclos, e não apenas relatar se eles existem.

Answer 3

Lema 22.11 na Introduction to Algorithms Book (Second Edition) afirma que:

Um gráfico G é acíclico dirigido se e somente se uma busca em profundidade de G não produz extremidades traseiras

Answer 4

Solution1 : algoritmo Kahn para verificar ciclo . idéia principal: Manter uma fila onde nó com zero graus será adicionado na fila. Em seguida, descolar um nó por um até fila está vazia. Verifique se qualquer nó é em-bordas são existiu.

Solution2 :. Tarjan algoritmo para verificar componente conectado forte

Solution3 : DFS . Use array de inteiros de status atual tag de nó: ou seja, 0 --means este nó não foi visto antes. -1 - meio deste nó foi visto, e seus nós filhos estão sendo visitados. 1 - meios este nó foi visto, e ele é feito. Então, se o status de um nó é -1 ao fazer DFS, isso significa que deve haver existido um ciclo.

Answer 5

A solução dada pela ShuggyCoUk é incompleta porque ele pode não verificar todos os nós.

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

Este tem timecomplexity O (n + m) ou O (n ^ 2)

Answer 6

Eu sei que este é um tema antigo, mas para os futuros pesquisadores aqui é um C # implementação eu criei (nenhuma reivindicação que é mais eficiente!). Isto é projetado para usar um inteiro simples para identificar cada nó. Você pode decorar que da maneira que quiser, desde que suas hashes objeto de nó e iguala corretamente.

Para gráficos muito profundo que isso pode ter alta sobrecarga, como ele cria um hashset em cada nó em profundidade (eles são destruídos mais de amplitude).

Você entrada do nó do qual você deseja pesquisar e tomar o caminho para esse nó.

• Para um gráfico com um nó raiz único que enviar esse nó e um hashset vazio
• Para um gráfico com vários nós raiz você quebrar isso em um foreach sobre esses nós e passar uma nova hashset vazia para cada iteração

• Quando a verificação de ciclos abaixo qualquer nó, apenas passar esse nó, juntamente com um hashset vazio

  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;
  }
  

Answer 7

Não deve haver qualquer extremidade traseira ao fazer DFS.Keep pista de nós já visitados ao fazer DFS, se você encontrar um limite entre nó atual e nó existente, em seguida, gráfico tem ciclo.

Answer 8

aqui é um código rápido de encontrar se um gráfico tem ciclos:

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)

A idéia é assim: um DFS normais algoritmo com uma matriz para manter o controle de nós visitados, e um conjunto adicional que serve como um marcador para os nós que levaram ao nó atual, de modo que sempre que nós executamos um DFS para um nó que definir o seu item correspondente na matriz marcador como verdadeira, de modo que sempre que um nó já visitou encontrou vamos verificar se o item correspondente na matriz marcador é verdade, se é verdade, então é um dos nós que permitem a si mesma (Daí um ciclo), e o truque é sempre um DFS de um nó retornos vamos definir a sua volta marcador correspondente à falsa, de modo que se nós visitado novamente a partir de uma outra rota que não se deixe enganar.

Answer 9

Aqui está minha implementação rubi do peel off folha nó algoritmo .

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

Answer 10

Apenas teve esta questão em uma entrevista Google.

topológica Sort

Pode tentar tipo topologicamente, que é O (V + E) em que V é o número de vértices, e E é o número de arestas. Um grafo direcionado é acíclico se e somente se isso pode ser feito.

Folha recursiva Remoção

Os recursivamente nós folha remove até que não haja nenhum à esquerda, e se há mais de um único nó deixado você tem um ciclo. Se não me engano, este é o (V ^ 2 + VE).

DFS-estilo ~ O (n + m)

No entanto, um algoritmo DFS-esque eficiente, o pior caso de 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);
}