¿Cómo verifico si un gráfico dirigido es acíclico?

82

¿Cómo verifico si un gráfico dirigido es acíclico? ¿Y cómo se llama el algoritmo? Agradecería una referencia.

nes1983
fuente
Otro caso a favor de alguna forma de "arreglar" respuestas incorrectas en SO.
Sparr
2
Entonces, umm, lo que más me interesa es el tiempo necesario para encontrarlo. Entonces, solo necesito el algoritmo abstracto.
nes1983
debe atravesar todos los bordes y verificar todos los vértices para que el límite inferior sea O (| V | + | E |). DFS y BFS tienen la misma complejidad, pero DFS es más fácil de codificar si tiene recursividad, ya que administra la pila por usted ...
ShuggyCoUk
DFS no tiene la misma complejidad. Considere la gráfica con nodos {1 .. N} y aristas en la forma {(a, b) | a <b}. Ese gráfico es acíclico y, sin embargo, DFS sería O (n!)
FryGuy
1
DFS nunca es O (n!). Visita cada nodo una vez y cada borde como máximo dos veces. Entonces O (| V | + | E |) u O (n).
Jay Conrod

Respuestas:

95

Intentaría ordenar el gráfico topológicamente , y si no puedes, entonces tiene ciclos.

FryGuy
fuente
2
¿Cómo es que esto no tiene votos? ¡Es lineal en nodos + bordes, muy superior a las soluciones O (n ^ 2)!
Loren Pechtel
5
En muchos casos, un DFS (consulte la respuesta de J. Conrod) puede ser más fácil, especialmente si es necesario realizar un DFS de todos modos. Pero, por supuesto, esto depende del contexto.
sábado
1
El orden topológico estará en un bucle infinito, pero no nos dirá dónde ocurre el ciclo ...
Baradwaj Aryasomayajula
35

Hacer una búsqueda simple en profundidad no es suficiente para encontrar un ciclo. Es posible visitar un nodo varias veces en un DFS sin que exista un ciclo. Dependiendo de dónde empiece, es posible que tampoco visite el gráfico completo.

Puede comprobar los ciclos en un componente conectado de un gráfico de la siguiente manera. Encuentre un nodo que solo tenga bordes salientes. Si no existe tal nodo, entonces hay un ciclo. Inicie un DFS en ese nodo. Al atravesar cada borde, verifique si el borde apunta hacia un nodo que ya está en su pila. Esto indica la existencia de un ciclo. Si no encuentra tal borde, no hay ciclos en ese componente conectado.

Como señala Rutger Prins, si su gráfico no está conectado, debe repetir la búsqueda en cada componente conectado.

Como referencia, el algoritmo de componentes fuertemente conectado de Tarjan está estrechamente relacionado. También le ayudará a encontrar los ciclos, no solo a informar si existen.

Jay Conrod
fuente
2
Por cierto: una ventaja que "apunta a un nodo que ya está en su pila" a menudo se denomina "borde posterior" en la literatura, por razones obvias. Y sí, esto puede ser más simple que ordenar el gráfico topológicamente, especialmente si necesita hacer un DFS de todos modos.
sábado
Para que el gráfico sea acíclico, usted dice que cada componente conectado debe contener un nodo con solo bordes salientes. ¿Puede recomendar un algoritmo para encontrar los componentes conectados (a diferencia de los componentes "fuertemente" conectados) de un gráfico dirigido, para su uso por su algoritmo principal?
kostmo
@kostmo, si el gráfico tiene más de un componente conectado, entonces no visitará todos los nodos en su primer DFS. Realice un seguimiento de los nodos que ha visitado y repita el algoritmo con los nodos no visitados hasta que los alcance a todos. Básicamente, así es como funciona un algoritmo de componentes conectados de todos modos.
Jay Conrod
6
Si bien la intención de esta respuesta es correcta, la respuesta es confusa si se usa una implementación de DFS basada en pila: la pila utilizada para implementar DFS no contendrá los elementos correctos para probar. Es necesario agregar una pila adicional al algoritmo utilizado para realizar un seguimiento del conjunto de nodos ancestros.
Theodore Murdock
Tengo varias preguntas sobre tu respuesta. Los publiqué aquí: stackoverflow.com/questions/37582599/…
Ari
14

El lema 22.11 del libro Introduction to Algorithms(segunda edición) establece que:

Un gráfico dirigido G es acíclico si y solo si una búsqueda en profundidad de G no produce bordes posteriores

Filipe Miguel Fonseca
fuente
1
Esto es básicamente una versión abreviada de la respuesta de Jay Conrod :-).
sleske
Uno de los problemas del mismo libro parece sugerir que hay una | V | algoritmo de tiempo. Se responde aquí: stackoverflow.com/questions/526331/…
Justin
9

Solución 1 : algoritmo de Kahn para comprobar el ciclo . Idea principal: mantener una cola donde el nodo con cero grados se agregará a la cola. Luego despegue los nodos uno por uno hasta que la cola esté vacía. Compruebe si existen bordes internos de algún nodo.

Solución 2 : algoritmo de Tarjan para comprobar el componente conectado fuerte.

Solución 3 : DFS . Utilice una matriz de enteros para etiquetar el estado actual del nodo: es decir, 0 - significa que este nodo no ha sido visitado antes. -1: significa que este nodo ha sido visitado y sus nodos secundarios están siendo visitados. 1: significa que este nodo ha sido visitado y está hecho. Entonces, si el estado de un nodo es -1 mientras realiza DFS, significa que debe haber existido un ciclo.

Chris Su
fuente
1

La solución proporcionada por ShuggyCoUk está incompleta porque es posible que no verifique todos los nodos.


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

Esto tiene complejidad de tiempo O (n + m) u O (n ^ 2)


fuente
el mío es de hecho incorrecto, aunque lo
eliminé
3
O (n + m) <= O (n + n) = O (2n), O (2n)! = O (n ^ 2)
Artru
@Artru O (n ^ 2) cuando se usa la matriz de adyacencia, O (n + m) cuando se usa la lista de adyacencia para representar el gráfico.
0x450
Um ... m = O(n^2)ya que el gráfico completo tiene exactamente m=n^2bordes. Entonces eso es O(n+m) = O(n + n^2) = O(n^2).
Alex Reinking
1

Sé que este es un tema antiguo, pero para los futuros buscadores, aquí hay una implementación de C # que creé (¡no hay afirmación de que sea más eficiente!). Está diseñado para utilizar un número entero simple para identificar cada nodo. Puede decorarlo como desee, siempre que su objeto de nodo tenga valores hash e iguales correctamente.

Para gráficos muy profundos, esto puede tener una sobrecarga alta, ya que crea un conjunto de hash en cada nodo en profundidad (se destruyen en el ancho).

Ingresa el nodo desde el que desea buscar y la ruta a ese nodo.

  • Para un gráfico con un solo nodo raíz, envía ese nodo y un hashset vacío
  • Para un gráfico que tiene múltiples nodos raíz, envuelve esto en un foreach sobre esos nodos y pasa un nuevo hashset vacío para cada iteración
  • Al verificar ciclos debajo de cualquier nodo, simplemente pase ese nodo junto con un hashset vacío

    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;
    }
    
Mateo
fuente
1

No debe haber ningún borde posterior mientras realiza DFS. Mantenga un registro de los nodos ya visitados mientras realiza DFS, si encuentra un borde entre el nodo actual y el nodo existente, entonces el gráfico tiene un ciclo.

santhosh
fuente
1

aquí hay un código rápido para encontrar si un gráfico tiene 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)

La idea es así: un algoritmo dfs normal con una matriz para realizar un seguimiento de los nodos visitados, y una matriz adicional que sirve como marcador para los nodos que condujeron al nodo actual, de modo que siempre que ejecutemos una dfs para un nodo establecemos su elemento correspondiente en la matriz de marcadores como verdadero, de modo que siempre que se encuentre un nodo ya visitado, verifiquemos si su elemento correspondiente en la matriz de marcadores es verdadero, si es verdadero, entonces es uno de los nodos que se permite a sí mismo (por lo tanto, un ciclo), y el truco es que cada vez que un dfs de un nodo regresa, volvemos a establecer su marcador correspondiente en falso, de modo que si lo visitamos nuevamente desde otra ruta no nos engañemos.

m.eldehairy
fuente
1

Acabo de tener esta pregunta en una entrevista de Google.

Orden topológico

Puede intentar ordenar topológicamente, que es O (V + E) donde V es el número de vértices y E es el número de aristas. Un gráfico dirigido es acíclico si y solo si esto se puede hacer.

Eliminación recursiva de hojas

Elimina de forma recursiva los nodos hoja hasta que no quede ninguno, y si queda más de un nodo, tienes un ciclo. A menos que me equivoque, esto es O (V ^ 2 + VE).

Estilo DFS ~ O (n + m)

Sin embargo, un algoritmo eficiente al estilo DFS, el peor de los casos O (V + E), es:

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);
}
Tom Golden
fuente
0

Aquí está mi implementación ruby ​​del algoritmo de nodo peel off leaf .

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
neoneye
fuente