Представяне на графи

Графът може да бъде записан (представен) във външната памет (външно представяне) и във вътрешната памет (вътрешно представяне).

 Външно представяне – 2 подхода:

  • записва се номера на възела и след тире се изреждат неговите съседи;

Пример: 1 – 2 3; 2 – 1 3 4 5; 3 – 1 2 4 5; 4 – 2 3 5; 5 – 2 3 4

  • на всеки ред от файла се записват съседите на възела, чийто номер съответства на номера на реда.
Пример:2 3
1 3 4 5
1 2 4 5
2 3 5
2 3 4

Вътрешно представяне


Вътрешното представяне може да се извърши по два основни начина: чрез матрица на съседство и чрез списъци на съседство.

В компютърните реализации един граф се представя с множеството от върховете си V={1,2,…,n} и матрица на съседство a[i][j], в която a[i][j]=1, когато съществува дъга от връх i към връх j и a[i][j]=0 в противен случай. В графите, където са зададени тегла по ребрата, съответната стойност може да бъде записана като стойност a[i][j], при което този масив няма да съдържа само нули и единици. Алтернативен начин за представяне на граф е чрез използване на множествата s[j], съдържащи съседите за всеки връх j. Множеството s[j] съдържа номерата на всички върхове, които са непосредствено свързани с върха, номериран с j. В програмните реализации елементите на множеството s[j] обикновено се представят като елементи на двуиндексен масив s[j][1], s[j][2], …, s[j][s[j][0]],  където s[j][0] съдържа броя на съседите на върха с номер j.

Матрица на съседство

Един от най-често използваните начини за представяне на граф G(V,E) е посредством матрица на съседство. Нека V={1,2,…,n}. Матрицата на съседство за G(V,E) е n x n матрица A, където a[i][j]=1 ако има дъга от i до j и a[i][j]=0 в противен случай.

Предимството на представянето чрез матрица на съседство е, че се изисква постоянно време (само еднократен достъп до паметта) за определянето дали има или не дъга между два дадени върха. В случаите, когато с всяка дъга е свързана дължина или тегло, представянето с матрица на съседство може да се модифицира подходящо, така че a[i][j] да съдържа дължината или теглото вместо единица. Недостатък на представянето с матрица на съседство е, че използваната памет е n² клетки, даже и в случаите, когато графът има твърде малко ребра. Освен това, само еднократното преглеждане на елементите на матрицата изисква n² стъпки, което автоматично води до това, че използваните алгоритми ще бъдат квадратични, даже и за разредени графи.

Създава се матрица по редовете и колоните на която се поставят номерата на възлите. При битоничните матрици в местата на връзка се записва 1, а при тегловните матрици (за тегловен граф)- теглото на реброто.

  1 2 3 4 5 1 0 1 1 0 0 2 1 0 1 1 1 3 1 1 0 1 1 4 0 1 1 0 1 5 0 1 1 1 0

Ако в графа няма бримки, по главния диагонал трябва да има само нули. Ако графът е неориентиран, матрицата е симетрична спрямо главния диагонал.
За представянето на графа са необходими n² клетки в паметта – доста неикономично.

  1 2 3 4 5 6 1 1 1 0 0 1 0 2 1 0 1 0 1 0 3 0 1 0 1 0 0 4 0 0 1 0 1 1 5 1 1 0 1 0 0 6 0 0 0 1 0 0

Списъци на съседство

Алтернативно предствавяне на граф G(V,E) е посредством списъци на съседство. Казваме, че връх j е съседен на връх i, когато има дъга от i до j. За представянето на графа използваме масив от n елемента, в който i-тия елемент указва списъка от съседи (в произволен ред) на върха i. Следователно необходимата памет за представяне на граф с n върха и m ребра е  от порядъка на n+m. Така се избягва недостатъка от използването на повече памет, отколкото е необходима. Недостатък на представянето чрез списъци на съседство е, че определянето дали има ребро от i до j може да изисква до n стъпки, защото е свързано с последователно обхождане на списъка от съседи на връх i. За приложения, където тясното място е определянето дали има ребро между два върха, за предпочитане е използването на матрица на съседство.

1 –> {1, 2, 5} 2 –> {1, 3, 5} 3 –> {2, 4} 4 –> {3, 5, 6} 5 –> {1, 2, 4} 6 –> {4}

При списъците на съседство са възможни 3 подхода: статично(два масива), полудинамично (масив+списъци) и динамично (списъчни структури).

  • Статично представяне – използват се два масива: масив “съседи”, където последователно се изреждат номерата на съседите на всеки един възел в графа. Масив ”начало” – във всеки елемент се записва индекса, от който в масив “съседи” започва изреждането на съседите на възела, който има номер, равен на индекса на елемента в масив ”начало”.

  • Полудинамично – в масива “начало” се записва адресът на записа на първия съсед. Всеки запис на съсед притежава по две полета: номер на възела и указател към следващия съсед. Указателят за следващ съсед на последния от списъка е нула. 
  • Динамично – за всеки възел се създава запис с две полета:  номер на възела и указател към двойка указатели. Първият указател от двойката съдържа адреса на съсед, а втория- адреса на следващата двойка указатели.