c: Ford - Fulkerson Algorithm

/**
 * *****************************************************************************
 * @file        FordFulkersonAlgorithm.h
 * @brief       Ford - Fulkerson Algorithm in C Ford-Fulkerson算法（FFA）是一种 贪婪算法 ，用于计算流网络中的最大流量
 * IDE VSCODE C11
 * @author       (geovindu,Geovin Du,涂聚文)
 * @date        2023-09-26
 * @copyright   geovindu
 * *****************************************************************************
 */
#ifndef FORDFULKERSONALGORITHM_H
#define FORDFULKERSONALGORITHM_H



 
#include <stdio.h>
#include <stdlib.h>

#define A 0
#define B 1
#define C 2
#define MAX_NODES 10
#define O 1000000000



int flow[MAX_NODES][MAX_NODES];
int color[MAX_NODES];
int pred[MAX_NODES];

int head, tail;
int q[MAX_NODES + 2];

/**
 * @brief       
 * 
 * @param       x 
 * @param       y 
 * @return      int 
 */
int min(int x, int y);

/**
 * @brief       
 * 
 * @param       x 
 * @param       color 
 */
void enqueue(int x,int color[MAX_NODES]);

/**
 * @brief       
 * 
 * @param       color 
 * @return      int 
 */
int dequeue(int color[MAX_NODES]);

/**
 * @brief       
 * 
 * @param       start 
 * @param       target 
 * @param       color 
 * @param       pred 
 * @param       flow 
 * @param       capacity 
 * @return      int 
 */
int bfs(int start, int target,int color[MAX_NODES],int pred[MAX_NODES],int flow[MAX_NODES][MAX_NODES],int capacity[MAX_NODES][MAX_NODES]);


/**
 * @brief       
 * 
 * @param       source 
 * @param       sink 
 * @param       capacity 
 * @return      int 
 */
int FordFulkerson(int source, int sink,int capacity[MAX_NODES][MAX_NODES]);




#endif 

/**
 * *****************************************************************************
 * @file        FordFulkersonAlgorithm.c
 * @brief       Ford - Fulkerson Algorithm in C Ford-Fulkerson算法（FFA）是一种 贪婪算法 ，用于计算流网络中的最大流量
 * IDE VSCODE C11
 * @author       (geovindu,Geovin Du,涂聚文)
 * @date        2023-09-26
 * @copyright   geovindu
 * *****************************************************************************
 */

#include <stdio.h>
#include "include/FordFulkersonAlgorithm.h"



int fn=6;
int fe=7;
/**
 * @brief       
 * 
 * @param       x 
 * @param       y 
 * @return      int 
 */
int min(int x, int y) {
  return x < y ? x : y;
}



/**
 * @brief       
 * 
 * @param       x 
 * @param       color 
 */
void enqueue(int x,int color[MAX_NODES]) {
  q[tail] = x;
  tail++;
  color[x] = B;
}
/**
 * @brief       
 * 
 * @param       color 
 * @return      int 
 */
int dequeue(int color[MAX_NODES]) {
  int x = q[head];
  head++;
  color[x] = C;
  return x;
}

// Using BFS as a searching algorithm
/**
 * @brief       
 * 
 * @param       start 
 * @param       target 
 * @param       color 
 * @param       pred 
 * @param       flow 
 * @param       capacity 
 * @return      int 
 */
int bfs(int start, int target,int color[MAX_NODES],int pred[MAX_NODES],int flow[MAX_NODES][MAX_NODES],int capacity[MAX_NODES][MAX_NODES]) {
  int u, v;
  for (u = 0; u < fn; u++) {
    color[u] = A;
  }
  head = tail = 0;
  enqueue(start,color);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue(color);
    for (v = 0; v < fn; v++) {
      if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {
        enqueue(v,color);
        pred[v] = u;
      }
    }
  }
  return color[target] == C;
}

// Applying fordfulkerson algorithm
/**
 * @brief       
 * 
 * @param       source 
 * @param       sink 
 * @param       capacity 
 * @return      int 
 */
int FordFulkerson(int source, int sink,int capacity[MAX_NODES][MAX_NODES]) {
  int i, j, u;
  int max_flow = 0;
  for (i = 0; i < fn; i++) {
    for (j = 0; j < fn; j++) {
      flow[i][j] = 0;
    }
  }

  // Updating the residual values of edges
  while (bfs(source, sink,color,pred,flow,capacity)) {
    int increment = O;
    for (u = fn - 1; pred[u] >= 0; u = pred[u]) {
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    }
    for (u = fn - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    // Adding the path flows
    max_flow += increment;
  }
  return max_flow;
}

调用：

   //14 Ford - Fulkerson algorith 
    /**/

    printf("\n14 Ford - Fulkerson algorith \n");

    int capacity[10][10];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
        capacity[i][j] = 0;
        }
    }
    capacity[0][1] = 8;
    capacity[0][4] = 3;
    capacity[1][2] = 9;
    capacity[2][4] = 7;
    capacity[2][5] = 2;
    capacity[3][5] = 5;
    capacity[4][2] = 7;
    capacity[4][3] = 4;

    int s = 0, t =5;
    printf("\nMax Flow: %d\n", FordFulkerson(s, t,capacity));