graph - studio - superponer graficas en r

¿Cómo detectar si un gráfico dirigido es cíclico?

Question

¿Cómo podemos detectar si un gráfico dirigido es cíclico? Pensé en usar la primera búsqueda de amplitud, pero no estoy seguro. ¿Algunas ideas?

Answer 1

Las pruebas de clasificación topológica sobre el gráfico dado lo guiarán a la solución. Si falla el algoritmo para topsort, es decir, que los bordes siempre deben dirigirse de una manera, significa que el gráfico contiene ciclos.

Answer 2

Lo que realmente necesita, creo, es un algoritmo de clasificación topológica como el que se describe aquí:

http://en.wikipedia.org/wiki/Topological_sorting

Si el gráfico dirigido tiene un ciclo, el algoritmo fallará.

Los comentarios / respuestas que he visto hasta ahora parecen estar perdiendo el hecho de que en un gráfico dirigido puede haber más de una manera de llegar del nodo X al nodo Y sin que haya ningún ciclo (dirigido) en el gráfico.

Answer 3

Otra solución simple sería un enfoque de marcaje y barrido. Básicamente, para cada nodo en el árbol lo marcas como "visitado" y luego pasas a sus hijos. Si alguna vez ves un nodo con la bandera "visted" establecida, sabes que hay un ciclo.

Si no es posible modificar el gráfico para incluir un bit "visitado", se puede usar un conjunto de punteros de nodo. Para marcar un nodo como visitado, coloque un puntero en el conjunto. Si el puntero ya está en el conjunto, hay un ciclo.

Answer 4

Use DFS para buscar si alguna ruta es cíclica

class Node<T> { T value; List<Node<T>> adjacent; }
class Graph<T>{
List<Node<T>> nodes;
public boolean isCyclicRec()
{
for (Node<T> node : nodes)
{
Set<Node<T>> initPath = new HashSet<>();
if (isCyclicRec(node, initPath))
{
return true;
}
}
return false;
}
private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
{
if (path.contains(currNode))
{
return true;
}
else
{
path.add(currNode);
for (Node<T> node : currNode.adjacent)
{
if (isCyclicRec(node, path))
{
return true;
}
else
{
path.remove(node);
}
}
}
return false;
}

Answer 5

Usualmente se usa la búsqueda de profundidad primero. No sé si BFS se aplica fácilmente.

En DFS , se construye un árbol de expansión por orden de visita. Si se visita un ancestro de un nodo en el árbol (es decir, se crea un borde posterior), detectamos un ciclo.

Consulte http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf para obtener una explicación más detallada.

Answer 6

enfoque: 1
¿Qué tal un nivel sin asignación para detectar un ciclo? Ej .: considere el siguiente gráfico. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D A medida que realiza un inicio DFS asignando un nivel no al nodo que visita (raíz A = 0). nivel no de nodo = padre + 1. Entonces A = 0, B = 1, D = 2, F = 3, G = 4 entonces, la recursión llega a D, entonces E = 3. No marque el nivel para G (G ya tiene un nivel no asignado que es más grande que E) Ahora E también tiene una ventaja a D. Así que la nivelación diría que D debería obtener un nivel no de 4. Pero D ya tiene asignado un "nivel inferior" 2. De este modo, cada vez que intentes asignar un número de nivel a un nodo mientras haces un DFS que ya tiene un número de nivel inferior establecido, sabrás que el gráfico dirigido tiene un ciclo.

approach2:
usa 3 colores blanco, gris, negro. coloree únicamente nodos blancos, nodos blancos a gris a medida que baja por el DFS, coloque los nodos grises en negro cuando se desarrolle la recursión (se procesan todos los elementos secundarios). si no todos los niños aún procesados ​​y golpeas un nodo gris, eso es un ciclo. por ejemplo: todo blanco para comenzar en el gráfico directo de arriba. color A, B, D, F, G son de color blanco grisáceo. G es hoja, por lo que todos los niños procesados ​​lo colorean de gris a negro. la recursividad se desarrolla en F (todos los niños procesados) lo colorean en negro. ahora llegas a D, D tiene niños no procesados, por lo que el color E es gris, G ya es de color negro, así que no vayas más abajo. E también tiene borde a D, por lo tanto, mientras procesa D (D sigue siendo gris), encuentra un borde hacia atrás a D (un nodo gris), se detecta un ciclo.