Представљање графова у рачунару¶

Матрица повезаности (суседства)¶

Нека је \(V=\{v_1,v_2,\ldots,v_n\}\). Матрица повезаности тј. матрица суседства графа \(G = (V, E)\) је квадратна матрица \(A=(a_{ij})\) реда \(n\), са елементима \(a_{ij}\) који су једнаки 1 ако и само ако \((v_i,v_j)\in E\); остали елементи матрице \(A\) су једнаки 0. Уместо јединица и нула могу се користити логичке вредности тачно и нетачно. Врста \(i\) ове матрице је дакле низ дужине \(n\) чија је \(j\)-та координата једнака \(1\) (или \(\top\)) ако из чвора \(v_i\) постоји грана ка чвору \(v_j\), односно \(0\) (или \(\bot\)) у противном.

Размотримо представљање графа пријатељстава на једној друштвеној мрежи матрицом повезаности.

Праћења на мрежи Фејсбук¶

Ако претпоставимо да су чворови нумерисани на следећи начин: 0 - Пера, 1 - Мика, 2 - Ана, 3 - Јована, тада се граф пријатељства приказан на слици може представити матрицом

Ако је граф неусмерен (као у претходном примеру), матрица \(A\) је симетрична (око главне дијагонале) и у том случају је могуће памтити само једну њену половину (горњи или доњи троугао).

Матрицом се могу представљати и усмерени графови. Размотримо поново пример графа којим се представљају праћења на једној друштвеној мрежи.

Праћења на мрежи Инстаграм¶

Он се може представити наредном матрицом (која није симетрична):

Ако је \(n\) број чворова графа, и ако користимо логичке вредности, у језику C# можемо употребити следећу меморијску репрезентацију матрице повезаности (без озбира на то да ли је она симетрична или није).

Претпоставимо да се матрица учитава са стандардног улаза, тако што се прво учитава њена димензија, а затим и матрица задата нулама и јединицама раздвојеним по једним размаком. На пример,

4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Матрица се тада може учитати помоћу следеће функције.

Уместо задавања графа матрицом на улазу, граф се често задаје тако што се наведу његове гране. На пример, ако се претпостави да су чворови нумерисани бројевима од \(1\) до \(n\), тада се оријентисани граф праћења може представити на следећи начин (прво се задаје број чворова, затим број грана и на крају подаци о појединачним гранама).

4
7
1 2
1 3
2 4
3 1
3 4
4 0
4 2

Прикажимо сада функцију која на основу оваквог улаза у меморији креира матрицу повезаности усмереног графа.

Приметимо да смо због нумерације чворова која почиње од 1, а не од 0, учитане индексе чворова грана a и b умањивали за 1 пре приступа пољу матрице. У задацима се често среће и нумерација која креће од 0 и нумерација која креће од 1, па је потребно обратити пажњу на овај детаљ.

Ако се претпоставља да је граф неусмерен, тада за сваку учитану неусмерену грану два симетрично постављена елемента матрице треба поставити на вредност true (за сваку неусмерену грану додају се обе усмерене гране које јој одговарају).

Пример обраде графа представљеног матрицом повезаности¶

Претпоставимо да је (усмерени) граф праћења на једној друштвеној мрежи задат матрицом повезаности. Елемент \(a_{ij}\) има вредност тачно ако и само ако особа \(i\) прати особу \(j\). Дефинисати функцију које одређује листу редних бројева корисника са највише пратилаца, и функцију која одређује листу редних бројева корисника који прате највише других.

Да бисмо одредили кориснике који имају највише пратилаца, прво одређујемо број пратилаца сваког појединачног корисника (рачунамо излазне степене чворова). Те податке можемо да чувамо у једном низу. Све елементе низа иницијализујемо на нулу, затим угнежђеним петљама пролазимо кроз све елементе матрице суседства и за сваку везу од особе \(i\) до особе \(j\) увећавамо број пратилаца особе \(j\). Након одређивања броја пратилаца сваке особе одређујемо максимум тог низа тј. максималан број пратилаца неког корисника. На крају, одређујемо оне кориснике који имају тај максималан број пратилаца. Пошто њих може бити више, све их смештамо у листу коју враћамо као резултат функције.

static List<int> KorisniciSaNajvisePratilaca(bool[,] A, int n) { // odredjujemo broj pratilaca svakog korisnika int[] brojPratilaca = new int[n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (A[i, j]) brojPratilaca[j]++; // odredjujemo najveci broj pratilaca nekog korisnika int maks = brojPratilaca.Max(); // izdvajamo sve korisnike koji imaju taj maksimalni broj pratilaca var korisnici = new List<int>(); for (int i = 0; i < n; i++) if (brojPratilaca[i] == maks) korisnici.Add(i); return korisnici; }

Друга функција је веома слична првој. Једина разлика је што се за сваку особу не одређује број пратилаца, већ број корисника које она прати.

static List<int> KorisniciKojiNajvisePrate(bool[,] A, int n) { int[] brojPracenih = new int[n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (A[i, j]) brojPracenih[i]++; int maks = brojPracenih.Max(); var korisnici = new List<int>(); for (int i = 0; i < n; i++) if (brojPracenih[i] == maks) korisnici.Add(i); return korisnici; }

Нагласимо да се у овом задатку претпостављало да је граф већ представљен матрицом у меморији рачунара. Задаци који се своде на анализу степена чворова се често могу решити и без експлицитног представљања графа, јер се степени чворова могу израчунати током учитавања графа (приликом учитавања података о грани која спаја чворове \(a\) и \(b\) увећава се излазни степен чвора \(a\) и улазни степен чвора \(b\)).

Предстваљање тежинских графова матрицом тежина¶

Матрична репрезентација се веома често користи и за представљање тежинских графова тако што се на месту \((i, j)\) поставља вредност \(a_{ij}\) која представља тежину гране између чворова \(i\) и \(j\) (претпостављамо да су чворови нумерисани вредностима од \(0\) до \(n-1\)). Ако између два чвора не постоји грана у матрицу се описује нека специјална вредност која обично представља \(\infty\) (то може бити 0, -1, највећи број који се може представити помоћу одговарајућег целобројног типа ако су тежине целобројне или вредност \(+\infty\) ако се користи реални тип који обично има могућност експлицитног представљање те вредности).

Део мреже путева у Војводини¶

Претпоставимо да смо места у Војводини обележили редом бројевима 0 - Суботица, 1 - Сомбор, 2 - Бачка Топола, 3 - Кикинда, 4 - Оџаци, 5 - Врбас и 6 - Бечеј. Део мреже путева између ових градова се тада може представити следећом матрицом.

Пошто је граф неусмерен, матрица је симетрична.

Пример обраде графа представљеног матрицом тежина¶

Авиони лете између аеродрома и позната су времена летова између аеродрома. За сваки аеродром одредити време најкраћег лета до неког другог аеродрома (без преседања). Претпоставити да су времена летова задата матрицом неусмереног тежинског графа.

Илустрације ради, прикажимо прво део програма који учитава податке о летовима и формира матрицу тежинског графа. Претпоставићемо да се подаци учитавају у следећем формату:

5
4
0 1 1:25
0 2 2:13
1 4 3:17
2 4 2:53

Прво се учитава број аеродрома, затим број летова, а затим подаци о појединачним летовима: редни бројеви полазног и долазног аеродрома и време трајања лета. Претпоставићемо да се у матрицу уписује -1 за све аеродроме између којих не постоји лет. Једноставности ради уместо времена лета у сатима и минутима, у матрици ћемо памтити само времена летова у минутима. Дакле, од учитаних података треба формирати наредну матрицу:

\[\begin{split}\left( \begin{array}{ccccc} -1 & 85 & 133 & -1 & -1\\ 85 & -1 & -1 & -1 & 197\\ 133 & -1 & -1 & -1 & 173\\ -1 & -1 & -1 & -1 & -1\\ -1 & 197 & 173 & -1 & -1 \end{array} \right)\end{split}\]

static int[,] UcitajLetove() { int n = int.Parse(Console.ReadLine()); int[,] A = new int[n, n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) A[i, j] = -1; int m = int.Parse(Console.ReadLine()); for (int i = 0; i < m; i++) { string[] str = Console.ReadLine().Split(' ', ':'); int a = int.Parse(str[0]); int b = int.Parse(str[1]); int hh = int.Parse(str[2]); int mm = int.Parse(str[3]); int t = hh*60 + mm; A[a, b] = t; A[b, a] = t; } return A; }

Прикажимо сада функцију којом се за сваки аеродром одређује најкраћи лет. Ово се заснива на томе да се у свакој врсти матрице одреди најмања бројевна вредност која је различита од -1. Пошто је матрица симетрична, уместо врста је могуће обрађивати и колоне (али то је по правилу неефикасније).

static int[] NajkraciLetovi(int[,] A, int n) { int[] letovi = new int[n]; for (int i = 0; i < n; i++) { int mint = -1; for (int j = 0; j < n; j++) if (A[i, j] != -1) if (mint == -1 || A[i, j] < mint) mint = A[i, j]; letovi[i] = mint; } return letovi; }

Представљање графа помоћу листа суседа чворова¶

Уместо да се и све непостојеће гране експлицитно представљају у матрици повезаности, за сваку врсту \(i=1,2,\ldots,n\) може се формирати повезана листа оних позиција из \(i\)-те врсте на којима се налазе јединице. Дакле, сваком чвору придружује се листа (или низ), која садржи бројеве чворова који су суседни том чвору (односно гране ка суседним чворовима). Граф је представљен низом листа (тј. низова). Овај начин представљања графа зове се представљање помоћу листа суседа, односно листа повезаности.

На пример, усмерен граф приказан на слици се може представити следећим листама суседа.

Представљање усмереног графа листама суседа¶

Треба напоменути да иако име тако сугерише, имплементација овакве репрезентације графа не мора бити заснована на листама, већ се уместо повезаних листи може користити низ или нека врста балансираних бинарних дрвета или пак хеш табела (чиме се омогућава ефикасна претрага свих суседа).

У језику C# можемо употребити следећу имплементацију засновану на коришћењу проширивих низова (List<int>). Наредни кôд гради празне листе суседа.

Нову усмерену грану која спаја два чвора (cvorOd и cvorDo) тада можемо додати помоћу:

Ако је граф неусмерен, тада се за сваку неусмерену грану која спаја два чвора (cvorA и cvorB) додају два податка:

Итерацију кроз све суседе чвора можемо остварити помоћу:

Прикажимо сада функцију која на основу учитаног списка грана оријентисаног графа формира његову репрезентацију у облику листа суседа. Претпоставићемо да се прво учитава број чворова, затим број грана и након тога подаци о појединачним гранама. На пример:

4
7
1 2
1 3
2 4
3 1
3 4
4 0
4 2

Функција која учитава граф би се тада могла дефинисати на следећи начин:

Да је у питању неусмерен граф, за сваку грану (a,b) би требало додати елементе у две листе (чвор a у листу суседа чвора b и чвор b у листу суседа чвора a)

Репрезентација тежинског графа листама повезаности¶

И тежински графови могу бити ретки и тада их је боље представити листама повезаности него матрицом. У том случају листа повезаности сваког чвора садржи уређени пар који садржи индекс суседног чвора и тежину гране. На пример, граф путева између градова 0 - Суботица, 1 - Сомбор, 2 - Бачка Топола, 3 - Кикинда, 4 - Оџаци, 5 - Врбас и 6 - Бечеј би се могао представити листама на следећи начин.

Део мреже путева у Војводини¶

Листе повезаности тежинског графа¶

Прикажимо сада програм који учитава неусмерени тежински граф и формира овакву репрезентацију. Можемо претпоставити да је сваки уређени пар задат посебно дефинисаном структуром (а можемо употребити и тип Tuple). Претпоставићемо да је на улазу дат број чворова, број грана и зати подаци о појединачним гранама. На пример:

7
12
0 1 56.9
0 2 34.8
0 3 91.4
1 2 46.3
1 4 35.9
1 5 52.1
2 3 80.5
2 5 30.1
2 6 41.1
3 6 52.6
4 5 37.7
5 6 35.3

Имплицитна репрезентација¶

У неким примерима граф се не представља експлицитно, већ само имплицитно. Најчећши примери тог типа су матрице. Наиме, свако поље матрице се може представити неким чвором графа, док се гране графа успостављају измећу оних чворова који представљају суседна поља матрице (при чему свако унутрашње поље матрице може имати или четири суседа или осам суседа, у зависности од тога да ли су дозвољени дијагонални прелази). Уместо да се за сваки чвор експлицитно чувају листе суседа, те листе се не памте у меморији рачунара, а обилазак свих суседа се врши петљама које израчунавају координате суседних поља на основу познатих координата текућег поља.

Набрајање 8 суседних поља се врши на следећи начин.

for (int dv = -1; dv <= 1; dv++)
   for (int dk = -1; dk <= 1; dk++) {
       if (dv == 0 && dk == 0)
          continue;
       int vv = v + dv;
       int kk = k + dk;
       if (0 <= vv && vv < m && 0 <= kk && kk < n)
           // polje (vv, kk) je sused polju (v, k)
   }

Ако се матрицом представе поља шаховске табле по којој се креће скакач, тада се суседна поља могу обићи на следећи начин.

int[] dv = {-2, -2, -1, -1, +1, +1, +2, +2};
int[] dk = {-1, +1, -2, +2, -2, +2, -1, +1};
for (int i = 0; i < 8; i++)
{
       int vv = v + dv[i];
       int kk = k + dk[i];
       if (0 <= vv && vv < m && 0 <= kk && kk < n)
           // polje (vv, kk) je sused polju (v, k)
}