Entfernen Zyklus Abhängigkeiten auf einem gerichteten Graphen mit festen Rändern

Question

Ich habe ein gerichtetes zyklisches Graphen. Einige Ränder sind fest und können nicht entfernt werden. Die anderen Kanten entfernt werden, um einen Zyklus zu brechen.

Was ist der beste Weg, um die Zyklen in diesem Diagramm entferne? Die Traversal sollte so viel wie ein DFS wie möglich sein und an einem gegebenen Knoten starten.

Answer 1

Ich habe den folgenden Algorithmus mein Problem zu lösen:

Starten Sie mit einem Diagramm aller festen Kanten markiert als bestätigt

Von einem Startknoten, recurse durch alle bestätigten Kanten sowie die noch nicht bestätigt diejenigen. Aber wenn Sie sind dabei bis auf Rekursion eine noch nicht bestätigt Kante zuerst prüfen, ob der Knoten, der die Kante geht auf einen Pfad hat, durch bestätigte Kanten folgenden, zu einem Knoten in dem aktuellen Suchbaum (dh einen Knoten mit einem < em> besuchen Flag gesetzt). Diese Prüfung muss rekursiv durchgeführt werden, indem alle bestätigten Kanten folgende, aber das ist zu langsam für mich, damit ich hier siedeln nur zu prüfen, ob der Knoten besucht oder wenn eine der Knoten es zu Besuch sind verbunden bestätigt. Dies wird die meisten meiner Fälle abdecken, aber occationally verlassen Zyklen in der grafischen Darstellung.

Nach dem obigen Schritt I Tarjan-Algorithmus verwenden, um die stark verbundenen Komponenten links in der Grafik für die Suche nach (dies kann in O (V + E) Zeit erfolgen). Die Zahl der stark verbundenen Komponenten werden in meinen Fällen sehr klein sein, damit ich durch jede stark verbundenen Komponente gehen Sie einfach und jeder abnehmbaren Rand entfernen. Dann kann ich diesen Schritt wieder, bis keine weiteren Zyklen bleiben in der grafischen Darstellung.

Das funktioniert gut und schnell genug ist.

Answer 2

Was Sie tun können, ist Dijkstra-Algorithmus verwenden: mit einem Diagramm beginnen nur die FIXED Kanten enthält. Dann eine Anpassung des Algorithmus anwenden mit dem Graphen beginnen Sie bereits haben:

1. Starten Sie mit dem Startknoten, und alle in der Komponente des Ausgangsknoten FIXED Kanten. Angenommen, dies ist ein Baum.
2. Fügen Sie den Knoten am nächsten Baum.
3. Fügen Sie auch alle FIXED Kanten in der Komponente des Knotens Sie gerade hinzugefügt haben.
4. Wenn alle Knoten im Baum, Ende sind. Andernfalls gehen Sie zu Schritt 4.

Das ist natürlich, geht davon aus, dass der Graph nur die festen Kanten aus Zyklen nicht enthalten. Ist dies der Fall, gibt es keine Lösung (das heißt, ein Teilgraph ohne Kanten, aber mit allen FIXED Kanten).

Für gerichtete Graphen, dann ist es etwas komplizierter. In diesem Fall sollte jede Komponente des Graphen von FIXED Kanten ein Baum sein. In dem Dijkstra-Algorithmus wie nur Wurzeln dieser Knoten sollen die Kandidaten in den Baum eingefügt werden, sein.

Answer 3

das Problem unterschätzt wird, weil Sie nicht zum Beispiel festgelegt haben wenn der Graph muss angeschlossen bleiben, oder wenn Sie wollen eine „kleine“ Anzahl der nicht-FIXED Kanten zu entfernen, um alle Zyklen zu brechen, oder wenn Sie wirklich brauchen, die global minimale Anzahl von Nicht-FIXED Kanten entfernt werden.

Wenn das Diagramm muss nicht verbunden bleiben, durchqueren die Kanten alle und entfernen Sie alle nicht fixierten diejenigen. Das entfernt alle Zyklen, die Sie ohne Entfernen FIXED Kanten entfernen.

Wenn Sie ein einfacher Greedy-Algorithmus Kanten zu entfernen, die reine DFS ist, können Sie so etwas wie dies, wenn der Graph auch verbunden bleibt verwenden, wenn Sie einige der nicht fixierten Kanten entfernen:

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]