10-11. Графи і алгоритми їх обробки

Перелік алгоритмів, що розглядаються

  • пошук у глибину;
  • пошук у ширину;
  • алгоритм Дейктри

Короткі теоретичні відомості

Питання для повторення

  1. Реалізація стеків і черг.

Постановка задачі

žГрафом називається сукупність двох множин:

  • непорожньої множини V (множини вершин)
  • множини E неупорядкованих пар різних елементів множини V (E – множина ребер)

Необхідно розробити подання графів у пам'яті комп'ютера, а також забезечити реалізацію таких дій:

  • обхід графа;
  • пошук довжин найкоротших шляхів від заданої вершини графа (джерела) до всіх інших вершин графа.

Опис алгоритмів

Опис структур даних
  • матриця суміжності: елемент з індексами i, j дорівнює 1, якщо вершини i та j є суміжними, і 0 в іншому випадку;
  • матриця інциденцій: елемент з індексами i, j дорівнює 0, якщо вершина i не є індидентною ребру j; 1, якщо інцидентна (для орграфа 1 - якщо вершина i є кінцем ребра j, і -1, якщо початком);
  • масив ребер (дуг): масив, кожен елемент якого є пара суміжних вершин;
  • список суміжності: масив, кожен елемент якого є покажчиком на список суміжних вершин.

1. Обхід графа

Ідея

Обхід починається з вершини v. Під час обходу вершини, суміжні з поточною, відмічаються і вносяться до структури даних T (стеку або черги). Чергова вершина для перегляду береться зі структури T, поки T не стане порожньою. Якщо як структура даних використовується стек, то говорять про пошук у глибину, якщо черга — про пошук у ширину.

Для відмічання вершин використовується масив marks, початкові значення елементів якого дорівнюють 0 (вершини невідмічені).

Псевдокод
Вставити (v, T)
marks[v] = 1
поки Т не порожня
{
  u = Вилучити (T)
  Вивести u
  Для всіх t з множини вершин V
    якщо t суміжна з u і marks[t] == 0
      то {Вставити (t, T); marks[t] = 1}
}

2.Пошук найкоротших шляхів

Ідея

Поступово уточнювати шукані шляхи:

  • спочатку покласти найкоротші шляхи рівними довжині ребра від джерела (вершини 1) до відповідної вершини;
  • на кожній ітерації намагатися зменшити шлях, замінивши "прямий" щлях "обхідним" через вершину, яка знаходиться на найменшій віддалі.

Алгоритм використовує множину S вершин, для яких найкоротші шляхи відомі та масив d цих найкоротших шляхів.

Псевдокод
// ініціалізація
S={1}
для  i  від  2  до  n
  d[i] = довжина ребра (1, i)
// уточнення шляхів
для  i  від  2  до  n – 1
{
  вибрати з V \ S вершину w, для якої d[w] мінімально
  S = S + {w};
  для кожної v з V \ S
    –d[v]= min{d[v],d[w]+довжина ребра (w,v)}
}

Завдання для виконання

Постановка задачі

Скласти програми, що забезпечують виконання операцій з графами. Програма повинна забезпечувати
  • введення з файлу графа у заданому поданні;
  • виведення на екран графа у вказаному викладачем поданні (тому самому, що й при введенні або іншому);
  • виконання вказаних викладачем дій з графом.

Технічні умови

  • кількість вершин графа не перевищує 20;
  • довжини ребер графа є цілими числами.

Хід роботи

  1. Скласти програму Graphs.cpp для зміни способу представлення графа відповідно до таблиці:
    2. Варіант Початкове подання графа Кінцеве подання графа
    1
    		 матриця суміжності матриця інциденцій
    2
    		 матриця суміжності масив ребер
    3
    		 масив ребер матриця суміжності
    4
    		 масив ребер матриця інциденцій
    5*
    		 матриця суміжності список суміжності
  2. Скласти програму SearchGr.cpp, яка реалізує вказаний викладачем обхід графа.
  3. Виконати програму в покроковому режимі для заданого викладачем графа на 5 вершинах. Проілюструвати на відповідному геометричному графі.
  4. Скласти програму Dijkstra.cpp для визначення найкоротших шляхів від вершини 1 до всіх іниших вершин графа..
  5. Виконати програму в покроковому режимі для заданого викладачем графа на 5 вершинах. Проілюструвати на відповідному геометричному графі.

Запитання для самоконтролю

  1. Яка структура називається графом?
  2. Охарактеризуйте основні способи подання графів.
  3. Поясніть основну ідею обходу графа. Чим відрізняються пошуку в глибину і в ширину?
  4. Що таке зважений граф? У чому полягає задача пошуку найкоротших шляхів у графі?
  5. Поясніть основні ідеї алгоритму Дейкстри. Яка його часова складність?