Güclü əlaqəli komponent

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Viza
Dərinlik İlk Axtarış QrafikBaxılıb 29

Güclü birləşdirilmiş komponentlər verilmiş əlaqəli komponentlərdir graph. SCC (güclü birləşdirilmiş komponent), hər bir düyünün cütünün bir-birindən başqa bir düyünə getmək üçün bir yola sahib olduğu birləşdirilmiş komponentlərdir. DGK müraciət etdi Rejissor Qrafiklər yalnız.

Bu, iki qovşaq arasındakı yolun yalnız sadə bir yol deyil yönləndirilmiş bir yoldur deməkdir. Nümunə ilə yönləndirilmiş qrafın SCC-sini başa düşək:

Güclü əlaqəli komponentPin

3 güclü əlaqəli komponent (1,2,3,4), (5,6,7), (8) var.

Qeyd: Bir qrafikin güclü birləşdirilmiş komponentini istifadə edərək tapa bilərik Kosarajunun alqoritm. Bu xətti bir zaman mürəkkəbliyi alqoritmidir.

Kosarajunun alqoritminin işlənməsi

Addım 1 Mənbə düyünündə DFS tətbiq edin və DFS həmin təpədə bitdikdə qovşaqları bir yığında saxlayın. Bunu izləyərək bir qrafikin zirvəsini topoloji çeşiddə saxlayırıq. Maksimum DFS bitmə müddəti olan vektoru ehtiva edən Yığın Üstü. Düyünləri bitmə vaxtının artan qaydasında saxlayırıq.

Addım 2 Verilən qrafiki geri qaytarmaq üçün hər kənarın istiqamətini dəyişdirin.

Addım 3 İndi DFS-i cari qrafikdə yenidən tətbiq edin ki, DFS-nin başladığı bir qaynaq olaraq həmişə yığının üst hissəsini seçək. DFS tamamlandıqda, SCC-nin yuxarı nöqtələri olduqları üçün ziyarət edilən bütün vertexi hazırkı DFS ilə çap edin. İndi yığını yuxarıdakı qovşaqdan çıxarın. Yığın yuxarı hissəsini mənbə kimi istifadə edərək bir qrafın bütün təpələrini ziyarət edənə qədər DFS tətbiq edin.

Güclü əlaqəli komponent üçün alqoritm

Step:1 Apply DFS(start) on the graph and store the finishing time of each node. 
       DFS(start): 
       i) visited[start]=true. 
       ii) for all neighbours u of start that are unvisited: DFS(u). 
       iii) stack.push(u). 
Step:2 Reverse the graph. 
       i) Clear the adjacency list. 
       ii) for all edges between u to v: adjacency_list[v].push_back(u). 
Step:3 Apply DFS from the vertex which is on the top of the stack. 
       While(!stack.empty()): 
       i) top=stack.top(). 
       ii) stack.pop(). 
           DFS(u). 
       iii) if the top is unvisited: 
            DFS(top). 
Step:4 When all nodes which are visited will form SCC. 
Step:5 Repeat till we get a vertex from the top of the stack which is unvisited.

Güclü əlaqəli komponent üçün tətbiqetmə

/*C++ Implementation for finding Strongly Connected Components of a graph.*/ 
#include<bits/stdc++.h>
using namespace std;
void finishing_time(int v, vector<int> graph[],int visited[],stack<int> &s)
{
    visited[v]=1;
    for(int i=0;i<graph[v].size();i++)
    {
        if(!visited[graph[v][i]])
        {
            finishing_time(graph[v][i],graph,visited,s);
        }
    }
    s.push(v);
}
void dfs(int source, vector<int> revrse_graph[],int visited[])
{
    visited[source]=1;
    cout<<source<<" ";
    for(int i=0;i<revrse_graph[source].size();i++)
    {
        if(!visited[revrse_graph[source][i]])
        {
            dfs(revrse_graph[source][i],revrse_graph,visited);
        }
    }
}
int main() 
{ 
    /*Input the number of nodes, edges*/
    int nodes,edges;
    cin>>nodes>>edges;
    vector<int> graph[nodes+1];
    /*reverse of graph*/
    vector<int> revrse_graph[nodes+1];
    /*make graph*/
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        /*its directed graph so we add only edge for x->y*/
        graph[x].push_back(y);
        revrse_graph[y].push_back(x);
    }
    int visited[nodes+1];
    /*set all nodes as unvisited(0)*/
    memset(visited,0,sizeof(visited));
    /*push the nodes in stack such that top of stack always more finishing time*/
    stack<int> s;
    /*push into stack*/
    for(int i=1;i<=nodes;i++)
    {
        if(!visited[i])
        {
            finishing_time(i,graph,visited,s);
        }
    }
    /*now, mark all the vertices as unvisited*/
    memset(visited,0,sizeof(visited));
    /*find the connected components*/
    cout<<"strongly connected components of given directed graphs are: "<<endl;
    while(s.size()>0)
    {
        /*pop the verte which is on the top of stack*/
        int top=s.top();
        s.pop();
        /*if top is unvisited then apply DFS start from source vertex(top as source vertex)*/
        if(!visited[top])
        {
            dfs(top,revrse_graph,visited);
            cout<<endl;
        }
    }
    return 0; 
}
8 9 
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
strongly connected components of given directed graphs are: 
1 4 3 2 
5 7 6 
8

Zamanın mürəkkəbliyi

O (N + E) burada N - qovşaqların sayı, E - kənarların sayı. Vasitə Kosarajunun alqoritm xətti bir zaman mürəkkəbliyi alqoritmidir. DFS-dən istifadə edərək, OC (N) olduğunu artıq bildiyimiz DFS-nin SCC və zaman mürəkkəbliyini tapırıq.

Kosmik Mürəkkəblik

O (N + E) burada N qovşaqların sayını, E isə kənarların sayını göstərir. Bitişiklər siyahısını istifadə edərək bir qrafik yaratdığımız zaman istifadə olunan zaman yaddaş sahəsi O (N + E) olur.

References

Translate »