П'ятниця, 29.03.2024, 16:20
Гость

Мішатронік

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Чи знаєте ви, що таке спортивне програмування?
Всього відповідей: 0
Статистика

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


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

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

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

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

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

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

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

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

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

 

Форма входа
Пошук
Друзі сайту
Календар
«  Березень 2024  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031

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