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 dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

visited[s] = True
        path.append(s)

if s == t:
            return path

for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

return None

def fordFulkerson(self, source, sink):
        max_flow = 0

path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

max_flow += path_flow

path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

path = self.dfs(source, sink)

return max_flow

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.fordFulkerson(source, sink))

#Python

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

#define V 6 // Total vertices

// Graph structure to hold the adjacency matrix and vertex names
typedef struct {
    int adjMatrix[V][V];
    char* vertexNames[V];
} Graph;

// Initialize the graph with vertex names and zero capacities
void initGraph(Graph* g, char* names[]) {
    memset(g->adjMatrix, 0, sizeof(g->adjMatrix));
    for (int i = 0; i < V; i++) {
        g->vertexNames[i] = names[i];
    }
}

// Add edge to the graph
void addEdge(Graph* g, int from, int to, int cap) {
    g->adjMatrix[from][to] = cap;
}

// Depth-First Search (DFS) for finding an augmenting path
int dfs(Graph* g, int s, int t, int parent[]) {
    static int visited[V]; // Static array to keep track of visited vertices
    memset(visited, 0, sizeof(visited));
    
    // Inner DFS function to recursively search for path
    int dfsVisit(int u) {
        visited[u] = 1;
        if (u == t) return 1; // Sink reached
        
        for (int v = 0; v < V; v++) {
            if (!visited[v] && g->adjMatrix[u][v] > 0) {
                parent[v] = u;
                if (dfsVisit(v)) return 1; // Path found
            }
        }
        return 0;
    }
    
    return dfsVisit(s);
}

// Ford-Fulkerson algorithm for finding maximum flow
int fordFulkerson(Graph* g, int source, int sink) {
    int u, v, max_flow = 0, parent[V];
    
    while (dfs(g, source, sink, parent)) {
        int path_flow = INT_MAX;
        
        // Find minimum capacity in the found path
        for (v = sink; v != source; v = parent[v]) {
            u = parent[v];
            path_flow = path_flow < g->adjMatrix[u][v] ? path_flow : g->adjMatrix[u][v];
        }
        
        // Update capacities and reverse edges along the path
        for (v = sink; v != source; v = parent[v]) {
            u = parent[v];
            g->adjMatrix[u][v] -= path_flow;
            g->adjMatrix[v][u] += path_flow;
        }
        
        max_flow += path_flow;
        
        // Print the path from source to sink
        printf("Path: ");
        int path[V], pathSize = 0;
        for (v = sink; v != source; v = parent[v]) {
            path[pathSize++] = v;
        }
        
        for (int i = pathSize - 1; i >= 0; i--) {
            printf("%s", g->vertexNames[path[i]]);
            if (i > 0) printf(" -> ");
        }
        printf(", Flow: %d\n", path_flow);
    }
    
    return max_flow;
}

int main() {
    Graph g;
    char* vertexNames[] = {"s", "v1", "v2", "v3", "v4", "t"};
    initGraph(&g, vertexNames);
    
    // Adding edges with capacities
    addEdge(&g, 0, 1, 3);
    addEdge(&g, 0, 2, 7);
    addEdge(&g, 1, 3, 3);
    addEdge(&g, 1, 4, 4);
    addEdge(&g, 2, 1, 5);
    addEdge(&g, 2, 4, 3);
    addEdge(&g, 3, 4, 3);
    addEdge(&g, 3, 5, 2);
    addEdge(&g, 4, 5, 6);
    
    printf("The maximum possible flow is %d\n", fordFulkerson(&g, 0, 5));
    return 0;
}

//C

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

static class Graph {
        private int[][] adjMatrix;
        private String[] vertexData;
        private int size;

public Graph(int size) {
            this.size = size;
            this.adjMatrix = new int[size][size];
            this.vertexData = new String[size];
        }

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

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

private List<Integer> dfs(int s, int t, boolean[] visited) {
            if (s == t) {
                List<Integer> path = new ArrayList<>();
                path.add(s);
                return path;
            }
            visited[s] = true;

for (int v = 0; v < size; v++) {
                if (!visited[v] && adjMatrix[s][v] > 0) {
                    List<Integer> subPath = dfs(v, t, visited);
                    if (subPath != null) {
                        subPath.add(0, s);
                        return subPath;
                    }
                }
            }
            return null;
        }

public int fordFulkerson(int source, int sink) {
            int maxFlow = 0;
            boolean[] visited = new boolean[size];
            List<Integer> path;

while ((path = dfs(source, sink, new boolean[size])) != null) {
                int pathFlow = Integer.MAX_VALUE;
                for (int i = 0; i < path.size() - 1; i++) {
                    int u = path.get(i);
                    int v = path.get(i + 1);
                    pathFlow = Math.min(pathFlow, adjMatrix[u][v]);
                }

for (int i = 0; i < path.size() - 1; i++) {
                    int u = path.get(i);
                    int v = path.get(i + 1);
                    adjMatrix[u][v] -= pathFlow;
                    adjMatrix[v][u] += pathFlow;
                }

maxFlow += pathFlow;

// Convert path from vertex indices to names
                List<String> pathNames = new ArrayList<>();
                for (int vertex : path) {
                    pathNames.add(vertexData[vertex]);
                }
                System.out.println("Path: " + String.join(" -> ", pathNames) + ", Flow: " + pathFlow);
            }

return maxFlow;
        }
    }

public static void main(String[] args) {
        Graph g = new Graph(6);
        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;
        int maxFlow = g.fordFulkerson(source, sink);

System.out.println("The maximum possible flow is " + maxFlow);
    }
}

// Java