Які способи зберігання графів існують?
Існує три основні способи зберігання графів:
1. Список суміжності (Adjacency List)
Кожна вершина зберігає список усіх вершин, з якими вона з'єднана.
Приклад: Для графа з ребрами A-B, A-C, B-C
javascript
A: B, C
B: A, C
C: A, BПлюси:
- Ефективно за пам'яттю для розріджених графів (мало ребер).
- Зручно обходити сусідів вершини.
Мінуси:
- Пошук конкретного ребра може бути повільнішим, ніж у матриці.
2. Матриця суміжності (Adjacency Matrix)
Використовується квадратна матриця n×n, де n - число вершин.
Комірка [i][j] = 1 (або вага), якщо є ребро між i та j, інакше 0.
Приклад:
javascript
A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]Плюси:
- Швидка перевірка наявності ребра (O(1)).
- Зручно для щільних графів (багато ребер).
Мінуси:
- Займає O(n²) пам'яті, навіть якщо зв'язків мало.
3. Список ребер (Edge List)
Зберігається просто список усіх ребер у вигляді пар (або трійок, якщо є вага):
javascript
[(A, B), (A, C), (B, C)]або
javascript
[(A, B, 5), (B, C, 3), (A, C, 8)]Плюси:
- Проста структура.
- Зручно для алгоритмів, які працюють напряму з ребрами (наприклад, Крускала).
Мінуси:
- Незручно шукати сусідів вершини.
Підсумок:
| Метод | Пам'ять | Зручно для | Приклад застосування |
|---|---|---|---|
| Список суміжності | O(V + E) | обходів і пошуку шляхів | алгоритми Дейкстри, BFS, DFS |
| Матриця суміжності | O(V²) | швидких перевірок зв'язків | щільні графи |
| Список ребер | O(E) | роботи з ребрами напряму | алгоритм Крускала |
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.