From e5176f49c3e7ca952a18a70b84bea418e3dccda2 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 22:01:54 +0200 Subject: Improving Euler path code. --- graph/euler.cpp | 22 ++++++++++------------ 1 file changed, 10 insertions(+), 12 deletions(-) (limited to 'graph/euler.cpp') diff --git a/graph/euler.cpp b/graph/euler.cpp index 6551ac3..a35ce13 100644 --- a/graph/euler.cpp +++ b/graph/euler.cpp @@ -1,21 +1,19 @@ // Laufzeit: O(|V|+|E|) -vector< vector > adjlist; -vector< vector > otherIdx; -vector cycle; -vector validIdx; +vector< vector > adjlist, otherIdx; +vector cycle, validIdx; -void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n. - int neighA = adjlist[n][a]; - int neighB = adjlist[n][b]; - int idxNeighA = otherIdx[n][a]; - int idxNeighB = otherIdx[n][b]; +// Vertauscht Kanten mit Indizes a und b von Knoten n. +void swapEdges(int n, int a, int b) { + int neighA = adjlist[n][a], neighB = adjlist[n][b]; + int idxNeighA = otherIdx[n][a], idxNeighB = otherIdx[n][b]; swap(adjlist[n][a], adjlist[n][b]); swap(otherIdx[n][a], otherIdx[n][b]); otherIdx[neighA][idxNeighA] = b; otherIdx[neighB][idxNeighB] = a; } -void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante). +// Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante). +void removeEdge(int n, int i) { int other = adjlist[n][i]; if (other == n) { //Schlingen. validIdx[n]++; @@ -30,7 +28,7 @@ void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugeh } // Findet Eulerzyklus an Knoten n startend. -// Teste vorher, dass Graph zusammenhängend ist! Was ist mit isolierten Knoten? +// Teste vorher, dass Graph zusammenhängend ist! Isolierten Knoten? // Teste vorher, ob Eulerzyklus überhaupt existiert! void euler(int n) { while (validIdx[n] < (int)adjlist[n].size()) { @@ -38,5 +36,5 @@ void euler(int n) { removeEdge(n, validIdx[n]); euler(nn); } - cycle.push_back(n); // Zyklus am Ende in cycle (umgekehrte Reihenfolge). + cycle.push_back(n); // Zyklus in cycle in umgekehrter Reihenfolge. } -- cgit v1.2.3