Сравнение алгоритмов Тарьяна и Косараджу

Опубликовано: 1 Декабря, 2021

Алгоритм Тарьяна в: Алгоритм Тарьян является эффективным алгоритмом графика , который используется , чтобы найти Сильно подсоединенный компонент (SCC) в ориентированном графе, используя только один обход DFS в линейной временной сложности.

За работой:

  • Выполните обход DFS по узлам, чтобы поддеревья сильно связанных компонентов удалялись при их обнаружении.
  • Затем присваиваются два значения:
    • Первое значение - это значение счетчика при первом исследовании узла.
    • Второе значение хранит самое низкое значение узла, доступное для начального узла, который не является частью другого SCC .
  • Когда узлы исследуются, они помещаются в стек.
  • Если остались какие-либо неисследованные дочерние элементы узла, они исследуются, и назначенное значение соответственно обновляется.

Ниже приведена программа для поиска SCC данного графа с использованием алгоритма Тарьяна:

C ++

// C++ program to find the SCC using
// Tarjan's algorithm (single DFS)
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
// A class that represents
// an directed graph
class Graph {
// No. of vertices
int V;
// A dynamic array of adjacency lists
list< int >* adj;
// A Recursive DFS based function
// used by SCC()
void SCCUtil( int u, int disc[],
int low[], stack< int >* st,
bool stackMember[]);
public :
// Member functions
Graph( int V);
void addEdge( int v, int w);
void SCC();
};
// Constructor
Graph::Graph( int V)
{
this ->V = V;
adj = new list< int >[V];
}
// Function to add an edge to the graph
void Graph::addEdge( int v, int w)
{
adj[v].push_back(w);
}
// Recursive function to finds the SCC
// using DFS traversal
void Graph::SCCUtil( int u, int disc[],
int low[], stack< int >* st,
bool stackMember[])
{
static time int = 0;
// Initialize discovery time
// and low value
disc[u] = low[u] = ++ time ;
st->push(u);
stackMember[u] = true ;
// Go through all vertices
// adjacent to this
list< int >::iterator i;
for (i = adj[u].begin();
i != adj[u].end(); ++i) {
// v is current adjacent of 'u'
int v = *i;
// If v is not visited yet,
// then recur for it
if (disc[v] == -1) {
SCCUtil(v, disc, low,
st, stackMember);
// Check if the subtree rooted
// with 'v' has connection to
// one of the ancestors of 'u'
low[u] = min(low[u], low[v]);
}
// Update low value of 'u' only of
// 'v' is still in stack
else if (stackMember[v] == true )
low[u] = min(low[u], disc[v]);
}
// head node found, pop the stack
// and print an SCC
// Store stack extracted vertices
int w = 0;
// If low[u] and disc[u]
if (low[u] == disc[u]) {
// Until stack st is empty
while (st->top() != u) {
w = ( int )st->top();
// Print the node
cout << w << " " ;
stackMember[w] = false ;
st->pop();
}
w = ( int )st->top();
cout << w << " " ;
stackMember[w] = false ;
st->pop();
}
}
// Function to find the SCC in the graph
void Graph::SCC()
{
// Stores the discovery times of
// the nodes
int * disc = new int [V];
// Stores the nodes with least
// discovery time
int * low = new int [V];
// Checks whether a node is in
// the stack or not
bool * stackMember = new bool [V];
// Stores all the connected ancestors
stack< int >* st = new stack< int >();
// Initialize disc and low,
// and stackMember arrays
for ( int i = 0; i < V; i++) {
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false ;
}
// Recursive helper function to
// find the SCC in DFS tree with
// vertex 'i'
for ( int i = 0; i < V; i++) {
// If current node is not
// yet visited
if (disc[i] == NIL) {
SCCUtil(i, disc, low,
st, stackMember);
}
}
}
// Driver Code
int main()
{
// Given a graph
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
// Function Call to find SCC using
// Tarjan's Algorithm
g1.SCC();
return 0;
}
Выход:
4
3
1 2 0

Алгоритм косарайя: Алгоритм Kosaraju является также Depth First Search алгоритм на основе, который используется для поиска SCC в ориентированном графе с линейной временной сложностью. Основная идея этого алгоритма заключается в том, что если мы можем достичь вершины v, начиная с вершины u , то мы должны достичь вершины u, начиная с вершины v , и если это так, мы можем сказать и заключить, что вершины u и v сильно связны и находятся в сильно связном подграфе.

За работой:

  • Выполните обход DFS на заданном графе, отслеживая время окончания каждого узла. Этот процесс можно выполнить с помощью стека.
  • Когда процедура выполнения обхода DFS по графу завершится, поместите исходную вершину в стек. Таким образом, узел с наибольшим временем завершения будет наверху стека.
  • Переверните исходный график, используя список смежности.
  • Затем выполните еще один обход DFS на обратном графе с исходной вершиной в качестве вершины на вершине стека. Когда DFS, работающая на перевернутом графе, завершает работу, все посещаемые узлы сформируют один сильно связанный компонент.
  • Если какие-либо еще узлы остаются или остаются непосещенными, это означает наличие более чем одной сильно связной компоненты на графе.
  • Поэтому выталкивайте вершины из вершины стека, пока не будет найден действительный непосещенный узел. Это будет самое большое время завершения из всех узлов, которые в настоящее время не посещаются.

Ниже приведена программа для поиска SCC данного графа с использованием алгоритма Косараджу:

C ++

// C++ program to print the SCC of the
// graph using Kosaraju's Algorithm
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
// No. of vertices
int V;
// An array of adjacency lists
list< int >* adj;
// Member Functions
void fillOrder( int v, bool visited[],
stack< int >& Stack);
void DFSUtil( int v, bool visited[]);
public :
Graph( int V);
void addEdge( int v, int w);
void printSCCs();
Graph getTranspose();
};
// Constructor of class
Graph::Graph( int V)
{
this ->V = V;
adj = new list< int >[V];
}
// Recursive function to print DFS
// starting from v
void Graph::DFSUtil( int v, bool visited[])
{
// Mark the current node as
// visited and print it
visited[v] = true ;
cout << v << " " ;
// Recur for all the vertices
// adjacent to this vertex
list< int >::iterator i;
// Traverse Adjacency List of node v
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// If child node *i is unvisited
if (!visited[*i])
DFSUtil(*i, visited);
}
}
// Function to get the transpose of
// the given graph
Graph Graph::getTranspose()
{
Graph g(V);
for ( int v = 0; v < V; v++) {
// Recur for all the vertices
// adjacent to this vertex
list< int >::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// Add to adjacency list
g.adj[*i].push_back(v);
}
}
// Return the reversed graph
return g;
}
// Function to add an Edge to the given
// graph
void Graph::addEdge( int v, int w)
{
// Add w to v's list
adj[v].push_back(w);
}
// Function that fills stack with vertices
// in increasing order of finishing times
void Graph::fillOrder( int v, bool visited[],
stack< int >& Stack)
{
// Mark the current node as
// visited and print it
visited[v] = true ;
// Recur for all the vertices
// adjacent to this vertex
list< int >::iterator i;
for (i = adj[v].begin();
i != adj[v].end(); ++i) {
// If child node *i is unvisited
if (!visited[*i]) {
fillOrder(*i, visited, Stack);
}
}
// All vertices reachable from v
// are processed by now, push v
Stack.push(v);
}
// Function that finds and prints all
// strongly connected components
void Graph::printSCCs()
{
stack< int > Stack;
// Mark all the vertices as
// not visited (For first DFS)
bool * visited = new bool [V];
for ( int i = 0; i < V; i++)
visited[i] = false ;
// Fill vertices in stack according
// to their finishing times
for ( int i = 0; i < V; i++)
if (visited[i] == false )
fillOrder(i, visited, Stack);
// Create a reversed graph
Graph gr = getTranspose();
// Mark all the vertices as not
// visited (For second DFS)
for ( int i = 0; i < V; i++)
visited[i] = false ;
// Now process all vertices in
// order defined by Stack
while (Stack.empty() == false ) {
// Pop a vertex from stack
int v = Stack.top();
Stack.pop();
// Print SCC of the popped vertex
if (visited[v] == false ) {
gr.DFSUtil(v, visited);
cout << endl;
}
}
}
// Driver Code
int main()
{
// Given Graph
Graph g(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
// Function Call to find the SCC
// using Kosaraju's Algorithm
g.printSCCs();
return 0;
}
Выход:
0 1 2 
3 
4

Сложность времени :
Временная сложность алгоритма Тарьяна и алгоритма Косараджу будет O (V + E) , где V представляет собой набор вершин, а E представляет собой набор ребер графа. Алгоритм Тарьяна имеет гораздо более низкие постоянные множители по сравнению с алгоритмом Косараджу. В алгоритме Косараджу обход графа выполняется как минимум 2 раза, поэтому постоянный множитель может иметь удвоенное время. Мы можем распечатать текущий SCC с помощью алгоритма Косараджу, когда мы выполняем вторую DFS. При выполнении алгоритма Тарьяна требуется дополнительное время для печати SCC после нахождения заголовка поддерева SCC.

Резюме :
Оба метода имеют одинаковую линейную временную сложность, но методы или процедура вычислений SCC существенно различаются. Метод Тарьяна зависит исключительно от записи узлов в DFS для разделения графа, тогда как метод Косараджу выполняет две DFS (или 3 DFS, если мы хотим оставить исходный граф без изменений) на графе и очень похож на метод поиска топологическая сортировка графа.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.