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

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

  1. Матрица на съседство
  2. Списък на съседство

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

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

Ето пример за списък със съседство:

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

Да кажем, че една графа съдържа 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 означава броя на възлите в графиката.