Course_manual - Стор 2

// функція виявлення не пройдених вершин графа void WayDepth (void)

// Глобальна змінна для обчислення індексу

// у масивах T і B

// Глобальна змінна для обчислення міток

for (u = 0; u // спочатку всі вершини графа

// помічаємо як не пройдені

for (u = 0; u // вибір черговий не пройденої

if (Mark[u] = = Depth (u,

void main ( void )

File *p, *f; int i, j, n;

// Введення вихідних даних

p = fopen( "spisok_Adj.in", "r"); if (fscanf (p, “%d”, &n) != EOF)

// встановлення покажчика початку списку суміжності для

// введення мітки вершини // введення числа вершин у списку // суміжності вершини i

for (j = 0; j введення списку суміжності вершини i

Fst[i+1] = Fst[i] + Nbr[i]; // встановлення покажчика початку

// Список суміжності наступної вершини

// Прохід графа у глибину

f = fopen( "spisok_reber.out", "w"); for (i = 0; i, представленого на рис. 1.4. У графі 7 вершин, вершини позначені цілими числами від 0 до 6).

Структура суміжності цього графа:

Вихідні дані структури суміжності графа задаються у текстовому файлі spisok_Adj.in у наступному форматі:

• у першому рядку файлу міститься число вершин графа;

• далі для кожної вершини в окремому рядку вказується номер самої вершини, число вершин суміжних з даною, і список цих вершин (вершини перераховуються в порядку зростання міток вершин).

Вихідний файл для графа на рис. 1.4.: 7

У програмі ця структура реалізована в масивах Vt, ADj, Fst, Nbr, що мають такий вигляд:

Дане відображення структури суміжності дозволяє звертатися до елементів масивів за номерами (позначками) відповідних вершин.Операція v ADj [x] у програмній реалізації представляється як

for (i = 0; i де Nbr[x] – кількість вершин у структурі суміжності для вершини x; Adj [x] – масив , що містить списки суміжності для кожної вершини ; Fst [x] – номер першої вершини у списку суміжності , що відповідає вершині x, тоді Fst [x] + i – номер i – й вершини у списку суміжності , що відповідає вершині x. Наприклад, нехай x = 3, тоді

Nbr [3] = 2 ( у списку суміжності вершини x два елементи ),

Adj [Fst [3] + 0] = Adj [10] = 1 і Adj [Fst [3] + 1] = Adj

[11] = 2 становлять список суміжності вершини x = 3.

Розв'язання задачі починається з виклику функції WayDepth, яка спочатку позначає в масиві Mark всі вершини як не пройдені (фарбує їх міткою рівною). для неї запускається функція Depth, що реалізує прохід графа в глибину Функція Depth позначає в масиві Mark цю вершину як виявлену (фарбує її значенням цілої змінної count, тобто пройдені вершини поступово нумеруються від 0 до │ V │ їх потрапляємо ).Затем проглядається список суміжності вершини , для якої запущена функція Depth.Якщо в цьому списку є ще не пройдені вершини (т. е. мітка Mark [v] вершини v дорівнює то ребро (x, v) додається до безлічі основних ребер дерева пошуку в глибину (вершини x і v поміщаються в масив T) Процес проходу графа в глибину в цьому випадку триває, починаючи з не пройденої вершини v (для вершини v запускається функція Depth). Коли у списку суміжності вершини x виявлена ​​пройдена вершина, то при Mark [v] ≠ ребро (x, v) буде зворотним ребром, якщо Mark [v] іv ≠ s. Умова Mark [v] означає, що вершина v була пройдена раніше

вершини x. Тому ребро (x, v) буде оберненим, якщо воно не є ребром дерева пошуку, пройденим від предка s до x, т. е. v ≠ s.

Дерево пошуку у глибину для графа на рис. 1.4. має такий вигляд:

Суцільними лініями відзначені ребра дерева, які були пройдені під час обходу графа в глибину, пунктирними – ребра назад. (На рис. 1.4. жирними лініями відзначені ребра, які були пройдені під час обходу графа в глибину).

Стан робочих масивів Mark, T і B після завершення алгоритму наведено нижче:

Результати роботи виводяться у файл spisok_reber.out у наступному форматі:

• у першому рядку файлу мітки початкових вершин ребер дерева пошуку в глибину;

• у другому рядку файлу мітки кінцевих вершин ребер дерева пошуку в глибину;

• у третьому рядку файлу ознаки ребер: значення 1 – ознака основного ребра, значення 0 – ознака зворотного ребра.

Вихідний файл для графа на рис. 1.4.:

0 1 2 2 3 2 4 4 5 6

1 2 0 3 1 4 0 5 6 4

1 1 0 1 0 1 0 1 1 0

Завдання 2 . У неорієнтованому графі G(V,E) потрібно виділити компоненти зв'язності.

Оскільки граф неорієнтований, то знаходження компонент зв'язності досить пройти граф в глибину, поки залишаються не пройдені вершини, у своїй позначаючи вершини однієї компоненти зв'язності однаковими мітками. І тому досить використовувати змінну , значення якої змінюється , якщо повністю пройдено компонента зв'язності ( у цій програмі це глобальна змінна count). Компонент зв'язності при проході в глибину буде повністю пройдений, коли в списках суміжності вершин цієї компоненти не буде не пройдених вершин. Вершиниграфа позначені цілими числами. Граф заданий структурою суміжності Adj [u].

Програма виділення компонентів зв'язності – пошук у глибину ( мова Сі )

# define maxn 100 // максимальна кількість вершин у графі

# define maxADj 1000 // максимальна довжина списку суміжності графа

int Adj [maxADj]; // Список суміжності графа

// покажчики на списки суміжності кожної v V

// число вершин у списку суміжності кожної v V

// Список вершин графа

// Мітки вершин графа

// функція проходження однієї компоненти зв'язності

void Component (int u)

// вершина u позначається як пройдена вершина

// Вибір зі списку суміжності u ще не

// функція пошуку не пройдених вершин графа, т.к. е. нової компоненти зв'язності STRONGL_Comp2 (void)

for (u = 0; u // спочатку всі вершини графа

// помічаємо як не пройдені

for (u = 0; u // вибір чергової не пройденої вершини

// Збільшення числа компонент зв'язності

void main ( void )

// Введення вихідних даних

p = fopen( "spisok_Adj.in", "r");

if (fscanf (p, “%d”, &n) != EOF)

// Введення числа вершин графа

// встановлення покажчика початку списку суміжності для

for (i = 0; i // введення мітки вершини

// Введення числа вершин у списку

// суміжності вершини i

for (j = 0; j // введення списку суміжності вершини i

Fst[i+1] = Fst[i] + Nbr[i];

// встановлення покажчика початку

// Список суміжності наступної вершини

STRONGL_Comp2 ( ); // Прохід графа в глибину, пошук компонент зв'язності

f = fopen( "component.out", "w"); for ( i = 0; i , представленого на рис. 1.5. У графі 11 вершин , вершини позначені цілими числами , починаючи з1.

Структура суміжності цього графа:

Вихідні дані структури суміжності графа задаються у текстовому файлі spisok_Adj.in у аналогічному форматі задачі 1.

Вихідний файл для графа на рис. 1.5.:

У програмі ця структура реалізована у масивах Vt, ADj, Fst, Nbr, мітки компонент – у масиві Mark. Стан масивів після виконання програми наведено нижче.

Результати роботи виводяться у файл component.out у наступному форматі:

• у першому рядку файлу мітки вершин графа;

• у другому рядку файлу номера компонент зв'язку. Вихідний файл для графа на рис. 1.5.:

2.3.3. Обхід (або пошук) завширшки

Нехай заданий граф (вихідний граф може бути неорієнтованим або орієнтованим) і фіксована початкова вершина s. У процесі пошуку ми йдемо вшир, а не вглиб: спочатку переглядаємо всі сусідні з вершини, потім сусідів сусідів і т.д. д. Алгоритм пошуку в ширину перераховує всі досяжні з s (якщо йти по ребрах) вершини в порядку зростання відстані від s. Відстанню вважається довжина (число ребер) найкоротшого шляху. У процесі пошуку з графа виділяється частина, звана "деревом пошуку завширшки" з коренем s. Воно містить усі досяжні з s вершини (і тільки їх). Для кожної з цих вершин шлях з кореня (вершини s) у дереві пошуку буде одним із найкоротших шляхів (з початкової вершини) у графі. Алгоритм також використовує кольори вершин. Спочатку всі вершини білі (не пройдені), у процесі пошуку біла вершина може стати сірою, якщо вона виявлена, а сіра – чорною. Відмінність між сірою та чорною вершиною дозволяє підтримувати таку властивість: якщо (u,v) E та u чорна, то v – сіра або чорна вершина. Таким чином, тільки сірі вершини можуть мати суміжні невиявленівершини.

Спочатку дерево пошуку завширшки складається тільки з кореня - початкової вершини s. Як тільки виявлена ​​біла вершина v, суміжна з раніше знайденою вершиною u, вершина v (разом з ребром (u,v)) додається до дерева пошуку, стаючи нащадком вершини u, а u стає батьком v. Кожна вершина виявляється лише одного разу, тож двох батьків у неї бути не може.

Нижче наведений алгоритм використовує представлення графа списками суміжних вершин Adj [u]. Для кожної вершини u графа додатково зберігаються її колір Mark [u] та її попередник Pr[u]. Якщо попередника немає (наприклад, якщо u = s або u ще не виявлено), то Pr [u] = nil. Крім того, d [u] записується відстань від s до u. Алгоритм також використовує чергу Q для зберігання безлічі сірих вершин.

---