网络最大流问题的算法设计和实现

package chap26.fordfulkerson; import java.util.LinkedList; import java.util.Vector; import chap26.fordfulkerson.FordFulkersonApp.MyCanvas; public class Graph { Vertex[] vertexList; int max = 20; int nVert; int adjMat[][]; // 对应于书上的c(u,v) LinkedList list = new LinkedList(); MyCanvas canvas; // 残留网络的流矩阵,这两个矩阵的值是经常变化的 int f[][]; // 对应于书上的f(u,v) int cf[][]; // 对应于书上的cf(u,v) public Graph() { vertexList = new Vertex[max]; nVert = 0; adjMat = new int[max][max]; f = new int[max][max]; cf = new int[max][max]; for (int i = 0; i < max; i++) { for (int j = 0; j < max; j++) { adjMat[i][j] = 0; f[i][j] = 0; } } } public void setCanvas(MyCanvas canvas) { this.canvas = canvas; } public void addVertex(char l) { Vertex v = new Vertex(l); vertexList[nVert] = v; v.sequenceNum = nVert; nVert++; } // 最大流是有向边 public void addEdge(int i, int j, int w) { adjMat[i][j] = w; } // bfs遍历,注意是在残留网中，返回s到t的距离 public int bfs(int s, int t) { // 初始化 for (int u = 0; u < nVert; u++) { if (u != vertexList[s].sequenceNum) { vertexList[u].d = Integer.MAX_VALUE; vertexList[u].p = -1; vertexList[u].color = 0; } } vertexList[s].d = 0; vertexList[s].p = -1; vertexList[s].color = 1; list.add(vertexList[s]); while (list.size() > 0) { Vertex u = (Vertex) list.remove(); for (int v = 0; v < nVert; v++) { if (vertexList[v].color == 0 && cf[u.sequenceNum][v] != 0) { vertexList[v].color = 1; vertexList[v].p = u.sequenceNum; vertexList[v].d = u.d + 1; list.add(vertexList[v]); } } vertexList[u.sequenceNum].color = 2; } return vertexList[t].d; } /** * 广度遍历得到了残留图中源点s到汇点t的一条路径，如果这条路径不存在则 * 返回Integer.Maxvalue否则返回路径上Cf的值，如果s到t的路径长度为仍然为无穷大 * 说明s到t不存在路径,这里不仅得到了cf的值，而且还调整了残留网络 * * @param s * @param t * @return */ public int getCf(int s, int t) { // 获取s到t路径上，关键边的权值,用一个向量存储s到t的顶点 Vector vector = new Vector(); vector.add(t); int temp = vertexList[t].p; while (temp != -1) { vector.add(0, temp); temp = vertexList[temp].p; } canvas.setVector(vector); int cfmin = Integer.MAX_VALUE; for (int i = 0; i < vector.size() - 1; i++) { int u = (Integer) vector.get(i); int v = (Integer) vector.get(i + 1); if (cf[u][v] < cfmin) { cfmin = cf[u][v]; } } for (int i = 0; i < vector.size() - 1; i++) { int u = (Integer) vector.get(i); int v = (Integer) vector.get(i + 1); f[u][v] += cfmin; f[v][u] = -f[u][v]; } // 输出路径上的点 for (int i = 0; i < vector.size(); i++) { int index = (Integer) vector.get(i); System.out.print(vertexList[index].label + " "); } System.out.println(); return cfmin; } // ford_fulkerson求s到t的最大流 public void ford_fulkerson(int s, int t) { // 表示最大流的值 int maxf = 0; // 初始化 for (int i = 0; i < nVert; i++) { for (int j = 0; j < nVert; j++) { f[i][j] = 0; f[j][i] = 0; } } int distance = 0; // 第一次执行ford_fulkerson算法时，残留图就是原来的图，之后的执行过程中 // 残留网络将不断的发生变化 initialize(); canvas.repaint(); distance = bfs(s, t); // System.out.println("s到t的距离："+distance); // 这里出现了死循环 while (distance != Integer.MAX_VALUE) { int cfmin = getCf(s, t); maxf += cfmin; translate(); try { Thread.sleep(4000); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } canvas.repaint(); distance = bfs(s, t); // System.out.println("s到t的距离："+distance); } System.out.println("图G的最大流的值为："); System.out.print(maxf); } public void initialize() { for (int i = 0; i < nVert; i++) { for (int j = 0; j < nVert; j++) { cf[i][j] = adjMat[i][j]; } } } // 计算残留图 public void translate() { for (int i = 0; i < nVert; i++) { for (int j = 0; j < nVert; j++) { cf[i][j] = adjMat[i][j] - f[i][j]; if (cf[i][j] < 0) { cf[i][j] = 0; } } } } public Vertex[] getVertexList() { return vertexList; } public int getNVert() { return nVert; } public int[][] getAdjMat() { return adjMat; } public int[][] getF() { return f; } public int[][] getCf() { return cf; } public void setPosition() { vertexList[0].setPosition(50, 200); vertexList[1].setPosition(100, 100); vertexList[2].setPosition(100, 300); vertexList[3].setPosition(200, 100); vertexList[4].setPosition(200, 300); vertexList[5].setPosition(350, 200); } }