The Tarjan algorithm, a fundamental technique for many important graph algorithms, is employed to identify the strongly connected components (SCCs) within directed graphs. These SCCs serve as fundamental elements of a graph where every vertex within the component is reachable from any other vertex. Essentially, these connections form cycles, ensuring that there is always a path from any vertex to another, eventually circling back to a previously visited node.
The DFS (Depth-First Search) strategy proves to be extremely efficient for its ability to deliver outstanding results when applied to graphs. When employing the DFS search technique, significant effort is allocated to delving deeply into vertices. Under the permissive policy framework, each vertex is uniquely numbered in sequence. The inability to traverse the complete graph structure is a result of a missing "address," yet DFS can circumvent this obstacle by utilizing a stack.
This method leads to optimal resource utilization and is beneficial for traversing graphs, finding paths, and analyzing networks. Therefore, this technique is crucial and can be applied in various scenarios requiring efficient exploration of graph data structures.
This process involves maintaining the timestamp for each vertex in a dynamic manner and identifying the minimum reachable vertex by traversing both directed and reverse edges in the graph. This approach enables Tarjan's algorithm to distinguish the strongly connected components (SCCs) within the graph. The method involves comparing a vertex's lowest ancestor with its own discovery time during traversal, aiming to identify a new vertex. Subsequently, it includes removing multiple vertices from the stack until reaching the current one.
Approach-1: Using Adjacency List Representation
The adjacency list representation is widely favored for storing graphs in data structures. In C++ code, the edge list is stored as an array or vector. Each element in the array corresponds to a vertex in the graph, and is a list containing adjacent vertices. This list effectively demonstrates the connections between the vertices, facilitating simple traversal and manipulation, which are crucial functionalities.
The edge list format proves to be highly beneficial in algorithms like Tarjan's algorithm, specifically designed for identifying strongly connected components (SCCs) within a graph. This representation simplifies accessing a vertex's neighbors and executing graph-related tasks, enhancing the efficiency of algorithms reliant on graph topology and relationships. Ultimately, the versatility and effectiveness of the adjacency list format empower efficient graph storage and manipulation in C++ programming.
Program:
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
int V; // Number of vertices
// Adjacency list representation of the graph
vector<vector<int>> adj;
// Function to perform Depth First Search
void DFS(int u, vector<int>& disc, vector<int>& low, stack<int>& st, vector<bool>& stackMember, vector<vector<int>>& SCCs);
public:
Graph(int V); // Constructor
// Function to add an edge to the graph
void addEdge(int v, int w);
// Function to find strongly connected components
vector<vector<int>> findSCCs();
};
Graph::Graph(int V) {
this->V = V;
adj.resize(V);
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFS(int u, vector<int>& disc, vector<int>& low, stack<int>& st, vector<bool>& stackMember, vector<vector<int>>& SCCs) {
static int time = 0;
disc[u] = low[u] = ++time;
st.push(u);
stackMember[u] = true;
for (int v : adj[u]) {
if (disc[v] == -1) {
DFS(v, disc, low, st, stackMember, SCCs);
low[u] = min(low[u], low[v]);
} else if (stackMember[v]) {
low[u] = min(low[u], disc[v]);
}
}
int w = 0;
vector<int> component;
if (low[u] == disc[u]) {
while (st.top() != u) {
w = st.top();
component.push_back(w);
stackMember[w] = false;
st.pop();
}
w = st.top();
component.push_back(w);
stackMember[w] = false;
st.pop();
SCCs.push_back(component);
}
}
vector<vector<int>> Graph::findSCCs() {
vector<int> disc(V, -1), low(V, -1);
vector<bool> stackMember(V, false);
stack<int> st;
vector<vector<int>> SCCs;
for (int i = 0; i < V; i++) {
if (disc[i] == -1)
DFS(i, disc, low, st, stackMember, SCCs);
}
return SCCs;
}
int main() {
int V = 5; // Number of vertices
Graph g(V);
// Adding edges to the graph
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(1, 3);
g.addEdge(3, 4);
// Finding strongly connected components
vector<vector<int>> SCCs = g.findSCCs();
// Printing strongly connected components
cout << "Strongly Connected Components:\n";
for (vector<int>& component : SCCs) {
for (int v : component)
cout << v << " ";
cout << "\n";
}
return 0;
}
Output:
Strongly Connected Components:
4
3
2 1 0
Explanation:
- Graph Class: The Graph class implements the directed graph making use of adjacency list representation. It has member variables to keep the number of vertices and the adjacency list (adj) which is a vector of vectors. Every vector in inner space is the adjacency list of a vertex. Constructor initializes the number of vertices and resizes the adjacency list to accommodate this number.
- Adding Edges: The addEdge function is being used in this way to establish links between the nodes of the graph. It takes two parameters: e, which joins vertex v to vertex w, is the edge. The addition of a new in-edge w to the adjacency list of v, means a directed link from v to w.
- Depth First Search (DFS): The Depth-First Search (DFS) algorithm traverses a graph linearly from a starting vertex u, maintaining discovery time (disc) and lowest ancestor (low) during edge labeling. It utilizes a stack (st) to track exploration momentum and a stackMember vector to identify vertices currently in the stack. DFS explores as deeply as possible along each branch before backtracking, effectively traversing the graph in a depth-first manner. By systematically visiting vertices and marking their discovery and lowest ancestor times, DFS aids in tasks such as cycle detection, topological sorting, and finding strongly connected components in a graph.
- Finding Strongly Connected Components: As the findSCCs method enters, it initializes the disc and low arrays to calculate vertex discovery time, lowest ancestor, and stackMember status of its vertex. It scans all vertexes in the graph and puts them into n-dim array called disc, whose current index is not visited (disc[i] == -1). During DFS we should be looking for the node u for which the lowest value of the ancestor is equal to its own discovery time (low[u] == disc[u]) which will indicate the beginning of strongly connected components. The pairs of vertices from the queue are then fed into the stack and when the stack becomes empty it the vertex u is reached, resulting in forming one strongly connected component. Following that, it is merged with the vector of all SCCs.
- Main Function: The main function starts by creating an empty directed Graph object and add vertices(V) and edges with Graph class. Edges are obtained in this graph via the addEdge method where the algorithm adds these connections between different vertices. Then, the strongly connected components (SCCs) findSCCs method is used to check for the existence of the strongly connected components. These SCCs, as solid units, contain the all vertex subsets which cover each vertex from every other vertex.
The structural groupings have been identified and subsequently displayed to narrate the interconnected network depicted by the entire graph. This aids in the comprehensive examination and comprehension of the graph, elucidating the connections among its components.
Complexity Analysis:
Time Complexity:
The algorithm operates with a time complexity of O(V+E), with V representing the vertices and E representing the edges within the graph. During the DFS traversal, a fundamental aspect of the algorithm, every vertex and edge are visited a maximum of one time, resulting in a time complexity of O(V+E). Furthermore, the identification of strongly connected components involves traversing the vertices and edges of the graph once more, adding an extra O(V + E) to the total time complexity.
The close connection between edges and vertices indicates that the algorithm is effective in processing extensive graphs, rendering it well-suited for such tasks. By leveraging the graph's structure and characteristics, Tarjan's algorithm excels at pinpointing strongly connected components, which play a crucial role in in-depth graph analysis.
Space Complexity:
The space efficiency of this algorithm is predominantly determined by the data structures employed to depict the graph and store the temporary elements needed for the DFS traversal.
The space complexity of representing an adjacency list is O(V + E), where V represents the vertices and E represents the directed arcs. This complexity is due to counting both edges separately in the case of undirected graphs. This is why each vertex maintains a list of adjacent vertices.
During DFS traversal, we maintain global vectors to store information such as discovery times, lowest ancestor values, stack membership status, and the stack's elements. This collection of tools collectively creates a data structure with a total complexity of O(V).
Thus, the space complexity of this algorithm is denoted by O(V + E), primarily influenced by the way the graph is represented using an adjacency list.
Approach-2: Using Hashmaps
Tarjan's algorithm is a versatile method for uniformly identifying all the strongly connected components (SCCs) within a directed graph. This algorithm leverages various data structures such as hash maps and hash sets to enhance its efficiency. These structures aid in swiftly handling and organizing topological details related to the graph's vertices and edges. Ultimately, this streamlined process facilitates the rapid detection of SCCs within the graph.
Through skillful utilization of these data structures to navigate the graph effectively using this algorithm; it accomplishes the precise grouping and organization of the interconnected elements of the graph without incurring significant computational overhead. This capability demonstrates the algorithm's versatility in handling diverse graph structures and sizes, consistently delivering exceptional performance.
Program:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <algorithm>
using namespace std;
class Graph {
int V; // Number of vertices
// Adjacency list representation of the graph
unordered_map<int, vector<int>> adj;
// Function to perform Depth First Search
void DFS(int u, unordered_map<int, int>& disc, unordered_map<int, int>& low, stack<int>& st, unordered_set<int>& inStack, vector<vector<int>>& SCCs);
public:
Graph(int V); // Constructor
// Function to add an edge to the graph
void addEdge(int v, int w);
// Function to find strongly connected components
vector<vector<int>> findSCCs();
};
Graph::Graph(int V) {
this->V = V;
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFS(int u, unordered_map<int, int>& disc, unordered_map<int, int>& low, stack<int>& st, unordered_set<int>& inStack, vector<vector<int>>& SCCs) {
static int time = 0;
// Assign discovery time and lowest ancestor values to the current vertex
disc[u] = low[u] = ++time;
// Push the current vertex onto the stack and mark it as a member of the stack
st.push(u);
inStack.insert(u);
// Traverse all adjacent vertices of the current vertex
for (int v : adj[u]) {
// If the adjacent vertex is not visited, perform DFS on it
if (disc.find(v) == disc.end()) {
DFS(v, disc, low, st, inStack, SCCs);
low[u] = min(low[u], low[v]);
}
// If the adjacent vertex is already in the stack, update the lowest ancestor value
else if (inStack.find(v) != inStack.end()) {
low[u] = min(low[u], disc[v]);
}
}
// If the current vertex is the root of a strongly connected component
if (low[u] == disc[u]) {
vector<int> component;
int w;
// Pop vertices from the stack until the current vertex is reached
do {
w = st.top();
component.push_back(w);
inStack.erase(w);
st.pop();
} while (w != u);
// Add the strongly connected component to the list of SCCs
SCCs.push_back(component);
}
}
vector<vector<int>> Graph::findSCCs() {
unordered_map<int, int> disc, low;
stack<int> st;
unordered_set<int> inStack;
vector<vector<int>> SCCs;
// Perform DFS on each vertex that has not been visited
for (auto& vertex : adj) {
int u = vertex.first;
if (disc.find(u) == disc.end())
DFS(u, disc, low, st, inStack, SCCs);
}
return SCCs;
}
int main() {
// Create a graph with 5 vertices
Graph g(5);
// Add edges to the graph
g.addEdge(5, 1);
g.addEdge(1, 7);
g.addEdge(7, 5);
g.addEdge(7, 9);
g.addEdge(9, 8);
// Find strongly connected components
vector<vector<int>> SCCs = g.findSCCs();
// Print strongly connected components
cout << "Strongly Connected Components:\n";
for (vector<int>& component : SCCs) {
for (int v : component)
cout << v << " ";
cout << "\n";
}
return 0;
}
Output:
Strongly Connected Components:
8
9
1 5 7
Explanation:
Graph Class:
The orientation attribute and the neighbor list of nodes are employed to represent the Graph category. The constructor sets up V (vertices), whereas the functions aid in recognizing strongly linked sections. By utilizing addEdge, the connections among vertices are formed to enhance the graph's connectivity.
The occurrences are in opposition to the findSCCs function, which depends on Tarjan's algorithm to identify interconnected components linked to cohesive subsets of vertices. This representation signifies distinct vertices within a graph, enabling precise handling of the vertex collection and facilitating the application of various graph theory algorithms.
DFS Function:
The DFS function executes a depth-first search algorithm to traverse the nodes of the graph in order to identify the super components.
The process of searching for a graph starts with the initial vertex u and monitors the count of visited vertices. During the ongoing Depth First Search (DFS) exploration, it employs a stack (st) to preserve the order of traversal. Additionally, it utilizes a vector of vectors (SCCs) to hold the detected strongly connected components. The algorithm also employs a data structure to map the lowest ancestor (low) of each vertex and calculate the time taken to transition from one vertex to another.
During the execution of a depth first search traversal, it calculates the discovery times and lowest ancestors for every vertex. Simultaneously, it maintains a record of vertices that are part of the ongoing DFS path by saving them in both a stack and a set data structure. The identification of Strongly Connected Components (SCCs) is accomplished by comparing the lowest ancestor value of a vertex with its discovery time. If these values differ, the algorithm proceeds to extract and return the popped vertices from the stack, leading to the creation of an SCC.
FindSCCs Function:
In the Graph class, the findSCCs method acts as a conductor orchestrating the efficient discovery of strongly connected components (SCCs) using a Depth-First Search (DFS) traversal. It initializes essential data structures like discovery time, lowest ancestor, a stack, and a depot to store vertices in the current traversal path. By iterating through all vertices, the function invokes DFS for unvisited nodes to explore the graph's adjacency.
While traversing the graph during execution, the algorithm performs the crucial tasks of updating discovery times and determining the lowest ancestors, which are vital for identifying the Strongly Connected Components (SCCs). Upon detection of SCCs, they are gathered and stored in a vector for later analysis. The complete Depth-First Search (DFS) procedure is employed to explore the entire graph comprehensively. Subsequently, executing the SCCs function reveals significant insights into the structural layout and relationships within the graph.
Main Function:
The primary function is established with the Graph object that defines the edges of the graph. Initially, individual nodes are instantiated and included in the graph through the addVertex function. Subsequently, connections between nodes are established by adding lines to the graph using the addEdge function. Next, the findSCCs function is invoked to identify the strongly connected components within the graph. Within this process, Tarjan's algorithm is employed to navigate through the graph.
By performing this action, groups of the nodes can be recognized, leading to the formation of SCCs based on their interconnections. Finally, displaying the identified SCCs in the console, the console will illustrate the structural layout of the graph. Consequently, this procedure allows us to observe and analyze portions of graphs with comparable characteristic traits related to the arrangement of nodes; beneficial for tasks such as network analysis, route planning, and categorizing groups.
Complexity Analysis:
Time Complexity:
The main factor affecting time complexity stems from the depth-first search (DFS) traversal carried out on the graph. Since the algorithm visits each node and edge exactly once, the time complexity is primarily determined by V and E, representing the total number of vertices and edges in the graph.
In the most unfavorable situation, the graph exhibits dense connectivity where every node is accessible from any other node, resulting in a time complexity of O(V + E) for DFS traversal. This is attributed to the fact that each vertex and edge are visited exactly once during the traversal process.
Furthermore, the identification process of strongly connected components (SCCs) during Depth First Search (DFS) traversal entails tasks such as setting discovery time and lowest ancestor value, as well as verifying specific criteria for SCC recognition. Apart from these computational tasks, the DFS traversal itself contributes significantly to the overall complexity of the process.
In summary, the overall complexity of this algorithm amounts to O(V + E), with V representing the total vertices and E denoting the total edges within the graph.
Space Complexity:
The space efficiency of the algorithm focuses mainly on additional data structures necessary for storing data while conducting DFS traversal and identifying the strongly connected components within the graphs.
The storage efficiency for displaying the graph in adjacency list form is O(V + E), with V representing the vertex count and E indicating the edge count.
The depth-first search (DFS) algorithm necessitates extra memory allocation for storing information like the time of discovery, the lowest ancestor, a history stack, and a set of visited vertices in the current path. The space complexity of these data structures is O(V).
Storing the identified SCC graphs requires space that depends on both the count of SCCs and the vertices within each SCC. In a scenario where every vertex is a sink and a vertex on its own, the maximum space required is V. Nonetheless, typically the number of SCCs is significantly less compared to the total vertices in the shared graph.
Therefore, the ultimate space complexity of the algorithm is O(V + E), where the primary space requirement comes from storing the graph structure and the various data structures essential for executing the Depth-First Search traversal.
