İki tərəfli qrafik

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Samsung
Genişlik İlk Axtarış Dərinlik İlk Axtarış Qrafik Qrafik BoyamaBaxılıb 101

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

İki tərəfli qrafik bir növüdür graph bir qrafın təpələrini iki dəstə böldüyümüz. Eyni dəstin təpələri arasında kənar yoxdur. Burada bipartit_qrafda dövrlərin uzunluğu həmişə bərabərdir. Əsasən, qrafın təpələrini böldüyümüz təpə dəstlərinə qrafın hissəsi deyilir. İki tərəfli qrafın nümunəsinə baxaq.

İki tərəfli qrafikPin

Burada qovşaqları bipartite_graph xüsusiyyətini izləyən 2 dəstə bölə bilərik. Tutaq ki, 1,2,3,4 təpələri olan çoxluq X, 5,6,7,8 təpələri olan çoxluq Y qoyulur. Görürük ki, eyni dəstin təpələri arasında kənar yoxdur.

Qeyd: Tam iki tərəfli qrafik X dəstinin hər təpəsinin bir kənar vasitəsilə Y çoxluğunun hər bir təpəsinə qoşulduğu xüsusi bir bipartit_qraf növüdür.

İki tərəfli qrafın xüsusiyyətləri

  • Tək uzunluqlu dövrlər içermir.
  • İki rəng olmalıdır.
  • Verilən ikitərəfli_qrafın altqrafikləri də iki tərəfli_qrafdır.
  • Burada X çoxluğu zirvələrinin dərəcəsinin cəmi Y çoxluğunun təpələrinin cəminə bərabərdir.
  • Qrafın spektrinin simmetrik olduğunu yoxlamaq lazımdırsa, qrafiqin iki tərəfli olub olmadığını yoxlayırıq. İki tərəfli bir qraf deyilsə, qrafın spektrinin simmetrik olmadığını söyləyə bilərik.
  • N təpədən ibarət bipartit_qraf ən çox ola bilər (1/4) * N * N kənarları.

Qrafın iki tərəfli olub olmadığını yoxlamaq üçün əsasən iki yol vardır:

  • Istifadə BFS qrafiki ehtiva etdiyini yoxlamaq tək uzunluq dövrü ya yox. Tək uzunluqlu dövr tapılıbsa, deməli onun BG deyil.
  • Istifadə DFS qrafiki yoxlamaq 2 rənglidir ya yox. İki rənglidirsə, qrafikin iki tərəfli olduğunu deyirik.

Qrafın iki tərəfli olduğunu yoxlayın və ya BFS istifadə etmirsiniz

Alqoritm

Step:1 Make a graph using the adjacency list.
Step:2 For i in range 1 to N:
       a) If i is unvisited then:
             i) BFS(i).
             ii) If we found the odd-length cycle then we stop the process and print graph is not bipartite.

Qrafın iki tərəfli olduğunu yoxlayın və ya DFS istifadə etmirsiniz

Alqoritm

Step:1 Use color 0,1 to color the vertices.
Step:2 Call DFS(start).
Step:3 Assign the opposite color of the parent to the current node and call DFS to visit the neighbors of current node.
Step:4 If any step we find the color of two nodes connected by each other is same then we return false.
Step:5 If we visit all the nodes and don't find the color of two nodes connected by each other is same then we return true.

Həyata keçirilməsi

/*C++ Implementation for check a graph is bipartite or not.*/ 
#include<bits/stdc++.h>
using namespace std;
/*function to check for graph is bipartite or not.*/
int check_biaprtite(int node,vector<int> v[],bool visited[],int assign[])
{
    /*visited all connected nodes to node*/
    for(int itr: v[node])
    {
        /*if connected node is unvisited then check_biaprtite*/
        if(!visited[itr])
        {
            visited[itr]=true;
            assign[itr]=!assign[node];
            if(!check_biaprtite(itr,v,visited,assign))
            {
                return 0;
            }
        }
        /*if two adjacent node have the same color then return false*/
        else if(assign[itr]==assign[node])
        {
            return 0;
        }
    }
    /*else return true*/
    return 1;
}
int main() 
{ 
    int nodes,edges;
    /*take inputs the value of node and edges*/
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    /*create undirected graph*/
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        /*add edge between x -> y*/
        v[x].push_back(y);
        /*add edge between y -> x*/
        v[y].push_back(x);
    }
    bool visited[nodes+1];
    /*set all the nodes as unvisited*/
    memset(visited,false,sizeof(visited));
    int assign[nodes];
    int test;
    /*check for all the nodes in the graph*/
    for(int i=1;i<=nodes;i++)
    {
        /*if node is unvisited*/
        if(!visited[i])
        {
           visited[i]=true;
           assign[i]=0;
           /*check for this connected component*/
           test=check_biaprtite(i,v,visited,assign);
           /*if test is 1 then graph is not Bipartite*/
           if(test==1)
           {
               goto label;
           }
        }
    }
    label:;
    /*print the result*/
    if(test==1)
    {
        cout<<"Graph is Bipartite"<<endl;
    }
    else
    {
        cout<<"Graph is not Bipartite"<<endl;
    }
    return 0; 
}
8 6
1 6
6 3
3 8
5 2
2 7
7 4
Graph is Bipartite

Zamanın mürəkkəbliyi

O (N + E) burada N - qovşaqların sayı, E - kənarların sayı. Qrafik yaratarkən bütün proses üçün mümkün olan maksimum O (N + E) vaxtından istifadə edirik.

Kosmik Mürəkkəblik

O (N + E) burada N - qovşaqların sayı, E - kənarların sayı. Bitişiklər siyahısını yaratmaq üçün O (N + E) olan maksimum yerdən istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »