summaryrefslogtreecommitdiff
path: root/graph/euler.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'graph/euler.cpp')
-rw-r--r--graph/euler.cpp22
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.
}