Ҷузъи бо ҳам алоқаманд


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Visa
Ҷустуҷӯи аввал Графикаи

Ҷузъҳои бо ҳам алоқаманд ҷузъҳои пайвастшудаи додашуда мебошанд граф. SCC (ҷузъи сахт пайвастшуда) он ҷузъҳои пайвастшуда мебошанд, ки дар онҳо ҳар як ҷуфт гиреҳ роҳи боздид аз як гиреҳи дигарро дорад. КДО муроҷиат кард Графикаи роҳнамо Танҳо.

Ин маънои онро дорад, ки роҳи байни ду гиреҳ роҳи роҳнамо на танҳо роҳи оддӣ мебошад. Биёед SCC-и графикаи равонашударо бо мисол фаҳмем:

Ҷузъи бо ҳам алоқаманд

3 ҷузъи бо ҳам сахт алоқаманд вуҷуд доранд (1,2,3,4), (5,6,7), (8).

Шарҳ: Мо метавонем ҷузъи бо ҳам пайвастаи графро бо истифода аз он пайдо кунем Косараҷу алгоритм. Ин алгоритми мураккабии хаттии вақт аст.

Коркарди алгоритми Косараҷу

Қадами: 1 DFS-ро дар гиреҳи манбаъ татбиқ кунед ва гиреҳҳоро дар стек нигоҳ доред, вақте ки DFS дар ин қулла ба итмом мерасад. Бо пайравӣ аз ин, мо қуллаи графро дар ҷобаҷогузории топологӣ нигоҳ медорем. Top Stack дорои вектори дорои мӯҳлати ниҳоии DFS мебошад. Мо гиреҳҳоро бо тартиби афзояндаи мӯҳлати нигаҳдорӣ нигоҳ медорем.

Қадами: 2 Барои бозгашти графики додашуда самти ҳар канораро тағир диҳед.

Қадами: 3 Ҳоло, DFS-ро дубора дар графикаи ҷорӣ татбиқ кунед, то ки мо ҳамеша болои стелларо ҳамчун манбаъе интихоб кунем, ки DFS-и мо аз он оғоз меёбад. Пас аз ба итмом расонидани DFS, пас ҳамаи вертикси ташрифшударо бо DFS-и ҳозира чоп кунед, зеро онҳо қуллаҳои SCC мебошанд. Акнун, гиреҳро аз болои анбора хориҷ кунед. То он даме ки тамоми қуллаҳои графро истифода барем, бо истифода аз болои стек ҳамчун манбаъ DFS -ро истифода баред.

Алгоритм барои ҷузъи ба ҳам васлшуда

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.

Амалисозӣ барои ҷузъи ба ҳам пайвастшуда

/*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

Мураккабии вақт

O (N + E) ки дар он N шумораи гиреҳҳо ва E шумораи канорҳо мебошанд. Воситаҳо Косараҷу алгоритм як алгоритми мураккабии хаттии вақт аст. Бо истифодаи DFS, мо SCC ва мураккабии вақти DFS-ро пайдо мекунем, ки мо аллакай медонем, ки O (N) аст.

Мураккабии фазо

O (N + E) ки дар он N шумораи гиреҳҳо ва E шумораи канорҳо ишора карда мешавад. Ҳангоме ки мо графикро бо истифода аз рӯйхати ҳамсоягӣ месозем, он гоҳ ин фазои хотираи вақт истифодашуда O (N + E) мебошад.

Адабиёт