埃德蒙兹-卡普算法

计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为 � ( � � 2 ) {\displaystyle O(VE^{2})}。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和理查德·卡普在1972年独立发表。[1]

C++实现 以下是关于埃德蒙兹-卡普算法的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) {}

};

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: