W3Schools 试用编辑器 - W3Schools 中文教程

Python

Java

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

def bfs(self, s, t, parent):
        visited = [False] * self.size
        queue = []  # Using list as a queue
        queue.append(s)
        visited[s] = True

while queue:
            u = queue.pop(0)  # Pop from the start of the list

for ind, val in enumerate(self.adj_matrix[u]):
                if not visited[ind] and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

return visited[t]

def edmonds_karp(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
                s = parent[s]

max_flow += path_flow
            v = sink
            while(v != source):
                u = parent[v]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow
                v = parent[v]

path = []
            v = sink
            while(v != source):
                path.append(v)
                v = parent[v]
            path.append(source)
            path.reverse()
            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

return max_flow

# Example usage:
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5
print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))

#Python

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

#define V 6 // Number of vertices
#define INF INT_MAX

int adjMatrix[V][V];
char* vertexNames[V] = {"s", "v1", "v2", "v3", "v4", "t"};

void addEdge(int from, int to, int capacity) {
    adjMatrix[from][to] = capacity;
}

// BFS function to find the shortest path from source to sink
bool bfs(int parent[], int source, int sink) {
    bool visited[V];
    memset(visited, 0, sizeof(visited));
    int queue[V], front = 0, rear = 0;

queue[rear++] = source;
    visited[source] = true;
    parent[source] = -1;

while (front < rear) {
        int u = queue[front++];

for (int v = 0; v < V; v++) {
            if (!visited[v] && adjMatrix[u][v] > 0) {
                if (v == sink) {
                    parent[v] = u;
                    return true;
                }
                queue[rear++] = v;
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    return false;
}

int edmondsKarp(int source, int sink) {
    int u, v;
    int parent[V]; // Store the path
    int maxFlow = 0;

while (bfs(parent, source, sink)) {
        int pathFlow = INF;

// Find the maximum flow through the path found.
        for (v = sink; v != source; v = parent[v]) {
            u = parent[v];
            pathFlow = pathFlow < adjMatrix[u][v] ? pathFlow : adjMatrix[u][v];
        }

// Update capacities and reverse capacities of the edges and reverse edges
        for (v = sink; v != source; v = parent[v]) {
            u = parent[v];
            adjMatrix[u][v] -= pathFlow;
            adjMatrix[v][u] += pathFlow;
        }

maxFlow += pathFlow;

// Code just for printing the path
        int path[V], pathSize = 0;
        for (v = sink; v != -1; v = parent[v]) {
            path[pathSize++] = v;
        }

printf("Path: ");
        for (int i = pathSize - 1; i >= 0; i--) {
            printf("%s", vertexNames[path[i]]);
            if (i > 0) printf(" -> ");
        }
        printf(", Flow: %d\n", pathFlow);
    }
    return maxFlow;
}

int main() {
    memset(adjMatrix, 0, sizeof(adjMatrix));

addEdge(0, 1, 3);
    addEdge(0, 2, 7);
    addEdge(1, 3, 3);
    addEdge(1, 4, 4);
    addEdge(2, 1, 5);
    addEdge(2, 4, 3);
    addEdge(3, 4, 3);
    addEdge(3, 5, 2);
    addEdge(4, 5, 6);

printf("The maximum possible flow is %d\n", edmondsKarp(0, 5));
    return 0;
}

//C

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static final int V = 6; // Assuming a fixed size for simplicity

static class Graph {
        int[][] adjMatrix = new int[V][V];
        String[] vertexData = new String[V];

void addEdge(int u, int v, int capacity) {
            adjMatrix[u][v] = capacity;
        }

void addVertexData(int vertex, String data) {
            vertexData[vertex] = data;
        }

boolean bfs(int s, int t, int[] parent) {
            boolean[] visited = new boolean[V];
            Queue<Integer> queue = new LinkedList<>();
            queue.add(s);
            visited[s] = true;
            parent[s] = -1;

while (!queue.isEmpty()) {
                int u = queue.poll();

for (int v = 0; v < V; v++) {
                    if (!visited[v] && adjMatrix[u][v] > 0) {
                        queue.add(v);
                        parent[v] = u;
                        visited[v] = true;
                    }
                }
            }
            return visited[t];
        }

int edmondsKarp(int source, int sink) {
            int u, v;
            int[] parent = new int[V];
            int maxFlow = 0;

while (bfs(source, sink, parent)) {
                int pathFlow = Integer.MAX_VALUE;
                for (v = sink; v != source; v = parent[v]) {
                    u = parent[v];
                    pathFlow = Math.min(pathFlow, adjMatrix[u][v]);
                }

for (v = sink; v != source; v = parent[v]) {
                    u = parent[v];
                    adjMatrix[u][v] -= pathFlow;
                    adjMatrix[v][u] += pathFlow;
                }

maxFlow += pathFlow;

// Printing the path
                LinkedList<String> path = new LinkedList<>();
                for (v = sink; v != source; v = parent[v]) {
                    path.addFirst(vertexData[v]);
                }
                path.addFirst(vertexData[source]);
                System.out.println("Path: " + String.join(" -> ", path) + ", Flow: " + pathFlow);
            }
            return maxFlow;
        }
    }

public static void main(String[] args) {
        Graph g = new Graph();
        String[] vertexNames = {"s", "v1", "v2", "v3", "v4", "t"};
        for (int i = 0; i < vertexNames.length; i++) {
            g.addVertexData(i, vertexNames[i]);
        }

g.addEdge(0, 1, 3);
        g.addEdge(0, 2, 7);
        g.addEdge(1, 3, 3);
        g.addEdge(1, 4, 4);
        g.addEdge(2, 1, 5);
        g.addEdge(2, 4, 3);
        g.addEdge(3, 4, 3);
        g.addEdge(3, 5, 2);
        g.addEdge(4, 5, 6);

int source = 0, sink = 5;
        System.out.println("The maximum possible flow is " + g.edmondsKarp(source, sink));
    }
}

// Java