Zusammenhangskomponenten < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:52 Sa 04.12.2004 | | Autor: | Skully |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.java-forum.org/de/viewtopic.php?t=11346
Hi!
Hab da nen Problem mit einem Graph-Algorithmus.
Es geht um Starke Zusammenhangskomponenten (ZHK).
Für die, die nicht wissen worums geht hier ein Beispiel.
Ein Graph besteht aus Knoten und Kanten.
Also seien folgende Knoten und Kanten gegeben.
Knoten (Vertices):
v1, v2, v3, v4, v5
Kanten (Edges):
Format: Name Startknoten Endknoten
e1 v1 v2
e2 v2 v1
e3 v2 v3
e4 v3 v2
e4 v3 v4
e5 v4 v5
e6 v5 v3
e7 v1 v3
Also die starken ZHK wären:
1. v1 v2
2. v2 v3
3. v1, v2, v3
4. v3, v4, v5
Auf deutsch, gibt es einen Weg v1 zu v2 und einen weg von v2 zu v1, dann ist dies eine ZHK.
Also mein Alg. ist ein modifizierter DFS-Algo. Er findet leider nur 3 der 4 ZHKS.
Also finden tut er 1,2 und 4.
Hier mal Pseudocode vom Alg:
| 1: |
| | 2: | v1 = Startknoten
| | 3: | pushe v1 auf Stack
| | 4: | v1 = besucht
| | 5: | solange bis Stack leer ist{
| | 6: | v1 = kopf vom Stack
| | 7: | v2 = unbesuchter Nachfolger von v1
| | 8: | wenn v2 = null dann stack.pop()
| | 9: | sonst v2 = besucht und pushe v2 auf stack
| | 10: | nun for each vertex vom Stack{
| | 11: | e1 = Kante von v2 zu vertex
| | 12: | wenn e1 != null
| | 13: | erzeuge neuen graphen tg
| | 14: | adde v2 und vertex zu tg
| | 15: | clone den stack zu stacktemp
| | 16: | solange v3 = stacktemp.pop() != vertex{
| | 17: | adde v3 zu tg
| | 18: | }
| | 19: | füge tg zu grapharray hinzu
| | 20: | }
| | 21: | return grapharray
| | 22: | }
|
Wenn ich die Graphen nach Gewicht sortiere und der Graph v1 zu v2 ein höheres Gewicht als v1 zu v3, findet er die ZHK v1,v2,v3 aber dafür v1,v2 nicht.
Problem ist halt wenn Alg irgendwann zu v1 zurückkommt, gibt es keine unbesuchten Nachfolger mehr.
Jemand ne Idee?
Kann auch den Java-Code posten, aber da dort verschiedene Sachen genutzt werden, wird das wohl nicht so leicht verständlich sein.
|
|
| |
|
Hallo Skully,
ich weiß zwar nicht warum, aber es sieht so aus, als ob dein Algorithmus die beiden ZHK v1-v2 und v2-v3 nicht zu v1-v2-v3 zusammenflicken kann. Wahrscheinlich hört er auf, sobald er eine möglichst kurze Strecke gefunden hat, die ZHK ist. Du müsstest ihm sagen, dass er weitersuchen soll, evtl. erst nach ZHK der Länge 1, dann ZHK der Länge 2 usw. bis es keinen Sinn mehr macht (die Länge der längsten ZHK kann ja nicht größer sein als die Anzahl der Kanten in deinem Graphen).
Hugo
|
|
|
|
