¿Cómo puedo comprobar si un grafo dirigido acíclico es?

Question

¿Cómo puedo comprobar si un grafo dirigido acíclico es? ¿Y cómo se llama el algoritmo? Le agradecería una referencia.

Answer 1

Me gustaría tratar de ordenar el gráfico topológico , y si no puede, entonces que tiene ciclos.

Answer 2

Haciendo un simple profundidad de primera búsqueda es no lo suficientemente bueno para encontrar un ciclo. Es posible visitar un nodo varias veces en un DFS sin un ciclo existente. Dependiendo de donde se inicia, tampoco puede visitar todo el gráfico.

Puede comprobar para los ciclos en un componente conectado de un gráfico como sigue. Encuentra un nodo que tiene bordes salientes única. Si no existe tal nodo, entonces hay un ciclo. Iniciar un DFS en ese nodo. Cuando se atraviesa cada borde, comprobar si el borde apunta a un nodo que ya están en su pila. Esto indica la existencia de un ciclo. Si no encuentra dicho borde, no hay ciclos en que la componente conectado.

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

Como referencia, algoritmo componente fuertemente conectado de Tarjan está estrechamente relacionado . También le ayudará a encontrar los ciclos, no sólo informan de si existen o no.

Answer 3

Lema 22.11 en el libro Introduction to Algorithms (Segunda Edición) establece que:

  

A grafo dirigido G es acíclico si y sólo si una búsqueda en profundidad de G no da la espalda bordes

Answer 4

Solution1 : algoritmo Kahn para verificar ciclo . La idea principal: Mantener una cola donde se agregará nodo con cero en grados en cola. Luego pelar nodo uno por uno hasta cola está vacía. Comprobar si están existían de cualquier nodo de bordes.

Solución 2 :. Tarjan algoritmo para verificar el componente conectado Strong

Solution3 DFS . Utilice matriz de enteros a variable de estado actual de nodo: es decir, 0 --means este nodo no ha sido visitado antes.      -1 - significa que este nodo se ha visitado, y sus nodos hijos están siendo visitado.      1 - significa que este nodo se ha visitado, y está hecho. Así que si el estado de un nodo es -1, mientras que haciendo DFS, que significa que debe haber existido un ciclo.

Answer 5

La solución propuesta por ShuggyCoUk es incompleta, ya que podría no comprobar 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 timecomplexity O (n + m) o O (n ^ 2)

Answer 6

Sé que esto es un tema viejo, pero para los futuros investigadores que aquí hay una aplicación C # creé (sin afirmación de que es más eficiente!). Esto está diseñado para usar un número entero simple de identificar a cada nodo. Se puede decorar sin embargo que desee, siempre sus valores hash de objetos de nodo y de igual forma adecuada.

Para gráficos muy profundas que esto puede tener altos gastos indirectos, ya que crea un hashset en cada nodo en la profundidad (que se destruyen más de amplitud).

introducir el nodo desde el que desea buscar y tomar el camino a ese nodo.

• Para un gráfico con un único nodo raíz que envíe ese nodo y un hashset vacío
• Para un gráfico que tiene múltiples nodos raíz que envuelven esta en un foreach sobre esos nodos y aprobar una nueva hashset vacío para cada iteración

• Cuando la comprobación de ciclos por debajo de cualquier nodo dado, sólo tiene que pasar 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;
  }
  

Answer 7

No debe haber ningún borde posterior mientras se hace un seguimiento de los nodos DFS.Keep ya visitados mientras se hace DFS, si se encuentra con un borde entre el nodo y el nodo actual existente, a continuación, el gráfico tiene ciclo.

Answer 8

aquí es un código rápida de 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 la siguiente: un algoritmo DFS normal con una matriz para realizar un seguimiento de los nodos visitados, y una serie adicional que sirve como marcador para los nodos que llevaron al nodo actual, de manera que cuando haya que ejecutar un DFS para un nodo establecimos su elemento correspondiente en la matriz marcador como verdadero, de modo que cuando cada vez que un nodo visitado ya encontró, comprobamos si su correspondiente elemento de la matriz marcador es cierto, si es cierto, entonces es uno de los nodos que permiten a sí mismo (Por lo tanto, un ciclo), y el truco es siempre un DFS de un nodo rendimientos que establezca su marcador correspondiente volver a falso, por lo que si visitamos de nuevo desde otra ruta que no te dejes engañar.

Answer 9

Aquí está mi aplicación rubí de la href="http://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acyclic/" rel="nofollow"> cáscara de la hoja .

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

Sólo tenía esta pregunta en una entrevista de Google.

topológica Ordenar

Puede intenta 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 acíclico es si y sólo si esto se puede hacer.

La eliminación recursiva de la hoja

La forma recursiva eliminar nodos hoja hasta que no quede ninguna, y si hay más de un único nodo de la izquierda tienes un ciclo. A menos que esté equivocado, esto es O (V ^ 2 + VE).

DFS-estilo ~ O (n + m)

Sin embargo, un algoritmo DFS-esque eficiente, peor caso 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);
}