|
Способи представлення графа
Представлення графів в пам’яті – це спосіб збереження інформації про ребра графа, який дозволяє розв'язувати наступні задачі:
- Для двох даних вершин u та v перевірити, чи з’єднані вершини u та v ребром.
- Перебрати усі ребра, які виходять з даної вершини u.
При цьому спосіб збереження графів в пам’яті повинен враховувати можливості роботи з орієнтованими та неорієнтованими графами. За замовчуванням можна припустити, що ми маємо справу з графами без петель та кратних ребер, тобто з простими графами.
Основними способами збереження графа є:
- Матриця суміжності.
- Списки (або множини) суміжних вершин.
- Матриця інцеденції.
Для вирішення задач по спортивному програмуванню зберігати граф у матриці суміжності є недоцільно, адже проходження по графу займатиме багато часу.
В мові С++ краще використовувати vector< vector<int> >g;
Джерела: disted.edu.vn.ua
|
