П'ятниця, 11.07.2025, 21:37
Гость

Мішатронік

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Java чи С++
Всього відповідей: 2
Статистика

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


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

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

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

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

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

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

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

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

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

 

Форма входа
Пошук
Друзі сайту
Календар
«  Липень 2025  »
ПнВтСрЧтПтСбНд
 123456
78910111213
14151617181920
21222324252627
28293031

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