Ich hab eine Art Graphenwolke Die besteht größtenteils aus unidirektionalen und ganz wenigen bidirektionalen Kanten und ein paar Knoten nichts wildes so 100-300 Knoten/Kanten (relativ klein) nicht alle Knoten können über alle Kanten erreicht werden d.h. diese Kanten/Knoten bilden n gerichtete Graphen ohne Mehrfachkanten Was ich von der Graphenwolke wissen möchte: -welche Graphen (zusammenhängende Knoten über die uni und bi-directionalen Kanten gibt es) -gibt es Zyklen (über die uni und bi-directionalen Kanten) mein Algorithmus steht und funktioniert auch - bisschen Rekursion/Durchlaufene Knoten/Kanten merken usw. Vor ein paar Tagen bin ich jetzt auf Adjazenzmatrix gestossen https://en.wikipedia.org/wiki/Adjacency_matrix und wollte wissen ob ich damit die beiden oberen Anforderungen mit bekannteren Standard-Algorithmen lösen kann (um z.B. Boost Graph zu verwenden oder auch einfach weniger dokumentieren zu müssen, oder auch weniger Rekursionen zu haben) Könnt ihr mir Algorithmen nennen die für die obigen Anforderungen gut passen würden oder ist eine Adjazenzmatrix in meinem Fall nicht wirklich sinnvoll?
Bidirektional ist wohl doch nicht ganz richtig - es sind Kanten die gar keine Richtung haben (oder die Richtung einfach nicht relevant ist - nur der Bezug zwischen den Knoten) bei der Zyklus-Erkennung verhaltet sich diese neutral was den Richtungswechsel angeht
cppbert schrieb: > Bidirektional ist wohl doch nicht ganz richtig - es sind > Kanten die gar keine Richtung haben (oder die Richtung > einfach nicht relevant ist - nur der Bezug zwischen den > Knoten) Die heißen m.W. einfach "ungerichtete Kanten". > bei der Zyklus-Erkennung verhaltet sich diese neutral > was den Richtungswechsel angeht Ungerichtete Kanten lassen sich m.W. äquivalent durch "antiparallele" Paare von gerichteten Kanten ersetzen.
cppbert schrieb: > Könnt ihr mir Algorithmen nennen die für die obigen > Anforderungen gut passen würden oder ist eine > Adjazenzmatrix in meinem Fall nicht wirklich sinnvoll? Ich verstehe zu wenig von Graphentheorie, um Dir gezielt helfen zu können, aber: 1. Für die mathematischen Grundlagen ist sicher ein gutes Lehrbuch am hilfreichsten; die online verfügbaren Tutorien finde ich ziemlich lückenhaft und nicht unbedingt gut verständlich. Unter Umständen findest Du heraus, dass Dein Graph spezielle Eigenschaften hat, die sich vorteilhaft ausnutzen lassen -- dann ist weniger brutale Gewalt notwendig. 2. Da man die Knoten nummerieren und i.d.R. auch sortieren kann, lassen sich für manche Zwecke n*log(n)-Algorithmen konstruieren. Für Deine relativ kleinen Graphen genügt das unter Umständen schon. 3. Wenn im Mittel jeder Knoten deutlich weniger Kanten hat, als Dein Graph insgesamt Knoten besitzt (-- anders gesagt: wenn Dein Graph "sehr weit" vom vollständigen Graphen "entfernt" ist), dann wird die Adjazenzmatrix schwach besetzt und damit wenig nützlich sein (vermute ich).
Die Antwort auf beide Fragen lautet: Tiefensuche und Färbung
color = 1
foreach node:
if node is uncolored:
depth-first-search(node, color) //recursively traverses graph,
colors nodes and detect cycles
color++
Softwareentwickler schrieb: > Die Antwort auf beide Fragen lautet: Tiefensuche und Färbung > > color = 1 > foreach node: > if node is uncolored: > depth-first-search(node, color) //recursively traverses graph, > colors nodes and detect cycles > color++ Zur Erklärung, du startest von einem Knoten aus eine Tiefensuche und markierst alle Knoten mit derselben Farbe die du währenddessen besuchst (triffst du auf einen schon gefärbten knoten mit derselben farbe, hast du einen Zyklus entdeckt), triffst du auf einen schon anders gefärbten Knoten überschreibst du die Farbe einfach. Am Ende schaust du wie viele verschiedene Farben in deinem Graphen vorherrschen. Das würde bei folgendem Graphen 2 ergeben: O->O<-O Wenn das Ergebnis 1 lauten soll, musst du jede Kante als ungerichtet betrachten bei der Färbung und nur für die Zyklendetektierung gerichtete Kanten berücksichtigen.
Danke für die Tips, ich hab jetzt meinen Graphen von meinen Objekten total entkoppelt und mit dem einfärben gearbeitet - viel kleiner und übersichtlicher
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.