Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

This blog will discuss the time and space complexities of some of the graphs algorithms. These graph algorithms are Ford-Fulkerson and Edmonds Karp, Dinic’s algorithm, MPM algorithm, Bipartite, Euler path, strongly connected components algorithms.

The above algorithms are widely asked in coding contests and various coding interviews.

Maximum flow algorithms :

Ford Fulkerson and Edmonds Karp algorithm

Ford Fulkerson is an algorithm that is used to solve problems like max-flow-min-cut. In such types of problems, we are given a network with some vertices and the weighted edges between those vertices, and our task is to calculate the total flow that can process at a time. Here typically, flow means data flow.

The Ford Fulkerson algorithm was discovered in 1956 by Ford and Fulkerson. This algorithm assumes a network as a graph with a starting vertex ‘S’ and an ending vertex ‘E’. The intuition of the algorithm is that as long as there is a path from ‘S’ to ‘E’ that can take some flow the entire way, we send it. The path is called an augmenting path. We have to do this until there are no more augmenting paths.

Edmonds Karp algorithm is the implementation and improved form of the ford Fulkerson method. Some protocols are left in the Ford Fulkerson algorithm. That's why there is another algorithm called the Edmonds Karp algorithm, which is its improved form. Modification in the Ford Fulkerson algorithm is such that the augmented path is well defined in the Edmonds Karp algorithm. In the ford Fulkerson method, there is no well-defined augmented path.

Let's take an example as shown in the below figure, The first value of each edge represents the flow, which is initially 0, and the second value represents the capacity.

The following image shows the maximal flow of the above flow network.

Complexities

Ford Fulkerson algorithm has time complexity O(|E| * f), where |E| is the number of edges and ‘f’ is the maximum flow of a network because it depends on the maximum flow of the network. Edmonds Karp algorithm has time complexity O(|V| * E^2), where E is the number of edges and V is the number of vertices. Edmonds Karp algorithm is independent of the maximum flow of the network. The space complexity of the Edmonds Karp algorithm is O(V) in the worst case. Creating a queue and inserting each node in it takes O(V) extra space.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Dinic’s Algorithm

This algorithm was given by Yefim Denitz in 1970. This algorithm is used to solve the maximum flow problem as described above. The algorithm consists of several phases. In each phase, construct the layered network of the residual network of graphs, say ‘G’.then find an arbitrary blocking flow in the layered network and add it in the current flow.

Complexities

The time complexity of Dinic’s algorithm is O(V^2 * E). There are fewer than V phases possible, and each phase takes O(V * E) time. Hence its time complexity is O(V ^ 2 *E). The space complexity of Dinic’s algorithm is O(V + E). As it stores the data of all the edges and vertices.

MPM Algorithm

MPM stands for Malhotra, Pramod Kumar, and Maheshwari algorithm. It is quite similar to Dinic’s algorithm.

In this, blocking flows are found for level graphs of increasing depth. Here we need to consider the capacity of a vertex instead of the edge's capacity. Define the capacity c(v) of a vertex ‘V’ to be the minimum capacity of its incoming edges and the total capacity of its outgoing edges:

Intuitively, this is the maximum commodity that can be pushed through that vertex. This definition also applies to residual capacities obtained by subtracting a nonzero flow.

The MPM algorithm proceeds in phases. The residual graph is computed for the current flow in each phase, and the level graph ‘L’ is calculated. If t does not appear in ‘L’, we are done. Otherwise, all vertices not on a path from ‘S’ to ‘T’ in the level graph are deleted.

Complexities

The blocking flow for any vertex takes O(V ^ 2) time, and there are total ‘V’ vertices, so the overall time complexity of the above algorithm is O(V ^ 3). The space complexity of the MPM algorithm is O(V+E) as we are storing the information of all the vertices (capacity of the vertices) and the edges.

Bipartite Graph

If all the vertices of a graph ‘G’ can be divided into two independent sets, say ‘U’ and ‘V’ such that every edge either connects a vertex from ‘U’ to ‘V’ or from ‘V’ to ‘U’ then that graph is known as a bipartite graph. A bipartite graph is possible using two colors e if the graph coloring is possible using two colors.

The graph shown below is the bipartite graph as it can be colored using only two colors.

Algorithm

The algorithm to check whether the graph is bipartite or not is as follows:

Make any vertex to a source vertex and assign RED color to that vertex(from set ‘U’).

Color all the neighbors to the BLUE color (from set ‘V’).

Color all the neighbors of previously BLUE colored vertices to RED color (from set ‘U’).

In this way, color all the vertices from both sets.

If any vertex is already colored with another color, the graph is not bipartite; otherwise, the graph is bipartite.

Complexities

The time complexity of the above algorithm is O(V + E), where ‘V’ is the number of vertices, and ‘E’ is the number of edges in the graph. As each vertex and each edge is visited only once, that's why its time complexity is O(V + E). it takes O(V) extra space to store the color of each vertex.

An Euler path is where each edge of the graph is visited exactly once, and the starting vertex is different from the ending vertex. If the starting and ending vertex are the same, then the circuit formed is the Euler circuit.

How to know whether the graph is an Euler circuit or not?

If all the vertices in the graph are even, then we can say that the graph contains an Euler circuit. If exactly two vertices in the graph have an odd degree, it contains an Euler path.

Algorithm

The algorithm to check whether the graph contains an Euler circuit or not is very simple. As we need to traverse all the vertices and find the degree of that vertex. If the degree of all the vertices is even then the graph contains the Euler circuit.

Complexities

The time complexity of the above algorithm is O(V), as we need to visit each vertex exactly once. It takes O(1) extra space as we haven’t used any extra space.

Strongly Connected component

In a directed graph ‘G’, if there is a path between all the pairs of vertices then that graph is known as strongly connected. Similarly, if there is a path between all the pairs of vertices in the subgraph of ‘G’ then that subgraph is known as a strongly connected component (SCC).

We can find all the strongly connected components of a graph using Kosaraju’s Algorithm.

Complexities

The time complexity of Kosaraju’s algorithm is O(V + E), where ‘V’ is the total number of vertices in the graph and ‘E’ is the total number of edges in the graph. It takes O(V) extra space as we are creating the stack.

What is a Graph? A graph is a non-linear data structure made up of nodes and edges. The edges represent some correlation between the nodes. Nodes are sometimes known as vertices, while edges are lines or arcs that connect any two nodes in the network.

For which types of problems, the Ford-Fulkerson and Edmonds Karp algorithm used? Ford- Fulkerson and Edmonds Karp algorithm is used in Maximum flow network problems.

What is the maximum number of Strongly connected components possible in any directed graph of ‘V’ vertices? The maximum number of strongly connected components possible in any directed graph with ‘V’ vertices is V as each vertex can be treated as SCC.

How can we Implement BFS? BFS can be implemented using a queue. We keep adding the nodes present at the same level into the queue and pop out the nodes of the previous level from the queue. When we finish traversing one level, all the next level’s nodes are there in the queue at that time.

How can we Implement DFS? DFS can be implemented using a stack. The nodes encountered are stored in a stack. And once all the children of a node are traversed, it is popped out of the stack.

Key Takeaways

In this blog, we learned the algorithms based on the graph. We have learned Ford Fulkerson and Edmonds algorithm, Dinic’s algorithm, MPM algorithm, bipartite graph, Euler path, an Euler circuit.

Hence learning never stops, and there is a lot more to learn.