diff options
Diffstat (limited to 'graph/euler.cpp')
| -rw-r--r-- | graph/euler.cpp | 22 |
1 files changed, 10 insertions, 12 deletions
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<int> > adjlist; -vector< vector<int> > otherIdx; -vector<int> cycle; -vector<int> validIdx; +vector< vector<int> > adjlist, otherIdx; +vector<int> 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. } |
