我正在实现一个程序来解决匹配问题，方法是使用从匹配问题到最大流量问题的减少，我决心使用 Edmond-Karp 算法来解决这个问题。
我已经查看并从不同的伪代码中获取印象，这些伪代码告诉如何使用 Edmond-Karp 算法执行解决最大流量问题的过程，并通过混合这些印象，我生成了一个适用于许多小型基本图的实现. 但是由于某种原因，该实现对更大的图给出了错误的答案，例如具有 100 条边的 50 个节点，甚至比此类图更大。因此，给出一个输入输出场景示例对于突出整个问题并没有太大帮助（如果您坚持，我可以按照您的意愿发布这样的输入输出场景）。当我说“错误答案”时，实现实际上并没有给出最大匹配（或最大流量值）给定要解决的图形。
在下面，您可以拥有在我的实现中使用的所有相关类，即在 MaxFlowSolver 类中（方法 solveFlowProblem(...) 是使用整个 Edmond-Karp 算法的方法）：
MaxFlowSolver
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class MaxFlowSolver {
private Graph flowProblemSolution;
private int flowValue;
public MaxFlowSolver(Graph toBeSolved, int source, int sink) {
flowProblemSolution = solveFlowProblem(toBeSolved, source, sink);
}
private Graph solveFlowProblem(Graph toSolve, int source, int sink) {
Graph rGraph = toSolve;
Edge[] path;
while((path=BFS(rGraph, source, sink))!=null) {
int r = Integer.MAX_VALUE;
for(Edge e = path[sink]; e!=null; e = path[e.getStartVertex()])
r = Math.min(r, e.getCapacity()-e.getFlow());
for(Edge e = path[sink]; e!=null; e = path[e.getStartVertex()]) {
e.changeFlow(e.getFlow()+r);
Edge erev;
if((erev=getReversedEdge(e, rGraph))==null) {
erev = new Edge(e.getEndVertex(), e.getStartVertex(), 0);
rGraph.addEdge(erev);
}
erev.changeFlow(-e.getFlow());
e.changeResCap(e.getCapacity()-e.getFlow());
erev.changeResCap(erev.getCapacity()-erev.getFlow());
}
flowValue += r;
}
return rGraph;
}
private Edge getReversedEdge(Edge e, Graph graph) {
LinkedList<Edge> neighbours = graph.getEdges().get(e.getEndVertex());
if(neighbours==null)
return null;
for(Edge i : neighbours)
if(i.getEndVertex()==e.getStartVertex())
return i;
return null;
}
private Edge[] BFS(Graph resGraph, Integer source, Integer sink) {
Queue<Integer> q = new LinkedList<>();
q.add(source);
Edge[] pred = new Edge[resGraph.numVertices()+1];
while(!q.isEmpty()) {
Integer curr = q.poll();
LinkedList<Edge> neighbours1 = resGraph.getEdges().get(curr);
if(neighbours1!=null)
for(Edge someEdge : neighbours1) {
if(pred[someEdge.getEndVertex()]==null && someEdge.getEndVertex()!=source &&
someEdge.getCapacity()>someEdge.getFlow()) {
pred[someEdge.getEndVertex()] = someEdge;
q.add(someEdge.getEndVertex());
}
}
if(curr==sink) return pred;
}
return null;
}
public Graph getSolution() {
return flowProblemSolution;
}
public ArrayList<Edge> retrievePositiveEdges(Graph arg0, int source, int sink) {
ArrayList<Edge> res = new ArrayList<>();
Set<Integer> goThroughInts = flowProblemSolution.getEdges().keySet();
for(Integer i : goThroughInts)
for(Edge j : flowProblemSolution.getEdges().get(i)) {
int start = j.getStartVertex();
int end = j.getEndVertex();
if(!res.contains(j) && j.getFlow()>0 &&
start!=source && start!=sink && end!=source && end!=sink &&
arg0.getEdges().get(i).contains(j))
res.add(j);
}
return res;
}
public int getFlowValue() {
return flowValue;
}
}
图形
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashMap;
public class Graph {
private HashMap<Integer, LinkedList<Edge>> edges;
private int firstVertices;
private int secondVertices;
private int size;
public Graph(int x, int y) {
firstVertices = x;
secondVertices = y;
edges = new HashMap<>();
size = 0;
}
public Graph(int size) {
firstVertices = size;
secondVertices = 0;
edges = new HashMap<>();
}
public boolean addEdge(int x, int y, boolean regularV) {
if(!(0<=x && x<=firstVertices && firstVertices<y && y<=firstVertices+secondVertices) && regularV) {
System.err.println("The graph is no longer bipartite. The execution is aborted.");
System.exit(1);
}
if(!edges.containsKey(x))
edges.put(Integer.valueOf(x), new LinkedList<Edge>());
Edge temp = new Edge(x,y);
if(!edges.get(x).add(temp))
return false;
size++;
return true;
}
public boolean addEdge(Edge newEdge) {
if(!edges.containsKey(newEdge.getStartVertex()))
edges.put(Integer.valueOf(newEdge.getStartVertex()), new LinkedList<Edge>());
if(!edges.get(newEdge.getStartVertex()).add(newEdge))
return false;
size++;
return true;
}
public void changeNumOfXs(int newVal) {
firstVertices = newVal;
}
public void changeNumOfYs(int newVal) {
secondVertices = newVal;
}
public int getNumOfXs() {
return firstVertices;
}
public int getNumOfYs() {
return secondVertices;
}
public int numOfEdges() {
return size;
}
public HashMap<Integer, LinkedList<Edge>> getEdges() {
return edges;
}
public void printGraph(Kattio io) {
printGraph(io, size-1, size);
}
public void printGraph(Kattio io, int source, int sink) {
io.println(firstVertices+secondVertices);
io.println(source + " " + sink);
io.println(size);
ArrayList<Edge> printed = new ArrayList<>();
for(LinkedList<Edge> i : edges.values())
for(Edge j : i)
if(!printed.contains(j)) {
printed.add(j);
io.println(j.getStartVertex() + " " + j.getEndVertex() + " " + j.getCapacity());
}
io.flush();
}
public int numVertices() {
return firstVertices+secondVertices;
}
public int numEdges() {
return size;
}
}
边缘
public class Edge {
private final int startVertex;
private final int endVertex;
private int flow;
private int rCapacity;
private final int capacity;
public Edge(int start, int end) {
startVertex = start;
endVertex = end;
flow = 0;
rCapacity = 1;
capacity = 1;
}
public Edge(int start, int end, int cap) {
startVertex = start;
endVertex = end;
flow = 0;
rCapacity = cap;
capacity = cap;
}
public void changeFlow(int newFlowVal) {
flow = newFlowVal;
}
public void changeResCap(int newResCapVal) {
rCapacity = newResCapVal;
}
public int getStartVertex() {
return startVertex;
}
public int getEndVertex() {
return endVertex;
}
public int getFlow() {
return flow;
}
public int getCapacity() {
return capacity;
}
public int getResCapacity() {
return rCapacity;
}
}
我主要遵循维基百科对使用邻接节点的 Edmond-Karp 算法的描述，但也有一些来自其他来源，但没有那么多。维基百科上的算法链接如下：
https://en.wikipedia.org/wiki/Edmonds –Karp_algorithm#Pseudocode
在我的实现中是否有某个地方我错误地解释了维基百科上的伪代码，或者它是否更具体地与我的 Java 代码有关？我几乎整天都在使用这个程序，但没有弄清楚是什么导致了某些图形的程序没有输出某些图形的最大匹配（或最大流量）的问题。
我能从你那里得到的所有帮助将不胜感激。
谢谢大家！