Beginner's Guide to Network Flow & Matching Algorithms
An introductory quiz on network flow and matching algorithms for backend developers.
Questions in this quiz
15 questions on Beginner's Guide to Network Flow & Matching Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary goal of the Ford-Fulkerson method in network flow?
- ATo find the minimum spanning tree
- BTo find the shortest path
- CTo find the maximum flow
- DTo find the longest path
2.In a flow network, what does a 'source' node represent?
- AA node where flow originates
- BA node where flow terminates
- CA node with no incoming edges
- DA node with no outgoing edges
3.What is the purpose of the Edmonds-Karp algorithm?
- ATo find the shortest path
- BTo find the minimum cut
- CTo find the longest path
- DTo find the maximum flow using BFS
4.What does the term 'capacity' refer to in a flow network?
- AThe maximum number of nodes
- BThe minimum flow through an edge
- CThe maximum flow through an edge
- DThe total number of edges
5.Which algorithm is commonly used for solving the Maximum Bipartite Matching problem?
- AHopcroft-Karp algorithm
- BKruskal's algorithm
- CPrim's algorithm
- DDijkstra's algorithm
6.In network flow, what is an 'augmenting path'?
- AA path with maximum capacity
- BA path that decreases overall flow
- CA path with no flow
- DA path that increases overall flow
7.What is the 'residual network' in the context of flow networks?
- AA network showing remaining capacities
- BA network with maximum flow
- CA network with no flow
- DA network with minimum flow
8.What is the main application of the Max-Flow Min-Cut Theorem?
- AFinding minimum cuts
- BFinding maximum flow
- CFinding maximum matching
- DFinding shortest paths
9.In a bipartite graph, what is a 'matching'?
- AA set of vertices with common edges
- BA set of edges with no common vertices
- CA set of edges with common vertices
- DA set of vertices with no common edges
10.What is the primary use of the Dinic's algorithm?
- AFinding maximum flow
- BFinding minimum spanning tree
- CFinding shortest paths
- DFinding longest paths
11.Which data structure is commonly used in the Edmonds-Karp algorithm?
- AQueue
- BPriority Queue
- CHeap
- DStack
12.What does the term 'cut' refer to in network flow?
- AA partition of the graph's edges
- BA path with maximum flow
- CA path with minimum flow
- DA partition of the graph's nodes
13.What is the complexity of the Ford-Fulkerson method in the worst case?
- AO(V+E)
- BO(VE^2)
- CO(V^2E)
- DO(E^2)
14.In network flow, what is a 'sink' node?
- AA node where flow originates
- BA node with no outgoing edges
- CA node with no incoming edges
- DA node where flow terminates
15.What is the main advantage of using the Edmonds-Karp algorithm over the basic Ford-Fulkerson method?
- AIt finds the shortest path
- BIt guarantees polynomial time complexity
- CIt uses DFS instead of BFS
- DIt finds the longest path