Способи представлення графа
Представлення графів в пам’яті – це спосіб збереження інформації про ребра графа, який дозволяє розв'язувати наступні задачі:
1. Для двох даних вершин u та v перевірити, чи з’єднані вершини u та v ребром.2. Перебрати усі ребра, які виходять з даної вершини u.
При цьому спосіб збереження графів в пам’яті повинен враховувати можливості роботи з орієнтованими та неорієнтованими графами. За замовчуванням припускатимемо, що ми маємо справу з графами без петель та кратних ребер, тобто з простими графами.
Основними способами збереження графа є:
Джерела:http://foxford.ru/wiki/informatika/sposoby-hraneniya-grafa1. Матриця суміжності.2. Списки (або множини) суміжних вершин.3. Список ребер.
Немає коментарів:
Дописати коментар