在具有大量节点和边缘的Java中，最大流算法太慢了

Question

我最近编写了一个Java应用程序，该程序使用最大的流量来执行图像分割。当节点数很少时，代码可以正常工作，但是当我使用大量节点时，代码将非常慢。是当节点和边缘的数量较大时，最大流量算法的速度变慢还是我的算法实现速度慢？以下是与最大流量的计算有关的相关代码。这个想法是要计算最大流量，并得到一个将源s与接收器t]分开的切口

// find path from nodeU to nodeV if one exists
public Map<Integer, Edge> BFS_(Integer nodeU, Integer nodeV)
{
    Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
    Map<Integer, Edge> path = new HashMap<Integer, Edge>();

    Queue<Integer> queue = new LinkedList<Integer>();

    queue.add(nodeU);
    visited.putIfAbsent(nodeU, true);
    path.putIfAbsent(nodeU, null);

    while( !queue.isEmpty() )
    {
        Integer cur = queue.poll();
        Set<Edge> neighbors = this.outgoing(cur);
        Iterator<Edge> iter = neighbors.iterator();

        while( iter.hasNext() )
        {
            Edge e = iter.next();
            // if not null
            if( visited.get(e.destination()) == null || visited.get(e.destination()) == false )
            {
                visited.putIfAbsent(e.destination(), true);
                path.putIfAbsent(e.destination(), e);
                queue.add(e.destination());
            }
        }
    }

    return path;
}

// find edges that link nodeU to nodeV and make a path
public Solution makePath(Map<Integer, Edge> in, Integer nodeU, Integer nodeV)
{
    Solution path = null;
    Integer parent = nodeV;

    path = new Solution();

    path.edges = new HashSet<Edge>();
    path.minflow = Integer.MAX_VALUE;

    Edge e = null;
    while( ( e = in.get(parent) ) != null )
    {
        if( e.flow() > 0 && e.flow() < path.minflow )
        {
            path.minflow = e.flow();
        }
        path.edges.add(e);
        parent = e.source();
    }

    if( path.edges.size() == 0 )
    {
        return null;
    }

    return path;
}

// make residual graph
 public Graph residualGraph()
 {
    Iterator<Edge> iter = this.edges.iterator();
    Set<Edge> back_edges = new HashSet<Edge>();
    Set<Edge> to_remove = new HashSet<Edge>();
    Integer forward_flow, backward_flow;

    while( iter.hasNext() )
    {
        Edge cur = iter.next();
        Edge backward_edge = new Edge(cur).reverse();
        // backward edge = f(e) > 0
        backward_flow = cur.flow();
        if( backward_flow > 0 )
        {
            // add forward and backward edges
            //this.addEdge(backward_edge);
            backward_edge.flow(backward_flow);
            back_edges.add(backward_edge);
        }
        // forward flow = c(e) - f(e) > 0
        forward_flow = cur.capacity() - cur.flow();
        // if forward flow is zero, remove edge
        if( forward_flow <= 0 )
        {
            //this.removeEdge(cur);
            to_remove.add(cur);
        }
        else
        {
            // modify forward edge in residual graph to contain flow it can send
            cur.flow(forward_flow);
        }
    }

    this.edges.removeAll(to_remove);
    this.edges.addAll(back_edges);

    return this;
}

// calculate max flow 
public Graph edmondsKarp(Integer nodeU, Integer nodeV)
{
    // create residual graph
    Graph h = new DirectedGraph(this);
    Graph r = new DirectedGraph(h);

    r.residualGraph();

    // run bfs on residual graph and while a path exists
    // keep augmenting the flow through the path
    Map<Integer, Edge> bfs = r.BFS_(nodeU, nodeV);

    Solution path = null;

    while( ( path = this.makePath(bfs, nodeU, nodeV) ) != null )
    {
        if( path.minflow > 0 )
        {
            h.updateNetwork(path.edges, path.minflow);
        }

        r = new DirectedGraph(h);
        r.residualGraph();
        bfs = r.BFS_(nodeU, nodeV);
    }

    // found max flow here
    // sum of outgoing flow from source = sum of incoming flow in sink
    Integer sumU = 0, sumV = 0;
    Iterator<Edge> s_edges = h.outgoing(nodeU).iterator();
    Iterator<Edge> t_edges = h.incoming(nodeV).iterator();

    while( s_edges.hasNext() )
    {
        Edge e = s_edges.next();

        sumU += e.flow();
    }

    while( t_edges.hasNext() )
    {
        Edge e = t_edges.next();

        sumV += e.flow();
    }

    System.out.println("t_edges: " + h.incoming(nodeV) + ", " + h.incoming(nodeV).size());

    if( !sumU.equals(sumV) )
    {
        Logger logger = Logger.getLogger(this.getClass().getName());

        logger.warning("flow in " + sumU + " not equal to flow out " + sumV);
    }

    h.maxflow = sumU;

    return h;
}

我最近编写了一个Java应用程序，该程序使用最大的流量来执行图像分割。当节点数较少时，代码可以正常工作，但是当我使用较大的节点时，代码却非常慢...

Answer 1

是当节点和边的数量较大时，最大流量算法较慢还是我的算法实现缓慢？