Aлгоритмы на графах

Тип работы:
Реферат
Предмет:
Информатика, программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Елементи теорії графів. Граф — сукупність крапок і ліній, де кожна лінія з'єднує дві точки. Крапки називаються вершинами, чи вузлами, графа, лінії - ребрами графа. Якщо ребро з'єднають дві вершини, то кажуть, що його їм инцидентно; вершини, з'єднані руба називаються суміжними. Дві вершини, з'єднані руба, можуть збігатися; таке ребро називається петлею. Кількість ребер, инцидентных вершині, називається ступенем вершини. Якщо два ребра инцидентны одному й тому ж парі вершин, вони називаються кратними; граф, у якому кратні ребра, називається мультиграфом. Ребро, з'єднуюче дві вершини, може мати напрям від однієї вершини в іншу; у разі воно називається спрямованим, чи орієнтованим, і змальовується стрілкою. Граф, де всі ребра орієнтовані, називається орієнтованим графом (орграфом); ребра орграфа часто називають дугами. Дуги іменуються кратними, якщо вони лише мають загальні вершини, а й збігаються в напрямі. Іноді потрібно розглядати не весь граф, а його частину (частина вершин і частина ребер). Частина вершин і всі инцидентные їм ребра називаються подграфом; все вершини і частина инцидентных їм ребер називаються суграфом. Циклом називається замкнута ланцюг вершин. Деревом називається граф без циклів. Остовным деревом називається пов’язаний суграф графа, яка має циклов.

Граф однозначно заданий, якщо задано безліч його вершин, безліч ребер і вказано все инцидентности (тобто. зазначено, які вершини якими ребрами з'єднані). Найнаочніше граф задається малюнком; проте всі деталі малюнка однаково важливі; зокрема, несуттєві геометричні властивості ребер (довга, кривизна тощо.) і взаємна розташування вершин на плоскости.

Для неориентированного ребра порядок, у якому указанны соединяемые їм вершини, не важливий. Для орієнтованого ребра важливо: першої вказується вершина, з якої виходить ребро.

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

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

Завдання у тому, знайти шляхи з вершини A в вершину B. Будемо ставити граф матрицею суміжності, тобто. квадратної таблицею NxN, в чим перетині i-го рядки — і j-го шпальти значення TRUE, якщо і і j з'єднані руба, і FALSE у протилежному случае.

Пошук в ширину.

Приблизно так як, відповідно до принципу Гюйгенса, кожна точка хвильового фронту є джерелом вторинної хвилі, ми, вирушивши з заданої вершини A, відвідуємо все суміжні із нею вершини (тобто. вершини, у яких ведуть стрілки з A). Кожна посещенная вершина стає джерелом нової хвилі тощо. У цьому слід подбати у тому, ніж повернуться до ту вершину, у якій были.

Задля реалізації алгоритму знадобляться: матриця m[1. n, 1. n] - матриця суміжності графа; допоміжний масив queue[1. n], у якому формуватися чергу, тобто. тип даних перший ввійшов — перший вийшов (FIFO). Розмір його достатній, адже ми не відвідуємо вершини двічі. З масивом queue пов’язані дві перемінні - head і tail. У перемінної head перебуватиме номер поточної вершини, з якої йде хвиля, а з допомогою перемінної tail нових вершин вкладаються у «хвіст «черги queue; допоміжний масив visited[1. n], потрібного у тому, щоб відзначати вже пройдені вершини (visited[i]=TRUE вершина і пройдено); допоміжний масив prev[1. n] для зберігання пройдених вершин. У цьому масиві і буде сформовано шуканий шлях; змінна f, яка прийме значення TRUE, коли шлях буде найден.

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

Program breadth_first_search;

Const n=9; m: array[1. n, 1. n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True),

(False, True, False, False, False, True, False, True, True),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;

Procedure A_to_B (A, B: integer);

Var

Visited: array[1. n] of boolean;

Prev: array[1. n] of integer; з: array[1. n] of integer; head, tail: integer; f: boolean; і, v, k: integer;

Begin head: =1; tail: =1; f: =False;

For i: =1 to n do

Begin

Visited[i]: =False;

Prev[i]: =0

End;

C[tail]: =A;

Visited[A]: =True;

While (head

ПоказатьСвернуть
Заполнить форму текущей работой