Графична структура на данните

Съдържание

Графична терминология
Графично представяне
Графични операции

В този урок ще научите какво представлява структурата на графичните данни. Също така ще намерите изображения на графика.

Структурата на графичните данни е колекция от възли, които имат данни и са свързани с други възли.

Нека се опитаме да разберем това чрез пример. Във facebook всичко е възел. Това включва потребител, снимка, албум, събитие, група, страница, коментар, история, видео, връзка, бележка … всичко, което има данни, е възел.

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

Пример за структура на графични данни

Тогава целият facebook е колекция от тези възли и ръбове. Това е така, защото facebook използва графична структура от данни, за да съхранява данните си.

По-точно, графика е структура от данни (V, E), която се състои от

Колекция от върхове V
Колекция от ребра E, представени като подредени двойки върхове (u, v)

Върхове и ръбове

В графиката,

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Графична терминология

Съседство : Казва се, че връхът е съседен на друг връх, ако има ръб, свързващ ги. Върховете 2 и 3 не са съседни, защото между тях няма ръб.
Път : Последователност от ръбове, която ви позволява да преминете от връх А към връх В, се нарича път. 0-1, 1-2 и 0-2 са пътища от връх 0 до връх 2.
Насочена графика : Графика, в която ръб (u, v) не означава непременно, че има и ръб (v, u). Ръбовете в такава графика са представени със стрелки, които показват посоката на ръба.

Графично представяне

Графиките обикновено се представят по два начина:

1. Матрица за съседство

Матрицата за съседство е 2D масив от V x V върхове. Всеки ред и колона представляват връх.

Ако стойността на който и да е елемент a(i)(j)е 1, това означава, че има ръб, свързващ връх i и връх j.

Матрицата на съседство за графиката, която създадохме по-горе, е

Графична матрица за съседство

Тъй като това е ненасочена графика, за ръб (0,2) също трябва да маркираме ръб (2,0); правейки матрицата на съседство симетрична спрямо диагонала.

Търсене на ръбове (проверка дали съществува ръб между връх A и връх B) е изключително бърз при представяне на матрица на съседство, но трябва да запазим място за всяка възможна връзка между всички върхове (V x V), така че изисква повече пространство

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

Списък за съседство представлява графика като масив от свързани списъци.

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

Списъкът на съседство за графиката, която направихме в първия пример, е както следва:

Представяне на списъка за съседство

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