As software engineers, one of the most daunting part of our career is facing algorithm problems in a technical interview. Algorithms can range from simple, testing only basic knowledge of a programming language, to advanced. The topic of this blog post will be about Strongly Connected Components and Directed Graphs, something you may experience in a technical interview.
Directed Graphs
Simplified, a directed graph is a type of graph the utilizes vertexes connected by arrows, or edges. These edges can be referred to in two different ways, either indegree or outdegree. A vertex that has 1 indegree edge has an edge that points to that vertex. If it also has 1 outdegree edge, it has an edge pointing outward to another vertex. Here is a simple directed graph:
If you look at vertex 11, you'll see it is has several edges pointing to it, and several edges pointing to other vertexes. In total, there are 3 outdegree edges and 2 indegree edges for vertex 11. This is the basic structure of a directed graph.
Strongly Connected Components
So what are strongly connected components? Well, we've all seen a graph like this:
We have two separate components, both with a few individual nodes in each component. These components are not connected in any way, because there is not common node between the two components. As such, there is no way for any node in the left component to reach any node in the right component. But what happens if they do share a common node?
Now that they have a common node, any node within the left component can be reached from the right component, and vice versa. Here is another way to visualize this:
What previously was two separate components connected by a common vertex in a directed graph is now joined into one strongly connected component, and there is no need to visualize it as two separate components but rather one strongly connected component:
Kosaraju's Algorithm
To first understand Kosaraju's Algorithm, we'll need to understand further how strongly connected components exist in a directed graph. The following screen shots shows several vertexes. Can you identify which vertexes are strongly connected? How would you re-write this directed graph to represent the existence of strongly connected components? How many strongly connected components are there?
Take a moments and think about it!
Here's the solution:
The solution to the problem is 2 strongly connected components. But what if we have a directed graph like this:
It may be much harder to visualize the amount of strongly connected components in a directed graph in which each vertex has several indegree and outdegree edges. Luckily for us, this is where Kosaraju's Algorithm comes into play. The purpose of the algorithm is to find the amount of strongly connected components in a directed graph. Kosaraju's Algorithm is extremely complex, so here's a resource that implements it in a practical situation:
Conclusion
Hopefully this blog will serve you in some way when you begin interviewing for software engineering positions. You never know, you may come across a directed graph problem!
Top comments (1)
helpful!