Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Які способи зберігання графів існують?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)Існує **три основні способи зберігання графів**: список суміжності, матриця суміжності та список ребер. **Ключове:** список суміжності ефективний за пам'яттю для розріджених графів, а матриця суміжності дає миттєву перевірку наявності ребра (O(1)).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняІснує **три основні способи зберігання графів**: --- ### 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) | роботи з ребрами напряму | алгоритм Крускала |Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.