Неділя, 21.04.2019, 23:43
Гость

Мішатронік

Автор - Кренцін Михайло

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Хто ви?

Всього відповідей: 9
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0




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

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

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

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

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

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

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

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

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

 

Форма входа
Пошук
Календар
«  Квітень 2019  »
ПнВтСрЧтПтСбНд
1234567
891011121314
15161718192021
22232425262728
2930
Друзі сайту
Погода у Вінниці


Єдина Країна! Единая Страна!