Слайд 2
![Вступ Орієнтований граф (коротко орграф, англ. digraph) — (мульти) граф,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-1.jpg)
Вступ
Орієнтований граф (коротко орграф, англ. digraph) — (мульти) граф, ребрам якого
присвоєно напрямок.
Орієнтовані ребра називаються також дугами.
Слайд 3
![Вступ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-2.jpg)
Слайд 4
![Вступ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-3.jpg)
Слайд 5
![Вступ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-4.jpg)
Слайд 6
![Задачі Пошук шляху. Чи існує шлях з s в t?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-5.jpg)
Задачі
Пошук шляху. Чи існує шлях з s в t?
Слайд 7
![Задачі Найкоротший шлях який найкоротший шлях з s в t?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-6.jpg)
Задачі
Найкоротший шлях
який найкоротший шлях з s в t?
Топологічне сортування
Чи можете ви
зобразити орграф так щоб всі ребра були направлені догори
Сильна зв’язність
чи існує шлях між всіма парами вершин орграфа
Транзитивне замикання
для яких вершин v і w, існує шлях від v до w
PageRank
важливість сторінок
Слайд 8
![Digraph API public class Digraph Digraph(int V) //створити порожній орграф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-7.jpg)
Digraph API
public class Digraph
Digraph(int V) //створити порожній орграф з V вершин
Digraph(In
in) // створити орграф з вхідного потоку
void addEdge(int v, int w) // додати орієнтоване ребро v->w
Iterable adj(int v) //вершини з’єднані (сусідні) з v
int V() //кількість вершин
int E() //кількість ребер
In in = new In(args[0]);
Digraph G = new Digraph(in); //читаємо граф з вхідного потоку
for (int v = 0; v < G.V(); v++) //виводимо кожне ребро (один раз)
for (int w : G.adj(v))
StdOut.println(v + "->" + w);
Слайд 9
![Digraph API](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-8.jpg)
Слайд 10
![Внутрішнє представлення орграфа Як ви думаєте, що ми маємо використати для внутрішнього представлення орієнтованого графа?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-9.jpg)
Внутрішнє представлення орграфа
Як ви думаєте, що ми маємо використати для внутрішнього
представлення орієнтованого графа?
Слайд 11
![Внутрішнє представлення орграфа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-10.jpg)
Внутрішнє представлення орграфа
Слайд 12
![Реалізація Digraph Що необхідно змінити, що б отримати реалізацію Digraph?](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-11.jpg)
Реалізація Digraph
Що необхідно змінити, що б отримати реалізацію Digraph?
public class Graph{
private
final int V;
private final Bag[] adj;
public Graph(int V){
this.V = V;
adj = (Bag[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag();
}
public void addEdge(int v, int w){
adj[v].add(w);
adj[w].add(v);
}
public Iterable adj(int v){
return adj[v];
}
}
Слайд 13
![Реалізація Digraph public class Digraph{ private final int V; private](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-12.jpg)
Реалізація Digraph
public class Digraph{
private final int V;
private final Bag[] adj;
public Digraph(int
V){
this.V = V;
adj = (Bag[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag();
}
public void addEdge(int v, int w){
adj[v].add(w);
//прибрали стрічку
}
public Iterable adj(int v){
return adj[v];
}
}
Слайд 14
![Досяжність Проблема. Знайти всі вершини досяжні з s в орієнтованому графі.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-13.jpg)
Досяжність
Проблема. Знайти всі вершини досяжні з s в орієнтованому графі.
Слайд 15
![Алгоритми пошуку Ми вже знаємо два алгоритми пошуку, нагадайте мені.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-14.jpg)
Алгоритми пошуку
Ми вже знаємо два алгоритми пошуку,
нагадайте мені.
Чи можна їх використовувати
для орієнтованих графів?
Слайд 16
![DFS DFS(v) – відвідати вершину v відмічаємо v як відвідану](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-15.jpg)
DFS
DFS(v) – відвідати вершину v
відмічаємо v як відвідану
рекурсивно відвідуємо усі суміжні
невідмічені вершини.
Кожний неорієнтований граф є орграфом (з ребрами направленими в обидва боки).
Що необхідно змінити в реалізації алгоритму, що б він працював на орієнтованих графах?
Слайд 17
![BFS Алгоритм: повторюємо поки черга не порожня: дістати вершину v](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-16.jpg)
BFS
Алгоритм:
повторюємо поки черга не порожня:
дістати вершину v з черги
додати в чергу
всі невідвідані вершини суміжні з v і помітити їх
Реалізація аналогічна.
Слайд 18
![Найкоротший шлях з множини джерел Найкоротший шлях з множини джерел.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-17.jpg)
Найкоротший шлях з множини джерел
Найкоротший шлях з множини джерел.
Маємо орграф
і множину джерел вершин, знайти найкоротший шлях до заданої вершини.
Приклад. S={1,7,10}
Найкоротший шлях до 4:
7->6->4
Найкоротший шлях до 5:
7->6->0->5
Найкоротший шлях до 12:
10->12
Як реалізувати?
Беремо BFS, але ініціалізувати чергу всіма вершинами множини.
Слайд 19
![Обхід веб Пошуковий робот. Розглянемо спрощену задачу. На вхід подається](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-18.jpg)
Обхід веб
Пошуковий робот.
Розглянемо спрощену задачу.
На вхід подається початкова сторінка.
Віднайти всі гіперлінки на сторінці і продовжити обхід
Слайд 20
![Обхід веб Алгоритм. Використовуємо BFS. вибираємо початкову сторінку як s](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-19.jpg)
Обхід веб
Алгоритм. Використовуємо BFS.
вибираємо початкову сторінку як s
створюємо чергу веб-сайтів для
відвідування
створюємо чергу вже відвіданих сторінок
з черги забираємо наступний сайт для відвідування і додаємо в чергу сайти на які є посилання з сторінки.
Чому не використати DFS?
Слайд 21
![Обхід веб Реалізація WebCrawler.java](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-20.jpg)
Обхід веб
Реалізація WebCrawler.java
Слайд 22
![Планування Нам даються певні завдання, що мають бути виконані з](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-21.jpg)
Планування
Нам даються певні завдання, що мають бути виконані з черговістю.
Питання,
в якій черзі ми маємо робити ці завдання.
Для цього використаємо модель орграфа.
вершини – завдання
ребра - черговість
Слайд 23
![Топологічне сортування Топологічний пошук працює на орієнтованих ациклічних графах (ОАГ).](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-22.jpg)
Топологічне сортування
Топологічний пошук працює на орієнтованих ациклічних графах (ОАГ).
Якщо в нас
буде присутній цикл, ми не зможемо вирішити проблему.
Чому?
Слайд 24
![Топологічне сортування Якщо ми маємо ОАГ, для вирішення задачі топологічного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-23.jpg)
Топологічне сортування
Якщо ми маємо ОАГ, для вирішення задачі топологічного сортування ми
маємо перемалювати його так, що б всі направлені ребра вказували вгору.
Таким чином ми отримаємо послідовність дій (порядок виконання).
Слайд 25
![Топологічне сортування Для вирішення цієї задачі ми можемо використати DFS](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-24.jpg)
Топологічне сортування
Для вирішення цієї задачі ми можемо використати DFS
Алгоритм:
запустити DFS
повернути вершини
в зворотному порядку
Слайд 26
![Топологічне сортування Відвідати 0. Відмітити як відвідану вершину З 0 є вихідні ребра.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-25.jpg)
Топологічне сортування
Відвідати 0. Відмітити як відвідану вершину
З 0 є вихідні ребра.
Слайд 27
![Топологічне сортування Відвідати 1. Відмітити як відвідану. З 1 є вихідні ребра.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-26.jpg)
Топологічне сортування
Відвідати 1. Відмітити як відвідану.
З 1 є вихідні ребра.
Слайд 28
![Топологічне сортування Відвідати 4. Відмітити як відвідану. З 4 немає](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-27.jpg)
Топологічне сортування
Відвідати 4. Відмітити як відвідану.
З 4 немає вихідних ребер.
Тому
повертаємо 4 і записуємо в postorder.
Слайд 29
![Топологічне сортування Повернулися назад. З 1 більше немає вихідних ребер.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-28.jpg)
Топологічне сортування
Повернулися назад.
З 1 більше немає вихідних ребер.
Тому повертаємо
1 і записуємо в postorder.
Слайд 30
![Топологічне сортування Повернулися назад. З 0 є вихідне ребро. Відвідати](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-29.jpg)
Топологічне сортування
Повернулися назад.
З 0 є вихідне ребро.
Відвідати 2. з два
немає вихідних ребер, додати в postorder
Слайд 31
![Топологічне сортування Повернулися назад. З 0 є вихідне ребро. Відвідати 5. З 5 є вихідне ребро.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-30.jpg)
Топологічне сортування
Повернулися назад.
З 0 є вихідне ребро.
Відвідати 5. З 5
є вихідне ребро.
Слайд 32
![Топологічне сортування 2 вже відвідане. З 5 більше немає вихідних](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-31.jpg)
Топологічне сортування
2 вже відвідане.
З 5 більше немає вихідних ребер.
Повернути 5 і
записати до postorder.
Слайд 33
![Топологічне сортування Повернулися в 0. З 0 немає більше не відвіданих ребер. Повернути 0.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-32.jpg)
Топологічне сортування
Повернулися в 0.
З 0 немає більше не відвіданих ребер.
Повернути 0.
Слайд 34
![Топологічне сортування 0 відвідане. Переглядаємо наступні вузли 1,2 (вони обидва](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-33.jpg)
Топологічне сортування
0 відвідане.
Переглядаємо наступні вузли 1,2 (вони обидва вже відвідані.
Наступний
не відвіданий вузол 3.
Відвідати 3.
Слайд 35
![Топологічне сортування Відвідати 2, відвідано. Відвідати 4, відвідано. Відвідати 5, відвідано. Відвідати 6.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-34.jpg)
Топологічне сортування
Відвідати 2, відвідано.
Відвідати 4, відвідано.
Відвідати 5, відвідано.
Відвідати 6.
Слайд 36
![Топологічне сортування З 6 є вихідні ребра. 0 відвідане 4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-35.jpg)
Топологічне сортування
З 6 є вихідні ребра.
0 відвідане
4 відвідане
Повернути 6 і записати
в postorder
Слайд 37
![Топологічне сортування З 3 більше немає ребер, повернути 3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-36.jpg)
Топологічне сортування
З 3 більше немає ребер, повернути 3
Слайд 38
![Топологічне сортування Всі вузли відвідані. Ми отримали postorder.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-37.jpg)
Топологічне сортування
Всі вузли відвідані. Ми отримали postorder.
Слайд 39
![Топологічне сортування Перевертаємо postorder і отримаємо топологічну чергу.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-38.jpg)
Топологічне сортування
Перевертаємо postorder і отримаємо топологічну чергу.
Слайд 40
![Топологічне сортування Орграф має топологічну чергу, якщо не має циклів.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-39.jpg)
Топологічне сортування
Орграф має топологічну чергу, якщо не має циклів.
Досить просто вирішуєма
задача, пошуку циклів в орієнтованому графі.
Слайд 41
![Цикли в орієнтовних графах Компілятор Java ідентифікує цикли. Спробуйте: public](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-40.jpg)
Цикли в орієнтовних графах
Компілятор Java ідентифікує цикли.
Спробуйте:
public class A extends B{
...
}
public
class B extends C{
...
}
public class C extends A{
...
}
компілятор видасть помилку.
Слайд 42
![Цикли в орієнтовних графах Microsoft Excell робить пошук циклів](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-41.jpg)
Цикли в орієнтовних графах
Microsoft Excell робить пошук циклів
Слайд 43
![Сильно зв’язані компоненти Вершини v і w є сильно зв’язаними](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-42.jpg)
Сильно зв’язані компоненти
Вершини v і w є сильно зв’язаними (СЗ) якщо
існує направлений шлях з v в w і з w в v.
Основні властивості:
vсильно зв’язана з v
якщо v СЗ з w тоді і w СЗ з v
якщо v СЗ з w, а w СЗ з x, тоді v СЗ з x
Сильно зв’язаним компонентом називають максимальну підмножину сильно зв’язаних вершин
Слайд 44
![Сильно зв’язані компоненти Згадаємо спочатку неорієнтовані графи і зв’язані компоненти.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-43.jpg)
Сильно зв’язані компоненти
Згадаємо спочатку неорієнтовані графи і зв’язані компоненти.
На малюнку 3
з’єднаних компоненти
Як ми пам’ятаємо досить просто обрахувати id компонента за допомогою DFS
public int connected(int v, int w){ return cc[v] == cc[w];
}
Слайд 45
![Сильно зв’язані компоненти З орієнтованими графами в нас з’являється умова](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-44.jpg)
Сильно зв’язані компоненти
З орієнтованими графами в нас з’являється умова сильної зв’язаності
вершин.
На малюнку 5 СЗК.
Ми знову можемо використати масив для зберігання СЗК id
public int stronglyConnected(int v, int w){
return scc[v] == scc[w];
}
Слайд 46
![Сильно зв’язані компоненти До 80-х років не існувало простих алгоритмів](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-45.jpg)
Сильно зв’язані компоненти
До 80-х років не існувало простих алгоритмів знаходження сильно
зв’язаних компонентів.
В 1978 р. з’явився простий двопрохідний алгоритм з лінійним часом, який приписують Косараджу.
Хоча пізніше цей алгоритм був знайдений в російській літературі датованій 72 роком.
В 90-х з’явився більш простий алгоритм Cheriyan-Mehlhorn.
Слайд 47
![Алгоритм Косараджу В алгоритмі використовується той факт, що в транспонованому](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-46.jpg)
Алгоритм Косараджу
В алгоритмі використовується той факт, що в транспонованому орграфі (той
самий граф з оберненими напрямками ребер) має ті самі сильно зв’язані компоненти, що й початковий граф.
Основна ідея:
Обрахувати топологічну чергу в трансопонованому орграфі
Запустити DFS використовуючи топологічну чергу
Слайд 48
![Алгоритм Косараджу Почнемо з фази один. Обрахунок топологічної черги.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-47.jpg)
Алгоритм Косараджу
Почнемо з фази один. Обрахунок топологічної черги.
Слайд 49
![Алгоритм Косараджу Отримаємо транспонований орграф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-48.jpg)
Алгоритм Косараджу
Отримаємо транспонований орграф
Слайд 50
![Алгоритм Косараджу Відвідати 0.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-49.jpg)
Алгоритм Косараджу
Відвідати 0.
Слайд 51
![Алгоритм Косараджу Відвідати 6.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-50.jpg)
Алгоритм Косараджу
Відвідати 6.
Слайд 52
![Алгоритм Косараджу Відвідати 8](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-51.jpg)
Алгоритм Косараджу
Відвідати 8
Слайд 53
![Алгоритм Косараджу Відвідати 6. Але 6 відвідано. Значить з 8 закінчили. Додати 8 до стеку.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-52.jpg)
Алгоритм Косараджу
Відвідати 6. Але 6 відвідано.
Значить з 8 закінчили. Додати 8
до стеку.
Слайд 54
![Алгоритм Косараджу З 6 є перехід в 7. Відвідати 7.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-53.jpg)
Алгоритм Косараджу
З 6 є перехід в 7.
Відвідати 7.
Слайд 55
![Алгоритм Косараджу З 7 немає більше ребер. Додати 7 до стеку.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-54.jpg)
Алгоритм Косараджу
З 7 немає більше ребер. Додати 7 до стеку.
Слайд 56
![Алгоритм Косараджу З 6 немає більше ребер, додати 6 до списку.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-55.jpg)
Алгоритм Косараджу
З 6 немає більше ребер, додати 6 до списку.
Слайд 57
![Алгоритм Косараджу З 0 є ребро в 2. Відвідати 2.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-56.jpg)
Алгоритм Косараджу
З 0 є ребро в 2.
Відвідати 2.
Слайд 58
![Алгоритм Косараджу Відвідати 4.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-57.jpg)
Алгоритм Косараджу
Відвідати 4.
Слайд 59
![Алгоритм Косараджу Відвідати 11.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-58.jpg)
Алгоритм Косараджу
Відвідати 11.
Слайд 60
![Алгоритм Косараджу Відвідати 9.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-59.jpg)
Алгоритм Косараджу
Відвідати 9.
Слайд 61
![Алгоритм Косараджу Відвідати 12.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-60.jpg)
Алгоритм Косараджу
Відвідати 12.
Слайд 62
![Алгоритм Косараджу Відвідати 10. І повернути 10.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-61.jpg)
Алгоритм Косараджу
Відвідати 10. І повернути 10.
Слайд 63
![Алгоритм Косараджу Повернути 12.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-62.jpg)
Алгоритм Косараджу
Повернути 12.
Слайд 64
![Алгоритм Косараджу Повернути 9.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-63.jpg)
Алгоритм Косараджу
Повернути 9.
Слайд 65
![Алгоритм Косараджу Повернути 11.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-64.jpg)
Алгоритм Косараджу
Повернути 11.
Слайд 66
![Алгоритм Косараджу Відвідати 5.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-65.jpg)
Алгоритм Косараджу
Відвідати 5.
Слайд 67
![Алгоритм Косараджу Відвідати 3, і повернути.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-66.jpg)
Алгоритм Косараджу
Відвідати 3, і повернути.
Слайд 68
![Алгоритм Косараджу Повернути 5.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-67.jpg)
Алгоритм Косараджу
Повернути 5.
Слайд 69
![Алгоритм Косараджу Повернути 4.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-68.jpg)
Алгоритм Косараджу
Повернути 4.
Слайд 70
![Алгоритм Косараджу Повернути 2.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-69.jpg)
Алгоритм Косараджу
Повернути 2.
Слайд 71
![Алгоритм Косараджу Повернути 0.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-70.jpg)
Алгоритм Косараджу
Повернути 0.
Слайд 72
![Алгоритм Косараджу Єдиний вузол не відвіданий 1. Відвідати 1 і повернути.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-71.jpg)
Алгоритм Косараджу
Єдиний вузол не відвіданий 1.
Відвідати 1 і повернути.
Слайд 73
![Алгоритм Косараджу Ми отримали топологічну чергу. Перейдемо до етапу 2.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-72.jpg)
Алгоритм Косараджу
Ми отримали топологічну чергу.
Перейдемо до етапу 2.
Маємо чергу 1,0,2,4,5,3,11,9,12,10,6,7,8
Повертаємося назад
до вихідного орграфу.
Слайд 74
![Алгоритм Косараджу Тепер починаємо DFS згідно черги. Відвідали 1. З](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-73.jpg)
Алгоритм Косараджу
Тепер починаємо DFS згідно черги.
Відвідали 1. З 1 немає більше
виходів. Значить цей елемент лежить в СЗК 0.
Слайд 75
![Алгоритм Косараджу Відвідати 0.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-74.jpg)
Алгоритм Косараджу
Відвідати 0.
Слайд 76
![Алгоритм Косараджу Відвідати 5.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-75.jpg)
Алгоритм Косараджу
Відвідати 5.
Слайд 77
![Алгоритм Косараджу Відвідати 4.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-76.jpg)
Алгоритм Косараджу
Відвідати 4.
Слайд 78
![Алгоритм Косараджу Відвідати 3.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-77.jpg)
Алгоритм Косараджу
Відвідати 3.
Слайд 79
![Алгоритм Косараджу Відвідати 5, відвідано, відвідати 2.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-78.jpg)
Алгоритм Косараджу
Відвідати 5, відвідано, відвідати 2.
Слайд 80
![Алгоритм Косараджу Відвідати 0, відвідано. Завершуємо крок рекурсії (повертаємося на початок).](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-79.jpg)
Алгоритм Косараджу
Відвідати 0, відвідано.
Завершуємо крок рекурсії (повертаємося на початок).
Слайд 81
![Алгоритм Косараджу Дістали 2 з черги. Вже відвідано, тому нічого не робимо. Аналогічно 4,5,3.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-80.jpg)
Алгоритм Косараджу
Дістали 2 з черги. Вже відвідано, тому нічого не робимо.
Аналогічно
4,5,3.
Слайд 82
![Алгоритм Косараджу Забрали з черги 11. Відвідати 11.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-81.jpg)
Алгоритм Косараджу
Забрали з черги 11.
Відвідати 11.
Слайд 83
![Алгоритм Косараджу Відвідати 12.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-82.jpg)
Алгоритм Косараджу
Відвідати 12.
Слайд 84
![Алгоритм Косараджу Відвідати 9.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-83.jpg)
Алгоритм Косараджу
Відвідати 9.
Слайд 85
![Алгоритм Косараджу Відвідати 10.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-84.jpg)
Алгоритм Косараджу
Відвідати 10.
Слайд 86
![Алгоритм Косараджу Всі можливі вузли відвідані.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-85.jpg)
Алгоритм Косараджу
Всі можливі вузли відвідані.
Слайд 87
![Алгоритм Косараджу Забираємо з черги 9,12,10, вони всі відвідані. Забираємо 6 і відвідуємо.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-86.jpg)
Алгоритм Косараджу
Забираємо з черги 9,12,10, вони всі відвідані.
Забираємо 6 і відвідуємо.
Слайд 88
![Алгоритм Косараджу Відвідати 8.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-87.jpg)
Алгоритм Косараджу
Відвідати 8.
Слайд 89
![Алгоритм Косараджу Отримали ще один СЗК](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-88.jpg)
Алгоритм Косараджу
Отримали ще один СЗК
Слайд 90
![Алгоритм Косараджу Забираємо з черги 7 і відвідуємо. Цей елемент один утворює СЗК.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-89.jpg)
Алгоритм Косараджу
Забираємо з черги 7 і відвідуємо.
Цей елемент один утворює СЗК.
Слайд 91
![Алгоритм Косараджу Забираємо з черги 8. Воно відвідано, закінчили роботу.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-90.jpg)
Алгоритм Косараджу
Забираємо з черги 8. Воно відвідано, закінчили роботу.
Слайд 92
![Алгоритм Косараджу Алгоритм Косараджу обчислює СЗКти орграфа за час пропорційний](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-91.jpg)
Алгоритм Косараджу
Алгоритм Косараджу обчислює СЗКти орграфа за час пропорційний E+V.
Вузьке місце
– запуск DFS двічі і обрахунок транспонованого графу.
В принципі можна усунути.
Реалізація дуже проста.
Необхідно змінити пару стрічок.
Слайд 93
![Алгоритм Косараджу public class CC{ private boolean marked[]; private int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-92.jpg)
Алгоритм Косараджу
public class CC{
private boolean marked[];
private int[] id;
private int count;
public CC(Graph
G){
marked = new boolean[G.V()];
id = new int[G.V()];
for (int v = 0; v < G.V(); v++){
if (!marked[v]){
dfs(G, v);
count++;
}
}
}
private void dfs(Graph G, int v){
marked[v] = true;
id[v] = count;
for (int w : G.adj(v))
if (!marked[w])
dfs(G, w);
}
public boolean connected(int v, int w){ return id[v] == id[w]; }
}
Слайд 94
![Алгоритм Косараджу public class KosarajuSharirSCC{ private boolean marked[]; private int[]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/20718/slide-93.jpg)
Алгоритм Косараджу
public class KosarajuSharirSCC{
private boolean marked[];
private int[] id;
private int count;
public KosarajuSharirSCC(Digraph
G){
marked = new boolean[G.V()];
id = new int[G.V()];
DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
for (int v : dfs.reversePost()){
if (!marked[v]){
dfs(G, v);
count++;
}
}
}
private void dfs(Digraph G, int v){
marked[v] = true;
id[v] = count;
for (int w : G.adj(v))
if (!marked[w])
dfs(G, w);
}
public boolean stronglyConnected(int v, int w){ return id[v] == id[w]; }
}