Network Flow
Learn Network Flow (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Network Flow: Capacities and Flow A flow network is a directed graph where each edge has a capacity , with a source s and a sink t . A flow sends an amount along each edge so that: (1) capacity : 0 ≤ flow(u,v) ≤ capacity(u,v) ; (2) conservation : at every vertex except s and t, what flows in equals what flows out. The value of the flow is what leaves s. Pipes, traffic and data networks are all flow problems.
More lessons in Graphs
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Connected Components
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- DFS Topological Sort
- Shortest Path - BFS
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Shortest Path - Floyd-Warshall
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Bridges
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Maximum Flow
- Bipartite Matching