Списък на съседство и матрично представяне на графика
Сара Чен
⚡ Умно обобщение
Списъкът на съседство и матричното представяне на графа съхраняват върховете и ребрата в паметта, което позволява на алгоритмите да преминават през мрежи. Списъкът на съседство използва свързани списъци за връх, докато матрицата на съседство използва квадратна двуизмерна мрежа.
Въпреки че изглеждат различни, всички видове графики може да се представи по подобен начин. Обикновено има два вида графично представяне:
- Матрица на съседство
- Списък на съседство
Списък на съседство
Списъкът на съседство се състои от свързани списъци. Всеки връх се счита за индекс на масив, а всеки елемент представлява свързан списък. Тези свързани списъци съдържат върховете, които споделят ребро с индексния връх.
Ето пример за списък на съседство:
Нека графът съдържа V брой върхове и E брой ребра. Пространствената сложност на списъка на съседство е O(V + E), който се мащабира с броя на реалните ръбове, а не с всяка възможна двойка върхове.
Най-лошият случай на пространствена сложност става O(V²) ако даденият граф е пълен граф, тъй като всеки връх е свързан с всеки друг връх.
Матрица на съседство
Матрицата на съседство е съставена от 2D масив. За граф с V върха, размерът на матрицата ще бъде V × V.
Казвам 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. Останалите клетки в ред E ще бъдат запълнени с нули.
Ето някои точки, които трябва да обърнете внимание:
- Графиката няма самоциклични цикли, когато основният диагонал на матрицата на съседство е 0.
- Графиката е насочена, ако клетките в (a, b) и (b, a) не съдържат една и съща стойност. В противен случай графиката е ненасочена.
- Графиката е претеглена графика, ако стойността на която и да е клетка е по-голяма от 1.
Основният проблем с матрицата на съседство е, че тя изисква квадратно пространство. Дори ребра, които не съществуват, все още разпределят клетки в паметта.
Например, ако имаме граф със 100 възела, тогава са необходими 10 000 клетки, за да се съхранява в него. RAMС по-малко ръбове в графа, разпределянето на толкова голяма памет може да бъде разточително. Така че пространствената сложност, използваща матрицата на съседство, е O(N²), където N е броят на възлите в графа.
Списък на съседство срещу Матрица на съседство
Преди да изберете представяне, е полезно да сравните двата модела един до друг в операциите, които доминират в реалните графични натоварвания:
| OperaАЦИ | Матрица на съседство | Списък на съседство |
|---|---|---|
| Сложност на пространството | O(V²) | O(V + E) |
| Добавяне на връх | O(V²) | O (1) |
| Добавете ръб | O (1) | O (1) |
| Премахване на ръб | O (1) | O(E) |
| Проверка дали ръб (i, j) съществува | O (1) | O (степен на i) |
| Итерация върху съседите на i | O(V) | O (степен на i) |
| Най - доброто за | Плътни графи, чести заявки към ръбове | Разредени графи, задачи с голямо търсене |
Накратко, матрицата на съседство печели при търсения на ръбове за постоянно време, докато списъкът на съседство печели при итерации на паметта и съседите, поради което алгоритми като BFS, DFS и Dijkstra обикновено се съчетават със списъци на съседство.
Предимства и недостатъци на графичното представяне
Всяко представяне носи своите недостатъци. Познаването на силните и слабите страни на двата модела ви помага да изберете правилния за проблема, който решавате.
Предимства на матрицата на съседство:
- Запитвания за съществуване на ръбове между произволна двойка върхове с константно време O(1).
- Фиксираното индексиране прави матрично-базирани алгоритми, като например Флойд-Уоршал и транзитивно затваряне, лесни за изпълнение.
- Претеглените ръбове се вписват естествено в една матрична клетка.
Недостатъци на матрицата на съседство:
- Загубва O(V²) памет, когато графиката е разредена.
- Добавянето на нов връх изисква преоразмеряване на цялата матрица.
- Итерирането върху съседите на един връх отнема O(V), дори когато върхът има само няколко ребра.
Предимства на списъка за съседство:
- Използва само O(V + E) памет, което е близко до реалния брой ръбове в разредени графове.
- Добавянето на нов връх или ръб е O(1).
- Алгоритми за обхождане, като BFS и DFS, итерират съседите в O(степен), което дава общо време за изпълнение O(V + E).
Недостатъци на списъка за съседство:
- Проверката дали съществува специфичен ръб отнема време O(градус) вместо O(1).
- Локалността на кеша е по-слаба, защото свързаните списъци са разпръснати из паметта.
- Претеглените ръбове се нуждаят от съпътстващо поле или списък от двойки, което леко усложнява структурата на данните.
Кога да използвате списък на съседство спрямо матрица на съседство
Изборът на представяне зависи от плътността на графиката и операциите, които изпълнявате най-често. Използвайте това кратко ръководство, за да изберете правилната структура:
- Предпочитайте матрицата на съседство когато графът е плътен (E е близо до V²), когато ръбовете рядко се променят и когато алгоритъмът ви пита многократно „има ли ръб между i и j?“.
- Предпочитайте списъка със съседни позиции когато графът е разреден (E е много по-малко от V²), когато множеството от върхове или ръбове расте по време на изпълнение и когато обхождате графа с BFS, DFS или Алгоритъмът за най-къс път на Дейкстра.
- Предпочитайте смесен модел (списък на съседни обекти плюс хеш набор от ръбове), когато се нуждаете както от бърза итерация на съседи, така и от O(1) заявки за ръбове, за сметка на допълнителна памет.
Съвременните графови библиотеки като NetworkX и igraph по подразбиране използват списъци със съседни данни, защото повечето графи от реалния свят – социални мрежи, пътни карти, уеб страници, зависимости на пакети – са разредени и изискват много преминаване.
