حل مساله بیشینه جریان — راهنمای جامع

برنامه نویسی, کامپیوتر, مهندسی

در این مطلب، روش حل مساله بیشینه جریان (Maximum Flow Problem) بیان و راهکار بیان شده برای آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) پیاده‌سازی شده است. یک گراف داده شده که نشانگر یک «شبکه جریان» (Flow Network) است و در آن، هر «یال» (Edge) دارای ظرفیت است. همچنین، دو راس s (مبدا | Source) و t (مقصد | Sink) در گراف داده شده است. هدف پیدا کردن بیشینه جریان ممکنی است که از s به t با در نظر داشتن محدودیت‌های زیر، شکل می‌گیرد.

فهرست مطالب این نوشته پنهان کردن

1. الگوریتم فورد–فالکرسون برای حل مساله بیشینه جریان

2. پیاده‌سازی الگوریتم ساده بالا

3. حل مساله بیشینه جریان در ++C

4. حل مساله بیشینه جریان در جاوا

5. حل مساله بیشینه جریان در پایتون

6. حل مساله بیشینه جریان در #C

جریان روی یک یال از ظرفیت داده شده روی آن یال سر ریز نمی‌کند.
جریان ورودی برای هر راس، به جز s و t، مساوی با جریان خروجی است.

برای مثال، می‌توان گراف زیر را در نظر گرفت.

بیشینه جریان ممکن در گراف بالا برابر با ۲۳ است.

الگوریتم فورد–فالکرسون برای حل مساله بیشینه جریان

در ادامه، «الگوریتم فورد–فالکرسون» (Ford-Fulkerson Algorithm) برای حل مساله بیشینه جریان ارائه شده است.

با جریان اولیه ۰ شروع کن.
تا هنگامی که یک مسیر تجمعی از مبدا به مقصد وجود دارد، این «مسیر-جریان» (Path-Flow) را به «جریان» اضافه کن.
جریان را بازگردان.

پیچیدگی زمانی الگوریتم بالا از درجه O(max_flow * E)‎ است. هنگامی که یک مسیر تجمعی وجود داشته باشد، یک حلقه اجرا می‌شود. در بدترین حالت، ممکن است ۱ واحد جریان در هر تکرار اضافه شود. بنابراین، پیچیدگی زمانی برابر با O(max_flow * E)‎ خواهد شد.

پیاده‌سازی الگوریتم ساده بالا

برای پیاده‌سازی الگوریتم بالا، ابتدا باید مفهوم «گراف باقیمانده» (Residual Graph) تعریف شود که برای درک این پیاده‌سازی مورد نیاز است. گراف باقیمانده از یک شبکه جریان، گرافی است که جریان اضافی ممکن را نشان می‌دهد. اگر مسیری از مبدا به مقصد وجود داشته باشد، این امکان وجود دارد که جریان اضافه شود. هر یال از گراف دارای مقداری است که به آن ظرفیت باقیمانده گفته می‌شود. ظرفیت باقیمانده برابر با ظرفیت اصلی یال‌ها منهای جریان کنونی است. ظرفیت باقیمانده اساسا ظرفیت کنونی یال‌ها است.

اکنون، پیرامون جزئیات پیاده‌سازی صحبت خواهد شد. اگر هیچ یالی بین دو راس از گراف باقیمانده وجود نداشته باشد، ظرفیت باقیمانده برابر با ۰ است. می‌توان با توجه به اینکه هیچ جریان اولیه‌ای وجود ندارد، به گراف باقیمانده مقداردهی اولیه کرد. همچنین، ظرفیت باقیمانده اولیه برابر با ظرفیت اصلی است. برای پیدا کردن مسیر تجمعی، می‌توان از الگوریتم «جستجوی اول سطح» (Breadth-First Search) یا «جستجوی اول عمق» (Depth-First Search) استفاده کرد. در پیاده‌سازی زیر، برای پیدا کردن مسیر تجمعی از BFS استفاده شده است.

با استفاده از BFS، می‌توان بررسی کرد که آیا مسیری از مبدا به مقصد وجود دارد یا خیر. همچنین، BFS، آرایه parent[]‎ را می‌سازد. با استفاده از آرایه parent[]‎، پیمایش در مسیر یافته شده انجام و جریان احتمالی از طریق این مسیر با پیدا کردن ظرفیت باقیمانده در طول مسیر پیدا می‌شود. در ادامه، جریان مسیر یافت شده به جریان کلی اضافه می‌شود. نکته مهم آن است که به روز رسانی ظرفیت باقیمانده‌ها در گراف باقیمانده مورد نیاز است. جریان مسیر از همه یال‌ها در طول مسیر کسر می‌شود و جریان مسیر در امتداد یال‌های معکوس اضافه می‌شود. نیاز به اضافه کردن جریان مسیر در طول یال‌های معکوس است، زیرا ممکن است بعدا نیاز به ارسال جریان در جهت معکوس باشد.

حل مساله بیشینه جریان در ++C

// C++ program for implementation of Ford Fulkerson algorithm 
#include <iostream> 
#include <limits.h> 
#include <string.h> 
#include <queue> 
using namespace std; 
  
// Number of vertices in given graph 
#define V 6 
  
/* Returns true if there is a path from source 's' to sink 't' in 
  residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[]) 
{ 
    // Create a visited array and mark all vertices as not visited 
    bool visited[V]; 
    memset(visited, 0, sizeof(visited)); 
  
    // Create a queue, enqueue source vertex and mark source vertex 
    // as visited 
    queue <int> q; 
    q.push(s); 
    visited[s] = true; 
    parent[s] = -1; 
  
    // Standard BFS Loop 
    while (!q.empty()) 
    { 
        int u = q.front(); 
        q.pop(); 
  
        for (int v=0; v<V; v++) 
        { 
            if (visited[v]==false && rGraph[u][v] > 0) 
            { 
                q.push(v); 
                parent[v] = u; 
                visited[v] = true; 
            } 
        } 
    } 
  
    // If we reached sink in BFS starting from source, then return 
    // true, else false 
    return (visited[t] == true); 
} 
  
// Returns the maximum flow from s to t in the given graph 
int fordFulkerson(int graph[V][V], int s, int t) 
{ 
    int u, v; 
  
    // Create a residual graph and fill the residual graph with 
    // given capacities in the original graph as residual capacities 
    // in residual graph 
    int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates  
                     // residual capacity of edge from i to j (if there 
                     // is an edge. If rGraph[i][j] is 0, then there is not)   
    for (u = 0; u < V; u++) 
        for (v = 0; v < V; v++) 
             rGraph[u][v] = graph[u][v]; 
  
    int parent[V];  // This array is filled by BFS and to store path 
  
    int max_flow = 0;  // There is no flow initially 
  
    // Augment the flow while tere is path from source to sink 
    while (bfs(rGraph, s, t, parent)) 
    { 
        // Find minimum residual capacity of the edges along the 
        // path filled by BFS. Or we can say find the maximum flow 
        // through the path found. 
        int path_flow = INT_MAX; 
        for (v=t; v!=s; v=parent[v]) 
        { 
            u = parent[v]; 
            path_flow = min(path_flow, rGraph[u][v]); 
        } 
  
        // 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; 
        } 
  
        // Add path flow to overall flow 
        max_flow += path_flow; 
    } 
  
    // Return the overall flow 
    return max_flow; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    // Let us create a graph shown in the above example 
    int graph[V][V] = { {0, 16, 13, 0, 0, 0}, 
                        {0, 0, 10, 12, 0, 0}, 
                        {0, 4, 0, 0, 14, 0}, 
                        {0, 0, 9, 0, 0, 20}, 
                        {0, 0, 0, 7, 0, 4}, 
                        {0, 0, 0, 0, 0, 0} 
                      }; 
  
    cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5); 
  
    return 0; 
}

100

101

102

103

104

105

106

107

108

109

110

111

112

// C++ program for implementation of Ford Fulkerson algorithm

#include <iostream>

#include <limits.h>

#include <string.h>

#include <queue>

using namespace std;

// Number of vertices in given graph

#define V 6

/* Returns true if there is a path from source 's' to sink 't' in

residual graph. Also fills parent[] to store the path */

bool bfs(int rGraph[V][V], int s, int t, int parent[])

{

// Create a visited array and mark all vertices as not visited

bool visited[V];

memset(visited, 0, sizeof(visited));

// Create a queue, enqueue source vertex and mark source vertex

// as visited

queue <int> q;

q.push(s);

visited[s] = true;

parent[s] = -1;

// Standard BFS Loop

while (!q.empty())

{

int u = q.front();

q.pop();

for (int v=0; v<V; v++)

{

if (visited[v]==false && rGraph[u][v] > 0)

{

q.push(v);

parent[v] = u;

visited[v] = true;

}

// If we reached sink in BFS starting from source, then return

// true, else false

return (visited[t] == true);

}

// Returns the maximum flow from s to t in the given graph

int fordFulkerson(int graph[V][V], int s, int t)

{

int u, v;

// Create a residual graph and fill the residual graph with

// given capacities in the original graph as residual capacities

// in residual graph

int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates

// residual capacity of edge from i to j (if there

// is an edge. If rGraph[i][j] is 0, then there is not)

for (u = 0; u < V; u++)

for (v = 0; v < V; v++)

rGraph[u][v] = graph[u][v];

int parent[V]; // This array is filled by BFS and to store path

int max_flow = 0; // There is no flow initially

// Augment the flow while tere is path from source to sink

while (bfs(rGraph, s, t, parent))

{

// Find minimum residual capacity of the edges along the

// path filled by BFS. Or we can say find the maximum flow

// through the path found.

int path_flow = INT_MAX;

for (v=t; v!=s; v=parent[v])

{

u = parent[v];

path_flow = min(path_flow, rGraph[u][v]);

}

// 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;

}

// Add path flow to overall flow

max_flow += path_flow;

}

// Return the overall flow

return max_flow;

}

// Driver program to test above functions

int main()

{

// Let us create a graph shown in the above example

int graph[V][V] = { {0, 16, 13, 0, 0, 0},

{0, 0, 10, 12, 0, 0},

{0, 4, 0, 0, 14, 0},

{0, 0, 9, 0, 0, 20},

{0, 0, 0, 7, 0, 4},

{0, 0, 0, 0, 0, 0}

};

cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);

return 0;

}

حل مساله بیشینه جریان در جاوا

// Java program for implementation of Ford Fulkerson algorithm 
import java.util.*; 
import java.lang.*; 
import java.io.*; 
import java.util.LinkedList; 
  
class MaxFlow 
{ 
    static final int V = 6;    //Number of vertices in graph 
  
    /* Returns true if there is a path from source 's' to sink 
      't' in residual graph. Also fills parent[] to store the 
      path */
    boolean bfs(int rGraph[][], int s, int t, int parent[]) 
    { 
        // Create a visited array and mark all vertices as not 
        // visited 
        boolean visited[] = new boolean[V]; 
        for(int i=0; i<V; ++i) 
            visited[i]=false; 
  
        // Create a queue, enqueue source vertex and mark 
        // source vertex as visited 
        LinkedList<Integer> queue = new LinkedList<Integer>(); 
        queue.add(s); 
        visited[s] = true; 
        parent[s]=-1; 
  
        // Standard BFS Loop 
        while (queue.size()!=0) 
        { 
            int u = queue.poll(); 
  
            for (int v=0; v<V; v++) 
            { 
                if (visited[v]==false && rGraph[u][v] > 0) 
                { 
                    queue.add(v); 
                    parent[v] = u; 
                    visited[v] = true; 
                } 
            } 
        } 
  
        // If we reached sink in BFS starting from source, then 
        // return true, else false 
        return (visited[t] == true); 
    } 
  
    // Returns tne maximum flow from s to t in the given graph 
    int fordFulkerson(int graph[][], int s, int t) 
    { 
        int u, v; 
  
        // Create a residual graph and fill the residual graph 
        // with given capacities in the original graph as 
        // residual capacities in residual graph 
  
        // Residual graph where rGraph[i][j] indicates 
        // residual capacity of edge from i to j (if there 
        // is an edge. If rGraph[i][j] is 0, then there is 
        // not) 
        int rGraph[][] = new int[V][V]; 
  
        for (u = 0; u < V; u++) 
            for (v = 0; v < V; v++) 
                rGraph[u][v] = graph[u][v]; 
  
        // This array is filled by BFS and to store path 
        int parent[] = new int[V]; 
  
        int max_flow = 0;  // There is no flow initially 
  
        // Augment the flow while tere is path from source 
        // to sink 
        while (bfs(rGraph, s, t, parent)) 
        { 
            // Find minimum residual capacity of the edhes 
            // along the path filled by BFS. Or we can say 
            // find the maximum flow through the path found. 
            int path_flow = Integer.MAX_VALUE; 
            for (v=t; v!=s; v=parent[v]) 
            { 
                u = parent[v]; 
                path_flow = Math.min(path_flow, rGraph[u][v]); 
            } 
  
            // 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; 
            } 
  
            // Add path flow to overall flow 
            max_flow += path_flow; 
        } 
  
        // Return the overall flow 
        return max_flow; 
    } 
  
    // Driver program to test above functions 
    public static void main (String[] args) throws java.lang.Exception 
    { 
        // Let us create a graph shown in the above example 
        int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0}, 
                                     {0, 0, 10, 12, 0, 0}, 
                                     {0, 4, 0, 0, 14, 0}, 
                                     {0, 0, 9, 0, 0, 20}, 
                                     {0, 0, 0, 7, 0, 4}, 
                                     {0, 0, 0, 0, 0, 0} 
                                   }; 
        MaxFlow m = new MaxFlow(); 
  
        System.out.println("The maximum possible flow is " + 
                           m.fordFulkerson(graph, 0, 5)); 
  
    } 
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

// Java program for implementation of Ford Fulkerson algorithm

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.LinkedList;

class MaxFlow

{

static final int V = 6; //Number of vertices in graph

/* Returns true if there is a path from source 's' to sink

't' in residual graph. Also fills parent[] to store the

path */

boolean bfs(int rGraph[][], int s, int t, int parent[])

{

// Create a visited array and mark all vertices as not

// visited

boolean visited[] = new boolean[V];

for(int i=0; i<V; ++i)

visited[i]=false;

// Create a queue, enqueue source vertex and mark

// source vertex as visited

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

queue.add(s);

visited[s] = true;

parent[s]=-1;

// Standard BFS Loop

while (queue.size()!=0)

{

int u = queue.poll();

for (int v=0; v<V; v++)

{

if (visited[v]==false && rGraph[u][v] > 0)

{

queue.add(v);

parent[v] = u;

visited[v] = true;

}

// If we reached sink in BFS starting from source, then

// return true, else false

return (visited[t] == true);

}

// Returns tne maximum flow from s to t in the given graph

int fordFulkerson(int graph[][], int s, int t)

{

int u, v;

// Create a residual graph and fill the residual graph

// with given capacities in the original graph as

// residual capacities in residual graph

// Residual graph where rGraph[i][j] indicates

// residual capacity of edge from i to j (if there

// is an edge. If rGraph[i][j] is 0, then there is

// not)

int rGraph[][] = new int[V][V];

for (u = 0; u < V; u++)

for (v = 0; v < V; v++)

rGraph[u][v] = graph[u][v];

// This array is filled by BFS and to store path

int parent[] = new int[V];

int max_flow = 0; // There is no flow initially

// Augment the flow while tere is path from source

// to sink

while (bfs(rGraph, s, t, parent))

{

// Find minimum residual capacity of the edhes

// along the path filled by BFS. Or we can say

// find the maximum flow through the path found.

int path_flow = Integer.MAX_VALUE;

for (v=t; v!=s; v=parent[v])

{

u = parent[v];

path_flow = Math.min(path_flow, rGraph[u][v]);

}

// 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;

}

// Add path flow to overall flow

max_flow += path_flow;

}

// Return the overall flow

return max_flow;

}

// Driver program to test above functions

public static void main (String[] args) throws java.lang.Exception

{

// Let us create a graph shown in the above example

int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},

{0, 0, 10, 12, 0, 0},

{0, 4, 0, 0, 14, 0},

{0, 0, 9, 0, 0, 20},

{0, 0, 0, 7, 0, 4},

{0, 0, 0, 0, 0, 0}

};

MaxFlow m = new MaxFlow();

System.out.println("The maximum possible flow is " +

m.fordFulkerson(graph, 0, 5));

}

حل مساله بیشینه جریان در پایتون

# Python program for implementation of Ford Fulkerson algorithm 
   
from collections import defaultdict 
   
#This class represents a directed graph using adjacency matrix representation 
class Graph: 
   
    def __init__(self,graph): 
        self.graph = graph # residual graph 
        self. ROW = len(graph) 
        #self.COL = len(gr[0]) 
          
   
    '''Returns true if there is a path from source 's' to sink 't' in 
    residual graph. Also fills parent[] to store the path '''
    def BFS(self,s, t, parent): 
  
        # Mark all the vertices as not visited 
        visited =[False]*(self.ROW) 
          
        # Create a queue for BFS 
        queue=[] 
          
        # Mark the source node as visited and enqueue it 
        queue.append(s) 
        visited[s] = True
           
         # Standard BFS Loop 
        while queue: 
  
            #Dequeue a vertex from queue and print it 
            u = queue.pop(0) 
          
            # Get all adjacent vertices of the dequeued vertex u 
            # If a adjacent has not been visited, then mark it 
            # visited and enqueue it 
            for ind, val in enumerate(self.graph[u]): 
                if visited[ind] == False and val > 0 : 
                    queue.append(ind) 
                    visited[ind] = True
                    parent[ind] = u 
  
        # If we reached sink in BFS starting from source, then return 
        # true, else false 
        return True if visited[t] else False
              
      
    # Returns tne maximum flow from s to t in the given graph 
    def FordFulkerson(self, source, sink): 
  
        # This array is filled by BFS and to store path 
        parent = [-1]*(self.ROW) 
  
        max_flow = 0 # There is no flow initially 
  
        # Augment the flow while there is path from source to sink 
        while self.BFS(source, sink, parent) : 
  
            # Find minimum residual capacity of the edges along the 
            # path filled by BFS. Or we can say find the maximum flow 
            # through the path found. 
            path_flow = float("Inf") 
            s = sink 
            while(s !=  source): 
                path_flow = min (path_flow, self.graph[parent[s]][s]) 
                s = parent[s] 
  
            # Add path flow to overall flow 
            max_flow +=  path_flow 
  
            # update residual capacities of the edges and reverse edges 
            # along the path 
            v = sink 
            while(v !=  source): 
                u = parent[v] 
                self.graph[u][v] -= path_flow 
                self.graph[v][u] += path_flow 
                v = parent[v] 
  
        return max_flow 
  
   
# Create a graph given in the above diagram 
  
graph = [[0, 16, 13, 0, 0, 0], 
        [0, 0, 10, 12, 0, 0], 
        [0, 4, 0, 0, 14, 0], 
        [0, 0, 9, 0, 0, 20], 
        [0, 0, 0, 7, 0, 4], 
        [0, 0, 0, 0, 0, 0]] 
  
g = Graph(graph) 
  
source = 0; sink = 5
   
print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink)) 
  
#This code is contributed by Neelam Yadav

# Python program for implementation of Ford Fulkerson algorithm

from collections import defaultdict

#This class represents a directed graph using adjacency matrix representation

class Graph:

def __init__(self,graph):

self.graph = graph # residual graph

self. ROW = len(graph)

#self.COL = len(gr[0])

'''Returns true if there is a path from source 's' to sink 't' in

residual graph. Also fills parent[] to store the path '''

def BFS(self,s, t, parent):

# Mark all the vertices as not visited

visited =[False]*(self.ROW)

# Create a queue for BFS

queue=[]

# Mark the source node as visited and enqueue it

queue.append(s)

visited[s] = True

# Standard BFS Loop

while queue:

#Dequeue a vertex from queue and print it

u = queue.pop(0)

# Get all adjacent vertices of the dequeued vertex u

# If a adjacent has not been visited, then mark it

# visited and enqueue it

for ind, val in enumerate(self.graph[u]):

if visited[ind] == False and val > 0 :

queue.append(ind)

visited[ind] = True

parent[ind] = u

# If we reached sink in BFS starting from source, then return

# true, else false

return True if visited[t] else False

# Returns tne maximum flow from s to t in the given graph

def FordFulkerson(self, source, sink):

# This array is filled by BFS and to store path

parent = [-1]*(self.ROW)

max_flow = 0 # There is no flow initially

# Augment the flow while there is path from source to sink

while self.BFS(source, sink, parent) :

# Find minimum residual capacity of the edges along the

# path filled by BFS. Or we can say find the maximum flow

# through the path found.

path_flow = float("Inf")

s = sink

while(s != source):

path_flow = min (path_flow, self.graph[parent[s]][s])

s = parent[s]

# Add path flow to overall flow

max_flow += path_flow

# update residual capacities of the edges and reverse edges

# along the path

v = sink

while(v != source):

u = parent[v]

self.graph[u][v] -= path_flow

self.graph[v][u] += path_flow

v = parent[v]

return max_flow

# Create a graph given in the above diagram

graph = [[0, 16, 13, 0, 0, 0],

[0, 0, 10, 12, 0, 0],

[0, 4, 0, 0, 14, 0],

[0, 0, 9, 0, 0, 20],

[0, 0, 0, 7, 0, 4],

[0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0; sink = 5

print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))

#This code is contributed by Neelam Yadav

حل مساله بیشینه جریان در #C

// C# program for implementation  
// of Ford Fulkerson algorithm 
using System; 
using System.Collections.Generic; 
  
public class MaxFlow 
{ 
    static readonly int V = 6; //Number of vertices in graph 
  
    /* Returns true if there is a path 
    from source 's' to sink 't' in residual 
    graph. Also fills parent[] to store the 
    path */
    bool bfs(int [,]rGraph, int s, int t, int []parent) 
    { 
        // Create a visited array and mark  
        // all vertices as not visited 
        bool []visited = new bool[V]; 
        for(int i = 0; i < V; ++i) 
            visited[i] = false; 
  
        // Create a queue, enqueue source vertex and mark 
        // source vertex as visited 
        List<int> queue = new List<int>(); 
        queue.Add(s); 
        visited[s] = true; 
        parent[s] = -1; 
  
        // Standard BFS Loop 
        while (queue.Count != 0) 
        { 
            int u = queue[0]; 
                queue.RemoveAt(0); 
  
            for (int v = 0; v < V; v++) 
            { 
                if (visited[v] == false && rGraph[u, v] > 0) 
                { 
                    queue.Add(v); 
                    parent[v] = u; 
                    visited[v] = true; 
                } 
            } 
        } 
  
        // If we reached sink in BFS  
        // starting from source, then 
        // return true, else false 
        return (visited[t] == true); 
    } 
  
    // Returns tne maximum flow 
    // from s to t in the given graph 
    int fordFulkerson(int [,]graph, int s, int t) 
    { 
        int u, v; 
  
        // Create a residual graph and fill  
        // the residual graph with given  
        // capacities in the original graph as 
        // residual capacities in residual graph 
  
        // Residual graph where rGraph[i,j]  
        // indicates residual capacity of  
        // edge from i to j (if there is an  
        // edge. If rGraph[i,j] is 0, then  
        // there is not) 
        int [,]rGraph = new int[V, V]; 
  
        for (u = 0; u < V; u++) 
            for (v = 0; v < V; v++) 
                rGraph[u, v] = graph[u, v]; 
  
        // This array is filled by BFS and to store path 
        int []parent = new int[V]; 
  
        int max_flow = 0; // There is no flow initially 
  
        // Augment the flow while tere is path from source 
        // to sink 
        while (bfs(rGraph, s, t, parent)) 
        { 
            // Find minimum residual capacity of the edhes 
            // along the path filled by BFS. Or we can say 
            // find the maximum flow through the path found. 
            int path_flow = int.MaxValue; 
            for (v = t; v != s; v = parent[v]) 
            { 
                u = parent[v]; 
                path_flow = Math.Min(path_flow, rGraph[u,v]); 
            } 
  
            // 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; 
            } 
  
            // Add path flow to overall flow 
            max_flow += path_flow; 
        } 
  
        // Return the overall flow 
        return max_flow; 
    } 
  
    // Driver code 
    public static void Main () 
    { 
        // Let us create a graph shown in the above example 
        int [,]graph =new int[,] { {0, 16, 13, 0, 0, 0}, 
                                    {0, 0, 10, 12, 0, 0}, 
                                    {0, 4, 0, 0, 14, 0}, 
                                    {0, 0, 9, 0, 0, 20}, 
                                    {0, 0, 0, 7, 0, 4}, 
                                    {0, 0, 0, 0, 0, 0} 
                                }; 
        MaxFlow m = new MaxFlow(); 
  
        Console.WriteLine("The maximum possible flow is " + 
                        m.fordFulkerson(graph, 0, 5)); 
  
    } 
} 
  
/* This code contributed by PrinciRaj1992 */

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

// C# program for implementation

// of Ford Fulkerson algorithm

using System;

using System.Collections.Generic;

public class MaxFlow

{

static readonly int V = 6; //Number of vertices in graph

/* Returns true if there is a path

from source 's' to sink 't' in residual

graph. Also fills parent[] to store the

path */

bool bfs(int [,]rGraph, int s, int t, int []parent)

{

// Create a visited array and mark

// all vertices as not visited

bool []visited = new bool[V];

for(int i = 0; i < V; ++i)

visited[i] = false;

// Create a queue, enqueue source vertex and mark

// source vertex as visited

List<int> queue = new List<int>();

queue.Add(s);

visited[s] = true;

parent[s] = -1;

// Standard BFS Loop

while (queue.Count != 0)

{

int u = queue[0];

queue.RemoveAt(0);

for (int v = 0; v < V; v++)

{

if (visited[v] == false && rGraph[u, v] > 0)

{

queue.Add(v);

parent[v] = u;

visited[v] = true;

}

// If we reached sink in BFS

// starting from source, then

// return true, else false

return (visited[t] == true);

}

// Returns tne maximum flow

// from s to t in the given graph

int fordFulkerson(int [,]graph, int s, int t)

{

int u, v;

// Create a residual graph and fill

// the residual graph with given

// capacities in the original graph as

// residual capacities in residual graph

// Residual graph where rGraph[i,j]

// indicates residual capacity of

// edge from i to j (if there is an

// edge. If rGraph[i,j] is 0, then

// there is not)

int [,]rGraph = new int[V, V];

for (u = 0; u < V; u++)

for (v = 0; v < V; v++)

rGraph[u, v] = graph[u, v];

// This array is filled by BFS and to store path

int []parent = new int[V];

int max_flow = 0; // There is no flow initially

// Augment the flow while tere is path from source

// to sink

while (bfs(rGraph, s, t, parent))

{

// Find minimum residual capacity of the edhes

// along the path filled by BFS. Or we can say

// find the maximum flow through the path found.

int path_flow = int.MaxValue;

for (v = t; v != s; v = parent[v])

{

u = parent[v];

path_flow = Math.Min(path_flow, rGraph[u,v]);

}

// 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;

}

// Add path flow to overall flow

max_flow += path_flow;

}

// Return the overall flow

return max_flow;

}

// Driver code

public static void Main ()

{

// Let us create a graph shown in the above example

int [,]graph =new int[,] { {0, 16, 13, 0, 0, 0},

{0, 0, 10, 12, 0, 0},

{0, 4, 0, 0, 14, 0},

{0, 0, 9, 0, 0, 20},

{0, 0, 0, 7, 0, 4},

{0, 0, 0, 0, 0, 0}

};

MaxFlow m = new MaxFlow();

Console.WriteLine("The maximum possible flow is " +

m.fordFulkerson(graph, 0, 5));

}

/* This code contributed by PrinciRaj1992 */

خروجی قطعه کدهای بالا به صورت زیر است.

The maximum possible flow is 23

1	The maximum possible flow is 23

پیاده‌سازی بالا از الگوریتم فورد–فالکرسون را «الگوریتم ادموندز کارپ» (Edmonds-Karp Algorithm) می‌گویند. ایده اصلی نهفته در پس استفاده از الگوریتم ادموندز کارپ، استفاده از BFS است؛ زیرا BFS همیشه مسیری با کمترین تعداد یال را انتخاب می‌کند.

هنگامی که BFS مورد استفاده قرار می‌گیرد، پیچیدگی زمانی بدترین حالت را می‌توان به O(VE²)‎ کاهش داد. پیاده‌سازی بالا از ارائه ماتریس مجاورت استفاده می‌کند و BFS دارای پیچیدگی زمانی از درجه O(V²)‎ است.

این مسأله با توجه به اینکه در بسیاری از موقعیت‌های عملی به وقوع می‌پیوندد، بسیار حائز است. از جمله مثال‌هایی برای مسأله بیشینه جریان می‌توان زد، افزایش حمل و نقل با توجه به محدودیت‌های ترافیکی داده شده و افزایش جریان بسته‌ها در شبکه‌های کامپیوتری است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

به اشتراک بگذارید:

منبع GeeksforGeeks

الهام حصارکی (+)

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

حل مساله بیشینه جریان — راهنمای جامع

الگوریتم فورد–فالکرسون برای حل مساله بیشینه جریان

پیاده‌سازی الگوریتم ساده بالا

حل مساله بیشینه جریان در ++C

حل مساله بیشینه جریان در جاوا

حل مساله بیشینه جریان در پایتون

حل مساله بیشینه جریان در #C

نظر شما چیست؟
لغو پاسخ

نظر شما چیست؟

برچسب‌ها

الگوریتم فورد–فالکرسون برای حل مساله بیشینه جریان

پیاده‌سازی الگوریتم ساده بالا

حل مساله بیشینه جریان در ++C

حل مساله بیشینه جریان در جاوا

حل مساله بیشینه جریان در پایتون

حل مساله بیشینه جریان در #C

مطالب مرتبط

نظر شما چیست؟ لغو پاسخ

نظر شما چیست؟

برچسب‌ها

نظر شما چیست؟
لغو پاسخ