Сравнение алгоритмов Тарьяна и Косараджу
Алгоритм Тарьяна в: Алгоритм Тарьян является эффективным алгоритмом графика , который используется , чтобы найти Сильно подсоединенный компонент (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.