Мішатронік

Способи представлення графа

Представлення графів в пам’яті – це спосіб збереження інформації про ребра графа, який дозволяє розв'язувати наступні задачі:

1. Для двох даних вершин u та v перевірити, чи з’єднані вершини u та v ребром.
2. Перебрати усі ребра, які виходять з даної вершини u.

При цьому спосіб збереження графів в пам’яті повинен враховувати можливості роботи з орієнтованими та неорієнтованими графами. За замовчуванням можна припустити, що ми маємо справу з графами без петель та кратних ребер, тобто з  простими графами.

Основними способами збереження графа є:

1. Матриця суміжності.
2. Списки (або множини) суміжних вершин.
3. Матриця інцеденції.

Для вирішення задач по спортивному програмуванню зберігати граф у матриці суміжності є недоцільно, адже проходження по графу займатиме багато часу.

В мові С++ краще використовувати vector< vector<int> >g;

Джерела: disted.edu.vn.ua