| Die letzten 10 Beiträge |
| Shizmo |
Ich glaub es hat grade klick gemacht.
| Zitat: |
Original von eulerscheZahl
Grundüberlegung:
Bei der Tiefensuche entsteht ein Baum.
[...] |
Bin grad nochmal alles durchgegangen und habe mir Tiefensuchbäume aufgezeichnet und somit ist alles viel klarer geworden.
Vielen Dank für deine Hilfe!!!! |
| eulerscheZahl |
Grundüberlegung:
Bei der Tiefensuche entsteht ein Baum. Es kann auch keine Querverbindung zwischen den Ästen mit gleicher Wurzel geben.
Betrachten wir zwei Knoten u und v:
es gibt einen Weg von u nach v, der durch die Tiefensuche gefunden wurde. Wenn es aber keinen anderen Weg gibt, um von v aus wieder über u zu kommen, ist u ein Artikulationspunkt (der einzige Weg von Knoten oberhalb von u nach v führt eben über u).
lowlink gibt an, wie weit man maximal zurück nach oben kommt. Kommt man nicht höher als bis u, ist u ein Artikulationspunkt.
Sag Bescheid, wenn du meine Vorlesungsmitschrift willst. Da ist der Beweis ausführlicher. |
| Shizmo |
Okay, aber warum macht man das? Generell, was ist dieses lowlink? |
| eulerscheZahl |
| Zitat: |
| Ich hab grad gemerkt, dass mir dieser Minimum-Vergleich fehlt, vermutlich klappt es deswegen nicht. Versteh aber auch nicht ganz für was der ist. |
Es kann sein, dass ein Knoten mehrere Rückkanten hat. Dann sprichst du immer so weit zurück nach oben wie möglich. |
| Shizmo |
Wird keiner gefunden gibt er aber auch ein false zurück und start.outDegree ist immer 1.
Ich hab grad gemerkt, dass mir dieser Minimum-Vergleich fehlt, vermutlich klappt es deswegen nicht. Versteh aber auch nicht ganz für was der ist.
Hab mal eine andere Version, die funktioniert soweit, allerdings nicht für einen trivialen Graph (also mit nur zwei Knoten).
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
|
time = 0
isBiconnected = true
for each v in V
v.color = weiß
v.PI = NIL
BICONNECTED(startNode)
return isBiconnected
--------------------------
BICONNECTED(u)
u.color = gray
u.d = time
u.l = u.d
time++
for each v in Adj[u]
if v.color == white
v.PI = u
MDFS-visit(v)
/* Kleineren Low-Wert des Kindes uebernehmen. */
u.l = min{u.l, v.l}
/* u ist Artikulationspunkt */
if v.l > u.d
isBiconnected = false
return
/* Rueckwaertskante */
if v.color == gray and u.PI != v
/* Merken, welche am weitesten zurueck reicht. */
u.l = min{u.l, v.d}
u.color = black |
|
|
| eulerscheZahl |
Kann es sein, dass ich einfach die Negation falsch gesetzt habe?
Mein Gedanke war: wenn findArtPoint true zurückgibt, hat der Graph einen Artikulationspunkt.
Jetzt gibt der Algorithmus aber false zurück, wenn ein Artikulationspunkt gefunden wird. |
| Shizmo |
Hja, das glaub ich dir 
Linker Knoten = A, mittlerer B und rechter Knoten = C.
A.visited = true
A.dfs = 1
A.lowlink = 1
B.Pi = A
A.outDegree = 1
B.visited = true
B.dfs = 2
B.lowlink = 2
C.Pi = B
B.outDegree = 1
C.visited = true
C.dfs = 3
C.lowlink = 3
if (C.lowlink >= B.dfs) (3>2) => return false
=> bool biconnected = true && start.outDegree == 1
Also true.
Aber der Graph ist nicht biconnected. |
| eulerscheZahl |
Ja, das hätte ein v werden sollen.
Wo ist denn das Problem bei deinem Graphen (tut mir leid, ich bin gerade denkfaul nach 2.5h Programmierwettbewerb). |
| Shizmo |
Hmm, also Zeile 24 soll v.outDegree++ heißen oder?
Wenn ich aber so einen Graph habe (Anhang) wird false returned und der StartKnoten hat zu dem Zeitpunkt auch den outDegree-Wert = 1, also true, was aber nicht stimmt. (Der linke Knoten ist der Startknoten)
Shizmo hat dieses Bild (verkleinerte Version) angehängt:
|
| eulerscheZahl |
So zum Beispiel
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
|
//Initialisieren
for each n in G
n.visited = false
n.dfs = NIL
n.lowlink = NIL
n.PI = NIL
n.outDegree = 0
counter = 0
bool biconnected = !findArtPoint(start) && start.outDegree == 1
//Eigentliches Programm
findArtPoint(Vertex v)
v.visited = true
v.dfs = counter++
v.lowlink = v.dfs
for each w in Adj[v]
if (! w.visited) {
w.PI = v
n.outDegree++
findArtPoint(w);
if (w.lowlink >= v.dfs)
return false
else if (v.PI != w)
v.lowlink = Minimum(v.lowlink, w.dfs) |
|
edit: du solltest vielleicht auch noch irgendwann true zurückgeben. |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
