查看“︁埃德蒙兹-卡普算法”︁的源代码

{{expand|time=2015-11-12T10:47:30+00:00}}
{{NoteTA
|G1=IT
}}
[[计算机科学]]中，'''埃德蒙兹-卡普算法'''（{{lang-en|Edmonds–Karp algorithm}}）通过实现[[福特-富尔克森算法]]来计算网络中的最大流，其时间复杂度为<math>O(VE^2)</math>。该算法由{{le|叶菲姆·迪尼茨|Yefim Dinitz}}在1970年最先提出，并由{{le|杰克·埃德蒙兹|Jack Edmonds}}和[[理查德·卡普]]在1972年独立发表。<ref>{{cite journal |last1=Edmonds |first1=Jack |author1-link=Jack Edmonds |last2=Karp |first2=Richard M. |author2-link=Richard Karp |title=Theoretical improvements in algorithmic efficiency for network flow problems |journal=Journal of the ACM |volume=19 |issue=2 |pages=248–264  |publisher=[[Association for Computing Machinery]] |year=1972 |url= |doi=10.1145/321694.321699 |id= |accessdate= |language=en}}</ref>

== C++實作 ==
以下是关于埃德蒙兹-卡普算法的C++语言描述：<syntaxhighlight lang="c++">
struct Main {
	struct Edge {
		int u, v, Capacity, Flow;

		Edge (int u, int v, int Capacity, int Flow) :
			u(u), v(v), Capacity(Capacity), Flow(Flow) {}
	};

	struct Edmonds_Karp {
		vector<Edge> Edges;
		vector<int> Graph[MAXN]; // 保存下标
		int n, Augment[MAXN], Previous[MAXN];
			// 当起点到 Augment[i] 的可改进量；

		void Initialise(int n)
		{
			for (int i = 0; i < n; ++i)
				G[i].clear();

			Edges.clear();
		}

		void Add(int u, int v, int Capacity)
		{
			Edges.push_back(Edge(u, v, Capacity, 0));
			Edges.push_back(Edge(v, u, 0, 0));

			int m = Edges.size() - 1;

			Graph[u].push_back(m - 1);
			Graph[v].push_back(m);
		}
	};

	int MaxFlow(int s, int t)
	{
		int FlowSum = 0;
		while (1) {
			memset(Augment, 0, sizeof Augment);

			queue<int> Travel;
			Travel.push(s);
			Augment[s] = INT_MAX;

			while (!Travel.empty()) {
				int From = Travel.front();
				Travel.pop();

				for (int i = 0; i < Graph[From].size(); ++i) {
					Edge &Temp = Edges[Graph[From][i]];

					if (!Augment[Temp.v] && Temp.Capacity > Temp.Flow) {
						Previous[Temp.v] = Graph[From][i];
						Augment[Temp.v] = min(Augment[From], Temp.Capacity - Temp.Flow);

						Travel.push(Temp.v);
					}
				}

				if (Augment[t]) break;
			}

			if (!Augment[t]) break;

			for (int i = t; i != s; i = Edges[Previous[i]].From) {
				Edges[Previous[i]].Flow += Augment[t];
				Edges[Previous[i] ^ 1].Flow -= Augment[t];
			}

			FlowSum += Augment[t];
		}

		return flow;
	}


	Main(void) {}
};
</syntaxhighlight>

== 参考资料 ==
{{reflist}}

== 参见 ==
*[[福特-富尔克森算法]]
*[[迪尼茨算法]]
*[[网络流]]
{{算法}}

[[Category:网络流]]
[[Category:图算法]]