Понеділок, 18.02.2019, 09:39
Гость

Мішатронік

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

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

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




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

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

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

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

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

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

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

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

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

 

Форма входа
Пошук
Календар
«  Лютий 2019  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728
Друзі сайту
Погода у Вінниці


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