Основно съдържание

Курс: Компютърни науки > Раздел 1

Урок 10: Представяне на граф

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

Има няколко начина за представяне на графи, всеки от които има предимства и недостатъци. Някои ситуации или алгоритми, които искаме да изпълним с входящи данни графи, се нуждаят от едно представяне, а други – от друго представяне. Тук ще видим три начина за представяне на графи.

Ще разгледаме три критерия. Единият е колко памет, или пространство, ни трябва за всяко представяне. Ще използваме асимптотична нотация. Да, ние можем да използваме асимптотична нотация за цели, различни от това да представим времето за изпълнение! Всъщност това е начин да се характеризират функции, а една функция може да опише времето за изпълнение като количеството необходимото пространство или друг ресурс. Другите два критерия, които ще използваме, са свързани с времето. Единият е колко време отнема да се определи дали дадено ребро е в графа. А другият е колко отнема намирането на съседите на даден връх.

Често върховете не се идентифицират по име (като "Одри," "Бостън," или "пуловер"), а с число. Т.е. обикновено номерираме

| V |

-те върхове от 0 до

| V | - 1

. Ето един граф за социална мрежа с 10 върха, идентифицирани с числа, вместо с имена:

Списък на ребрата

Един прост начин за представянена граф е списък или масив от

| E |

ребра, който наричаме списък на ребрата. За да представим едно ребро, ни трябва масив от две числа на върхове или масив от обекти, който да съдържа числата на върховете, които са свързани от реброто. Ако ребрата имат тежести, или добавяме към масива трети елемент, или даваме повече информация към обекта, която да даде на реброто тежест. Тъй като всяко ребро съдържа само две или три числа, общото пространство за един списък с ребра е

Θ (E)

. Например ето как представяме един списък от ребра в JavaScript за граф на социална мрежа:

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]

Списъците с ребра са прости, но ако искаме да разберем дали графът съдържа конкретно ребро, трябва да преминем през целия списък. Ако ребрата в списъка не са подредени, това означава линейно търсене през

| E |

ребра. Един въпрос, над който да помислиш: Как можеш да организираш списъка, за да може търсенето на конкретно ребро да отнема време

O (\lg E)

? Отговорът е малко сложен.

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

За граф с

| V |

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

| V | \cdot | V |

матрица от нули и единици, в която записът на ред

i

и колона

j

е 1, тогава и само тогава, когато реброто

(i, j)

се съдържа в графа. Ако искаш да покажеш тегло на реброто, постави го в записа на ред

i

, колона

j

и върни специална стойност (например null), която да показва липса на ребро. Ето една матрица на съседство за граф на социална мрежа:

В JavaScript представяме тази матрица така:

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

С матрица на съседство можем да разберем дали едно ребро е налице за едно и също време само като проверим съответния запис в матрицата. Например ако матрицата на съседство се нарича graph, можем да попитаме дали реброто

(i, j)

се съдържа в графа, като проверим graph[i][j]. Какви са недостатъците на матрицата на съседство? Всъщност това са две неща. Първото е, че отнема време

Θ (V^{2})

, дори ако графът е по-рядък: има относително малко ребра. С други думи, за по-рядък граф матрицата на съседство се състои основно от нули, а използваме много пространство, за да представим само няколко ребра. Второ, ако искаш да разбереш кои върхове са съседни на даден връх

i

, трябва да прегледаш всичките

| V |

записа в редица

i

дори и за малък брой върхове, които са съседни на връх

i

За неориентиран граф матрицата на съседство е симетрична: записът на редицата

i

и колоната

j

е 1 тогава и само тогава, когато записът на редица

j

и колона

i

е 1. За ориентиран граф матрицата на съседство не е нужно да е симетрична.

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

Представянето на граф със списъци на съседство комбинира матриците на съседство със списъците от ребра. За всеки връх

i

, запазваме масив с върховете, които са съседни на него. Обикновено имаме масив от

| V |

списъка на съседство – по един списък за връх. Ето едно представяне на граф на социална мрежа с помощта на списък на съседство:

В JavaScript представяме тези списъци на съседство така:

[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

Не е необходимо номерата на върховете в списъка на съседство да се появяват в определен ред, макар че е прието да ги подредим във възходящ ред, както е в този пример.

Можем да достигнем списъка на съседство на всеки връх за константно време, защото просто трябва да обходим масива. За да разберем дали върхът

(i, j)

е наличен в графа, отиваме в списъка на съседство на

i

за константно време и след това търсим

j

в списъка на съседство на

i

. Колко време отнема най-лошият случай? Отговорът е време

Θ (d)

, където

d

е степента на връх

i

, защото това е дължината на списъка на съседство на

i

. Степента на връх

i

може да достигне

| V | - 1

(ако

i

е съседен на всички останали

| V | - 1

въха) или да е най-малко 0 (ако

i

е изолиран и няма свързващи ребра). В неориентиран граф върхът

j

е в списъка на съседство на върха

i

тогава и само тогава, когато

i

е в списъка на съседство на

j

. Ако графът е претеглен, то всеки елемент в неговия списък на съседство има или масив от два елемента, или обект, който да дава номера на върха и теглото на реброто.

Можеш да използваш for цикъл, за да обходиш върховете в списъка на съседство. Например да предположим, че имаш представяне на граф със списък на съседство в променливата graph, така че graph[i] е масив, който съдържа съседите на върха

i

. Тогава, за да извикаш функцията doStuff върху всеки връх, съседен на върха

i

, можеш да използваш следния JavaScript код:

for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}

Ако нотацията с двоен индекс те обърква, можеш да помислиш по този начин:

var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}

Какво пространство заема един списък на съседство? Имаме

| V |

списъка и почти всеки от тях може да съдържа най-много

| V | - 1

върха, а общо списъците на съседство за неориентиран граф съдържат

2 | E |

елемента. Защо

2 | E |

? Всяко ребро

(i, j)

се появява точно два пъти в списъците на съседство – веднъж в списъка на съседство на

i

и веднъж в списъка на съседство на

j

и има

| E |

ребра. За ориентиран граф списъците на съседство съдържат общо

| E |

елемента, по един елемент за насочено ребро.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.