Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

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

Реферат: 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<=tail) and not f do

Begin

v:=C[head];

head:=head+1;

For k:=1 to n do

if m[v, k] and not Visited[k] then

Begin

tail:=tail+1;

C[tail]:=k;

Visited[k]:=True;

Prev[k]:=v;

if k=B then

Begin

f:=true;

break

End

End

End;

if f then

Begin

k:=B;

Write(B);

While Prev[k]<>0 do

Begin

Write('<-', Prev[k]);

k:=Prev[k]

end

End

else

Write('Пути з ', A, ' в ', B, ' немає')

end;

Begin

Write('A= '); readln(A);

Write('B= '); readln(B);

A_to_B(A, B)

End.

Пошук завглибшки.

Ідея пошуку глибину проста: вирушаючи від поточної вершини, ми бачимо нову (ще вивчену) суміжний із нею вершину, яку помечаем як вивчену і оголошуємо поточної. Після цього процес відновлюється. Якщо новій суміжною вершини немає (глухий кут), повертаємося до тієї вершині, з якої потрапили до поточну, і робимо таку спробу. Якщо потрапимо в вершину B, друкуємо шлях. Якщо всі вершини вичерпані - такого шляху немає.

Зауважимо, побудований в такий спосіб алгоритм здатні отримувати всі дороги з A в B, але хто першим знайдений необов'язково може бути найкоротшим.

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

матриця m[1 n, 1 n] - матриця суміжності графа;

допоміжний масив visited[1 n], який ми у тому, щоб відзначати вже пройдені вершини (visited[i]=TRUE <=> вершина і пройдено);

змінна f, яка прийме значення TRUE, коли шлях буде знайдено.

Program depth_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;

f: boolean;

і: integer;

Procedure Depth(p: integer);

var k: integer;

Begin

Visited[p]:=True;

For k:=1 to n do

If not f then

If m[p, k] and not Visited[k] then

If k=B then

Begin

f:=True;

Write(B);

Break

End

else Depth(k);

If f then write('<=', p);

End;

Begin

For i:=1 to n do Visited[i]:=False;

f:=false;

Depth(A);

If not f then write('Пути з ', A, ' в ', B, ' немає')


Схожі реферати

Статистика

[1] 2 3 4