cycles in graph

Hi,

wie kann man pruefen ob ein directed und undirected graph einen cycle enthaelt?

LG

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

volkard

graphics schrieb:

wie kann man pruefen ob ein directed und undirected graph einen cycle enthaelt?

würde mal anfangen bei
http://en.wikipedia.org/wiki/Strongly_connected_component

Jester

Ungerichtet: testen ob es eine zusammenhangskomponente gibt, die mindestens so viele kanten wie Knoten enthält.

Gerichtet: iterativ Knoten weglöschen, die Eingangsgrad 0 bzw. Ausgangsgrad 0 haben. Lässt sich so alles löschen, dann gibt es keinen gerichteten Kreis, sonst schon.

Natürlicht geht das auch mit den allgemeineren Verfahren, die volkard verlinkt hat, aber die sind halt schon etwas komplexer.

Hi, lese gerade glfilgenden artikel:
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
http://www.geeksforgeeks.org/detect-cycle-undirected-graph/

Warum sind die algos fuer directed und undirected graphs unterschiedlich?

Im undirected fall verstehe ich foldendes nicht:

// If an adjacent is visited and not parent of current vertex,
        // then there is a cycle.
        else if (*i != parent)
           return true;

otze

wenn man von einem nachbarknoten weitergeht, dann hat man in einem ungerichteten graphen immer eine kante zurück. diese ignoriert man.

kann man das irgendwie grafisch darstellen was du meinst?

otze

zeichne einen ungerichteten graphen mit 2 Knoten und schau nach, ob du ohne die bedingung einen kreis hättest.

volkard

graphics schrieb:

kann man das irgendwie grafisch darstellen was du meinst?

http://programmingwiki.de/images/thumb/1/1b/GerichteterGraph.png/250px-GerichteterGraph.png
das war eigentlich ein ungerichteter Graph. Wenn wir ihn als grichteten Grapen darstellen, dann ist halt jede Kante eine doppelte Kante mit Hin- und Rückpfeil.

Sodele, dieses Hin-Rück ist aber jeweisl ein Kreis! Aber wenn wir von ungerichteten Graphen reden, meinen wie diese Sorte von Mini-Kreisen nicht. Deswegen war auch Jesters Code für den gerichteten so einfach und der für den ungerichteten so schwer.

nehmen wir mal folgenden graphen:
http://www.geeksforgeeks.org/wp-content/uploads/cycleGraph.png

so ich starte bei knoten 0. mach eine dfs:

recursiver aufruf: isCyclicUtil(v=0, parent=-1) neighbors: 1, 2
recursiver aufruf: isCyclicUtil(v=1, parent=0) neighbors: 0, 2
0 ist bereits besucht...so machen wir ein return zurueck zum vorherigen knoten und sehen das 2 noch nicht besucht wurde...
recursiver aufruf: isCyclicUtil(v=2, parent=0) neighbors: 0, 1
0, 1 sind bereits besucht...so machen wir ein return zurueck zum vorherigen knoten(0) ... und nehmen 2... und sehen folgendes:
i (2) != parent (-1) --> cycle

macht das sinn?