Qrafik və onun təsviri

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çatdırılma Məlumat dəsti Infosys MAQ o9 həlləri
Məlumatların quruluşu Qrafik nəzəriyyəBaxılıb 62

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.

Bir qrafik obyektlər arasındakı münasibətləri və əlaqələri təmsil edən mücərrəd bir məlumat növüdür (şəhərlər kobud yolla birləşdirilmişdir kimi). Qrafikdə və onun təsvirində, əsasən, əlaqələr kənarlarla, cisimlər isə təpələr (düyünlər) ilə işarələnir. Qrafik sonlu bir təpə və kənardan ibarətdir. Qrafik xətti olmayan Məlumat Strukturudur. Nümunə götürək Facebook, hamımızın Facebook-da dostlarımızın iki yönlü əlaqədə olduğunu bilirik, əgər A B-nin dostudursa B o zaman B-nin də A-nın dostudur. Hər dostun qalan dostların dostu olduğu Qrup, Yönləndirilməmiş Qrafik nümunəsidir.

 

Qrafik və onun təsviriPin

                        Şəkil 1: İstiqamətləndirilməmiş bir qraflıq zirvələrdən = {1,2,3,4,5,6} və kənarlardan = {12,14,23,35,45,56} ibarətdir
  • Düyünlər / Vertices:  Münasibəti kənarları ilə təyin olunan varlıqlar kimidir.
  • Kənarları: Düyünlər / təpələr arasındakı əlaqəni təmsil edən komponentlər kimidir.

Qrafik növləri

  • İstiqamətsiz Qrafik: Təbiətdə iki istiqamətli kənarları ilə bir-birinə bağlanan bir sıra obyektlərdir (qovşaqlar / təpələr) (bax Şəkil 1).
  • İstiqamət Qrafı: Bütün kənarların bir qovşaqdan digərinə yönəldildiyi kənarlarla bir-birinə bağlanan bir sıra obyektlərdir (qovşaqlar / təpələr) (bax Şəkil 2).
  • Ağırlıqlı Qrafik: Qrafın hər kənarının çəki adlanan əlaqəli ədədi dəyərə sahib olduğu kənarları ilə bir-birinə bağlanan bir sıra obyektlərdir (qovşaqlar / təpələr) (bax Şəkil 3).

Qrafik və onun təsviriPin                                                        Qrafik və onun təsviriPin

             Şəkil 2: Yönləndirilmiş Qrafik Şəkil 3: Ağırlıqlı Qrafik

Qrafın tətbiqi

Bir qrafın kənarlarının sıxlığından və yerinə yetirmək istədiyimiz əməliyyatlar növündən asılı olaraq qrafiki optimal şəkildə təmsil etməyin müxtəlif yolları var.

Bitişiklik matrisi

V * yalnız V olan ümumi təpələrin sayı olduğu V * V ölçülü bir əlaqə matrisidir 0,1. Əgər i j və 1 <= i, j <= V-yə bitişikdirsə, onda dəyəri 1-dir, əks halda 0. Bitişiklik matrisinin bəzi nümunələrinə baxaq:

Qrafik və onun təsviriPin        Pin            Pin

Yönləndirilməmiş qrafik bitişiklik matrisi Direktivli qraflıq bitişiklik matrisi Çəkili qraflıq bitişiklik matrisi

(Bax Şəkil 1) (Bax Şəkil 2) (Bax Şəkil 3)

QEYD: Qrafikdə öz-özünə dönmə yoxdursa, i = j olduğu bütün hüceyrələr 0 olmalıdır (Yuxarıdakı matrislərə baxın).

/*C++ Implementation of adjacency matrix for undirected graph*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    int adj_matrix[nodes+1][nodes+1];
    memset(adj_matrix,0,sizeof(adj_matrix));
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        adj_matrix[x][y]=1;
        adj_matrix[y][x]=1;// for directed graph we don't write for y->x;
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        for(int j=1;j<=nodes;j++)
        {
            cout<<adj_matrix[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(N*N) WHERE N IS THE NUMBER OF NODES IN GRAPH */

Yaxınlıq siyahısı

Hər siyahının qrafadakı bir təpənin qonşularını təsvir etdiyi N (ümumi qovşaq) siyahıları olan əlaqəli bir nümayəndəlikdir. Siyahının ölçüsü (istənilən təpə üçün) bu təpənin dərəcəsinə bərabərdir.

İstiqamət qraflığı bitişiklər siyahısı (bax Şəkil 2)

/*C++ Implementation of adjacency list for directed graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y); /* add v[y].push_back(x) also for undirected graph beacuse edge is bidirectional in nature*/
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        int degree=v[i].size();
        for(int j=0;j<degree;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(V+E) WHERE V IS THE NUMBER OF VERTICES/NODES IN GRAPH AND E IS THE NUMBER OF EDGES */

arayış

İstinad1

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