¿Cómo transformo un gráfico no dirigido y muy cíclico en un gráfico acíclico dirigido?

Question

Estoy trabajando en un algoritmo TopSort modificado y estoy teniendo problemas para encontrar/crear gráficos acíclicos dirigidos grandes (más de 1000 nodos) para usarlos en las pruebas. Tengo un gráfico de muestra no dirigido de otro proyecto que es de buen tamaño, pero tiene muchos ciclos. ¿Hay algún algoritmo que pueda usar para dirigir los bordes para que no haya ciclos?

Answer 1

Está buscando convertir el gráfico en un bosque de árboles enraizados. hacer un cruce de gráfico primero o primero de profundidad de cada componente del gráfico. Durante el recorrido, crea un borde dirigido entre los vértices padre-hijo.

ver http://en.wikipedia.org/wiki/Graph_traversal

Answer 2

this proporciona una forma de obtener gráficos acíclicos. Básicamente, un cruce de gráfico produce un árbol, que define un orden parcial en los nodos originales. Luego, simplemente dirija todos los bordes para que apunten en una dirección consistente de acuerdo con el orden parcial, o estén entre 2 elementos que no están ordenados (estos pueden apuntar en cualquier dirección).

Answer 3

Para garantizar que el nuevo grafo dirigido esté conectado, ¿podría utilizar la búsqueda de primer orden de la siguiente manera?

old_undirected graph G 
new_directed graph D 
dequeue Q 
v is any node in G 
add v to D 
Q.push_back(v) 
while(Q is not empty): 
    v = Q.pop_front() 
    for all neighbors u to v: 
     if u in D 
       add edge u->v to D 
     else 
       add u to D and add edge v->u to D 
       Q.push_back(u) 

return D 

este gráfico debe contener todos los bordes de la gráfica original, pero el debe ser tan dirigido que no habrá ningún círculos.