Types of Graphs
Two different graph types exist. As follows:
- Directed Graph
- Undirected Graph
Directed Graph
A directed graph, also known as a digraph, consists of a set of vertices and a group of directed edges, each of which links a pair of ordered vertices. A directed edge is one that originates at the first vertex of the pair and terminates at the second vertex.
Undirected Graph
An undirected graph is a collection of linked nodes with only bidirectional edges. An undirected network is another name for an undirected graph. Edges in an undirected graph do not have a clear direction. Thus, it is known as an undirected graph.
Note
If every vertex in a graph can be reached from every other vertex, the graph is said to be strongly connected. An arbitrary directed graph is divided into strongly connected subgraphs by its strongly connected components.
If there is a path connecting each pair of the graph's vertices in each direction, a directed graph is said to be strongly connected. The first vertex in the pair has a path leading to the second, and the second vertex has a path leading to the first.
You can also read Detect cycle in an undirected graph here.
Kosaraju's DFS
The depth-first search algorithm is the foundation of Kosaraju's method, which was twice implemented.
The straightforward approach by Kosaraju algorithm that performs two DFS traversals of the graph is as follows:
- Set each vertex's initial state to unvisited.
- Perform a DFS traversal of the graph beginning at any vertex v. Return false if the DFS traversal doesn't reach every vertex.
- Invert each arc (or find transpose or reverse of the graph)
- Mark each vertex in the reversible graph as unvisited.
- Beginning with the same vertex v, do a DFS traversal of the inverted graph. Return false if DFS traversal doesn't reach every vertex. If not, return true.
Now, let's check whether this graph is strongly connected or not;
Implementation
In CPP
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int search, destination ;
};
class Graph
{
Public:
vector<vector<int>> adjList;
Graph(vector<Edge> const &edges, int n)
{
adjList.resize(n);
for (auto &edge: edges) {
adjList[edge.search].push_back(edge.destination );
}
}
};
void DFS(Graph const &graph, int v, vector<bool> &visited)
{
visited[v] = true;
for (int u: graph.adjList[v])
{
if (!visited[u]) {
DFS(graph, u, visited);
}
}
}
bool isStronglyConnected(Graph const &graph, int n)
{
for (int i = 0; i < n; i++)
{
vector<bool> visited(n);
DFS(graph, i, visited);
if (find(visited.begin(), visited.end(), false) != visited.end()) {
return false;
}
}
return true;
}
int main()
{
vector<Edge> edges = {
{0, 4}, {1, 0}, {1, 2}, {2, 1}, {2, 4},
{3, 1}, {3, 2}, {4, 3}
};
int n = 5;
Graph graph(edges, n);
if (isStronglyConnected(graph, n)) {
cout << "This graph is strongly connected";
}
else {
cout << "This graph is not strongly connected";
}
return 0;
}
Output:
This graph is strongly connected
Time Complexity: If the graph is represented using an adjacency list, the above approach has the same time complexity as Depth First Search, which is O(V+E).
In Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class edge
{
int source, destination ;
public edge(int source, int destination )
{
this.source = source;
this.destination = destination ;
}
}
class Graph
{
List<List<Integer>> adjList = null;
Graph(List<Edge> edges, int n)
{
adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (Edge edge: edges)
{
int search = edge.source;
int destination = edge.destination ;
adjList.get(search).add(destination );
}
}
}
class Main
{
private static void DFS(Graph graph, int v, boolean[] visited)
{
visited[v] = true;
for (int u: graph.adjList.get(v))
{
if (!visited[u]) {
DFS(graph, u, visited);
}
}
}
public static boolean isStronglyConnected(Graph graph, int n)
{
for (int i = 0; i < n; i++)
{
boolean[] visited = new boolean[n];
DFS(graph, i, visited);
for (boolean b: visited)
{
if (!b) {
return false;
}
}
}
return true;
}
public static void main(String[] args)
{
List<Edge> edges = Arrays.asList(
new Edge(0, 4), new Edge(1, 0), new Edge(1, 2), new Edge(2, 1),
new Edge(2, 4), new Edge(3, 1), new Edge(3, 2), new Edge(4, 3)
);
int n = 5;
Graph graph = new Graph(edges, n);
if (isStronglyConnected(graph, n)) {
System.out.println("This graph is strongly connected");
}
else {
System.out.println("This graph is not strongly connected");
}
}
}
Output:
This graph is strongly connected
Time Complexity: The above method has the same time complexity as that of Kosaraju algorithm Depth First Search, which is O(V+E) only if the graph is represented using an adjacency list.
Frequently Asked Questions
What is the Brute Force Method?
Brute force algorithms are exactly what they resemble- simple solutions to problems that rely on computer power alone and exhaust all possibilities rather than using cutting-edge approaches to increase efficiency.
What are the different types of Graphs?
There are two different types of graphs: Directed and Undirected graphs.
What are directed graphs?
A directed graph mainly consists of a set of vertices and a group of directed edges, each of which links a pair of ordered vertices.
What are undirected graphs?
An undirected graph is a collection of linked nodes with only bidirectional edges. An undirected network is another name for an undirected graph.
What is Kosaraju's algorithm?
The Kosaraju-Sharir method, also known as Kosaraju's algorithm, is a linear time approach for determining the strongly connected components of a directed graph.
Conclusion
In this article, we learned about Kosaraju's Algorithm and dry run with various examples to have a clear idea.
After reading about Kosaraju's Algorithm, are you not feeling excited to read/explore more articles on the topic of Ruby? Don't worry; Coding Ninjas has you covered. To learn, see Multithreading in Python, Descriptors in Python, and BorderLayout in Java.
Recommended Problem - K Closest Points To Origin
Refer to our Guided Path on Code studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more!
Do upvote our blogs if you find them helpful and engaging!
305+ registered