Списък на съседство и матрично представяне на графика
Въпреки че изглеждат различни, всички видове графики могат да бъдат представени по подобен начин. Обикновено има два вида графично представяне:
- Матрица на съседство
- Списък на съседство
Списък на съседство
Списъкът за съседство се състои от свързани списъци. Всеки връх се счита за индекс на масив и всеки елемент представлява свързан списък. Тези свързани списъци съдържат върховете, които имат ръбове с индексния връх.
Ето пример за списък със съседство:
Да кажем, че една графа съдържа V брой върхове и E брой ръбове.
Като цяло космическата сложност ще бъде O(V + E)
.
В най-лошия случай космическата сложност ще бъде O(V2)
ако дадената Графа е пълната Графа
Матрица на съседство
Матрицата на съседство се състои от 2D масив. Графиката има V брой върхове, размерът на матрицата ще бъде VxV
.
кажи, matrix[i][j] = 5
. Това означава, че има край между възел i и j, където теглото е 5.
Нека да разгледаме следната графика и нейната матрица на съседство:
Ние създадохме 2D масив използвайки тези стъпки:
Стъпка 1) Връх A има пряк ръб с B и теглото е 5. Така че клетката в ред A и колона B ще бъдат запълнени с 5. Останалите клетки в ред A ще бъдат запълнени с нула.
Стъпка 2) Върховете B имат пряк ръб с C и теглото е 4. Така че клетката в ред B и колона C ще бъдат запълнени с 4. Останалите клетки в ред B ще бъдат запълнени с нула, тъй като B няма изходящ ръб към никоя други възли.
Стъпка 3) Върховете C нямат преки ръбове с други върхове. И така, ред C ще бъде запълнен с нули.
Стъпка 4) Връх D има насочен ръб с A и C.
- Тук клетката в ред D и колона A ще има стойност 7. Клетките в ред D и колона C ще имат стойност 2.
- Останалите клетки в ред D ще бъдат запълнени с нули.
Стъпка 5) Върховете E имат насочен ръб с B и D. Клетката в ред E и колона B ще има стойност 6. Клетките в ред E и колона D ще имат стойност 3. Останалите клетки в ред D ще бъдат пълни с нули.
Ето някои точки, които трябва да обърнете внимание:
- Графиката няма собствени цикли, когато основният диагонал на матрицата на съседство е 0.
- Графиката е насочена графа, ако индексите (a,b) и (b,a) нямат една и съща стойност. В противен случай Graph е насочен граф.
- Графиката ще бъде претеглена графика, ако стойността на клетките е повече от 1.
Има някакъв проблем с матрицата на съседство, тъй като тя изисква интервали на квадрат. Тук съхраняваме ръбовете, които не са свързани. Тези ръбове разпределят място в паметта.
Например, ако имаме график със 100 възела, тогава са необходими 10 хиляди клетки, за да го съхраним в RAM. С по-малко ръбове в Graph, разпределянето на толкова голяма памет може да бъде загуба. И така, пространствената сложност, използваща матрицата на съседство, ще бъде O(N2)
, където N означава броя на възлите в графиката.