Графік і яго прадстаўленне


Узровень складанасці серада
Часта пытаюцца ў Дэліверы Факты Infosys MAQ o9 рашэнні
Структура дадзеных Графік тэорыя

Графік гэта абстрактны тып дадзеных, які ўяўляе адносіны альбо сувязі паміж аб'ектамі (напрыклад, гарады злучаны няроўнай дарогай). У графіку і яго прадстаўленні ў асноўным адносіны абазначаюцца рэбрамі, а аб'екты - вяршынямі (вузламі). Графік складаецца з канчатковага набору вяршынь і рэбраў. Графік - гэта нелінейная структура дадзеных. Возьмем прыклад facebook, мы ўсе ведаем, што сябры знаходзяцца ў двухбаковых адносінах на Facebook, калі A з'яўляецца сябрам B, то B таксама з'яўляецца сябрам A. Група сяброў, у якіх кожны сябар з'яўляецца сябрам астатніх сяброў, з'яўляецца прыкладам ненакіраванага графіка.

 

Графік і яго прадстаўленне

                        Малюнак 1: Ненакіраваны графік складаецца з вяршынь = {1,2,3,4,5,6} і рэбраў = {12,14,23,35,45,56}
  • Вузлы / вяршыні:  Гэта як сутнасці, узаемасувязь якіх вызначаецца рэбрамі.
  • Краі: Гэта як кампаненты, якія прадстаўляюць сувязь паміж вузламі / вяршынямі.

Віды графікаў

  • Ненакіраваны графік: Гэта набор аб'ектаў (вузлоў / вяршынь), якія злучаны паміж сабой рэбрамі, якія маюць двухбаковы характар ​​(гл. Малюнак 1).
  • Накіраваны графік: Гэта набор аб'ектаў (вузлоў / вяршынь), якія злучаны паміж сабой рэбрамі, дзе ўсе краю накіраваны ад аднаго вузла да іншага (гл. Малюнак 2).
  • Узважаны графік: Гэта набор аб'ектаў (вузлоў / вяршыняў), якія злучаны паміж сабой рэбрамі, дзе кожны край графіка мае адпаведнае лікавае значэнне, якое называецца вагой (гл. Малюнак 3).

Графік і яго прадстаўленне                                                        Графік і яго прадстаўленне

             Малюнак 2: Накіраваны графік Малюнак 3: Узважаны графік

Рэалізацыя графіка

Існуюць розныя спосабы аптымальнага прадстаўлення графіка ў залежнасці ад шчыльнасці яго рэбраў і тыпу аперацый, якія мы хочам выканаць.

Матрыца сумежнасці

Гэта матрыца злучэння памерам V * V, дзе V - агульная колькасць вяршыняў, якая ўтрымлівае толькі 0,1. Дзе i суседнічае з j і 1 <= i, j <= V, тады яго значэнне роўна 1, інакш 0. Давайце паглядзім прыклад матрыцы сумежнасці:

Графік і яго прадстаўленне                   

Ненакіраваная матрыца сумежнасці графа Матрыца накіраванасці графа Ўзважаная матрыца сумежнасці графа

(Гл. Мал. 1) (гл. Мал. 2) (гл. Мал. 3)

Заўвага: Калі ў графіку няма самаканструкцыі, тады ўсе ячэйкі, дзе i = j, павінны быць 0 (гл. Матрыцы вышэй).

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

Спіс сумежнасці

Гэта звязанае ўяўленне, якое змяшчае N (усяго вузлоў) спісаў, у якіх кожны спіс апісвае набор суседзяў вяршыні ў графіку. Памер спісу (для любой вяршыні) роўны ступені гэтай вяршыні.

Накіраваны графік Спіс сумежнасці (гл. Мал. 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 */

Спасылка

Даведка1