我现在正在处理一项任务，因为我们正在进入我们的图论单元，它是福特 Fulkerson 算法的实现。这个想法是我们有一个带有一定数量节点的加权有向图。我们还提供了图本身，它是有向边和节点的集合，但是，鉴于节点和边的构造，我们必须使用边作为我们的遍历方法（它们是由起始节点、权重组成的对象，和结束节点）。
我已经降低了 DFS，但在实际生成最终加权图时遇到了困难。就目前而言，我能够获得正确的最大流量，但是我的边缘附加了错误的权重，目前甚至没有加起来到最大流量。我怀疑错误来自我如何计算残差图边缘的流量，因为它目前只是从当前权重值中减去流量。我知道在普通的福特 Fulkerson 中，每条边的残差都有两个方向，但在我实现它的方式中，我只有一个，因为 Graphs 的构造函数没有这样做。我还需要在最后返回我的残差以查看所有顶点的值及其权重，
福特富尔克森级
import java.lang.reflect.Array;
import java.util.*;
import java.io.File;
public class FordFulkerson {
public static ArrayList<Integer> pathDFS(Integer source, Integer destination, WGraph graph) {
Stack<Integer> toVisit = new Stack<>();
ArrayList<Integer> visited = new ArrayList<>();
HashMap<Integer, Integer> parents = new HashMap<>();
toVisit.push(0);
boolean flag = false;
while (!toVisit.isEmpty()) {
int node = toVisit.pop();
visited.add(node);
if (node == destination) {
flag = true;
break;
}
for (Edge curEdge : graph.getEdges()) {
if ((curEdge.nodes[0] == node) &&(curEdge.weight>0)&&(!visited.contains(curEdge.nodes[1]))) {
toVisit.push(curEdge.nodes[1]);
parents.put(curEdge.nodes[1], curEdge.nodes[0]);
}
}
}
if (flag) {
ArrayList<Integer> path = new ArrayList<>();
int current = destination;
while (current != source) {
path.add(0, current);
current = parents.get(current);
}
path.add(0, source);
return path;
}
return new ArrayList<>();
}
public static String fordfulkerson(WGraph graph) {
ArrayList<Integer> result = pathDFS(graph.getSource(), graph.getDestination(), graph);
WGraph residual = new WGraph(graph);
String answer = "";
int maxFlow = 0;
while (!result.isEmpty()) {
int flow = Integer.MAX_VALUE;
int parentNode;
int childNode;
for (int i=result.size()-1; 0 < i; i--) {
parentNode = result.get(i-1);
childNode = result.get(i);
flow = Math.min(flow,residual.getEdge(parentNode,childNode).weight);
}
for (int i=0; i < result.size()-1; i++) {
parentNode = result.get(i);
childNode = result.get(i+1);
residual.getEdge(parentNode,childNode).weight -= flow;
// residual.getEdge(parentNode,childNode).weight -= flow;
}
maxFlow += flow;
result = pathDFS(graph.getSource(),graph.getDestination(),residual);
}
answer += maxFlow + "\n" + residual.toString();
return answer;
}
public static void main(String[] args){
String file = args[0];
File f = new File(file);
WGraph g = new WGraph(file);
System.out.println(fordfulkerson(g));
}
}
图形和边缘类
import java.io.*;
import java.util.*;
class Edge{
public int[] nodes = new int[2]; /*The nodes connected by the edge*/
public Integer weight; /*Integer so we can use Comparator*/
Edge(int i, int j, int w){
this.nodes[0] = i;
this.nodes[1] = j;
this.weight = w;
}
@Override
public String toString() {
return String.format("Edge(%s,%s,%s)",this.nodes[0],this.nodes[1],this.weight);
}
}
public class WGraph{
private ArrayList<Edge> edges = new ArrayList<Edge>();
private ArrayList<Integer> nodes = new ArrayList<Integer>();
private int nb_nodes = 0;
private Integer source = 0;
private Integer destination =0;
WGraph() {
}
WGraph(WGraph graph) {
for(Edge e:graph.edges){
this.addEdge(new Edge(e.nodes[0],e.nodes[1],e.weight));
}
this.source = graph.source;
this.destination = graph.destination;
}
WGraph(String file) throws RuntimeException {
try {
Scanner f = new Scanner(new File(file));
String[] ln = f.nextLine().split("\\s+"); /*first line is the source and destination*/
this.source = Integer.parseInt(ln[0]);
this.destination = Integer.parseInt(ln[1]);
int number_nodes = Integer.parseInt(f.nextLine()); /*second line is the number of nodes*/
while (f.hasNext()){
String[] line = f.nextLine().split("\\s+");
/*Make sure there is 3 elements on the line*/
if (line.length != 3){
continue;
}
int i = Integer.parseInt(line[0]);
int j = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
Edge e = new Edge(i, j, w);
this.addEdge(e);
}
f.close();
/*Sanity checks*/
if (number_nodes != this.nb_nodes){
throw new RuntimeException("There are " + this.nb_nodes + " nodes while the file specifies " + number_nodes);
}
for (int i = 0; i < this.nodes.size(); i++){
if ((this.nodes.get(i) >= this.nb_nodes) || (this.nodes.get(i) < 0)){
throw new RuntimeException("The node " + this.nodes.get(i) + " is outside the range of admissible values, between 0 and " + this.nb_nodes + "-1");
}
}
if(!this.nodes.contains(source)){
throw new RuntimeException("The source must be one of the nodes");
}
if(!this.nodes.contains(destination)){
throw new RuntimeException("The destination must be one of the nodes");
}
}
catch (FileNotFoundException e){
System.out.println("File not found!");
System.exit(1);
}
}
public void addEdge(Edge e) throws RuntimeException{
/*Ensures that it is a new edge if both nodes already in the graph*/
int n1 = e.nodes[0];
int n2 = e.nodes[1];
if (this.nodes.indexOf(n1) >= 0 && this.nodes.indexOf(n2) >= 0){
for (int z = 0; z < this.edges.size(); z++){
int[] n = this.edges.get(z).nodes;
if ((n1 == n[0] && n2 == n[1])){
throw new RuntimeException("The edge (" + n1 + ", " + n2 + ") already exists");
}
}
}
/*Update nb_nodes if necessary*/
if (this.nodes.indexOf(n1) == -1){
this.nodes.add(n1);
this.nb_nodes += 1;
}
if (this.nodes.indexOf(n2) == -1){
this.nodes.add(n2);
this.nb_nodes += 1;
}
this.edges.add(e);
}
public Edge getEdge(Integer node1, Integer node2){
for(Edge e:edges){
if(e.nodes[0]==node1 && e.nodes[1]==node2){
return e;
}
}
return null;
}
public void setSource(int source){
this.source = source;
}
public void setDestination(int destination){
this.destination = destination;
}
public int getSource(){
return this.source;
}
public int getDestination(){
return this.destination;
}
public void setEdge(Integer node1, Integer node2, int weight){
for(Edge e:edges){
if(e.nodes[0]==node1 && e.nodes[1]==node2){
e.weight=weight;
}
}
}
public ArrayList<Edge> listOfEdgesSorted(){
ArrayList<Edge> edges = new ArrayList<Edge>(this.edges);
Collections.sort(edges, new Comparator<Edge>() {
public int compare(Edge e1, Edge e2)
{
return e2.weight.compareTo(e1.weight);
}
});
return edges;
}
public ArrayList<Edge> getEdges(){
return this.edges;
}
public int getNbNodes(){
return this.nb_nodes;
}
public String toString(){
String out = Integer.toString(this.source)+ " " + Integer.toString(this.destination)+"\n";
out += Integer.toString(this.nb_nodes);
for (int i = 0; i < this.edges.size(); i++){
Edge e = edges.get(i);
out += "\n" + e.nodes[0] + " " + e.nodes[1] + " " + e.weight;
}
return out;
}
}
作为参考，我有输入
0 5
6
0 1 16
0 2 13
1 3 12
2 1 4
2 4 14
3 2 9
3 5 20
4 3 7
4 5 4
它定义了一个具有 5 个节点和 9 个边的起始图，它们的权重偏向一边。正确的输出是：
23
0 5
6
0 1 12
0 2 11
1 3 12
2 1 0
2 4 11
3 2 0
3 5 19
4 3 7
4 5 4
但是，在运行我的 Ford Fulkerson 时，我得到以下输出：
23
0 5
6
0 1 6
0 2 0
1 3 0
2 1 2
2 4 3
3 2 9
3 5 1
4 3 0
4 5 0
我一直在看下面的GeeksforGeeks 文章，其中他们从有向图开始，但后来不知何故能够以相反的方向访问顶点：
// update residual capacities of the edges and
// reverse edges along the path
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
关于从哪里开始寻找或我做错了什么的任何指示或提示都会很棒。