diff options
Diffstat (limited to 'graph/edmondsKarp.cpp')
| -rw-r--r-- | graph/edmondsKarp.cpp | 14 |
1 files changed, 8 insertions, 6 deletions
diff --git a/graph/edmondsKarp.cpp b/graph/edmondsKarp.cpp index 9181062..dcfd85b 100644 --- a/graph/edmondsKarp.cpp +++ b/graph/edmondsKarp.cpp @@ -1,7 +1,8 @@ -int s, t, f; //source, target, single flow -int res[MAX_V][MAX_V]; //adj-matrix +// Laufzeit: O(|V|*|E|^2) +int s, t, f; // Quelle, Senke, single flow +int res[MAX_V][MAX_V]; vector< vector<int> > adjlist; -int p[MAX_V]; //bfs spanning tree +int p[MAX_V]; void augment(int v, int minEdge) { if (v == s) { f = minEdge; return; } @@ -10,14 +11,15 @@ void augment(int v, int minEdge) { res[p[v]][v] -= f; res[v][p[v]] += f; }} -int maxFlow() { //first inititalize res, adjList, s and t +// Initialisiere res, adjList, s und t. +int maxFlow() { int mf = 0; while (true) { f = 0; bitset<MAX_V> vis; vis[s] = true; queue<int> q; q.push(s); memset(p, -1, sizeof(p)); - while (!q.empty()) { //BFS + while (!q.empty()) { // BFS int u = q.front(); q.pop(); if (u == t) break; for (int j = 0; j < (int)adjlist[u].size(); j++) { @@ -26,7 +28,7 @@ int maxFlow() { //first inititalize res, adjList, s and t vis[v] = true; q.push(v); p[v] = u; }}} - augment(t, INF); //add found path to max flow + augment(t, INF); // Pfad zu Fluss hinzufügen. if (f == 0) break; mf += f; } |