Вступ до алгоритму DFS
DFS відомий як алгоритм глибинного першого пошуку, який забезпечує кроки для переходу кожного вузла графіка, не повторюючи жодного вузла. Цей алгоритм такий самий, як обхід першої глибини для дерева, але відрізняється підтримкою булевого сигналу, щоб перевірити, чи вже відвіданий вузол чи ні. Це важливо для обходу графіків, оскільки в графіку також існують цикли. У цьому алгоритмі підтримується стек для зберігання призупинених вузлів під час проходження. Він названий так тому, що ми спочатку подорожуємо до глибини кожного сусіднього вузла, а потім продовжуємо обхід іншого сусіднього вузла.
Поясніть алгоритм DFS
Цей алгоритм суперечить алгоритму BFS, де відвідуються всі сусідні вузли, а за ними сусіди до сусідніх вузлів. Він починає досліджувати графік з одного вузла та досліджує його глибину перед тим, як повернутись назад. У цьому алгоритмі розглядаються дві речі:
- Відвідування вершини: вибір вершини чи вузла графіка для проходження.
- Дослідження вершини: обхід усіх вузлів, прилеглих до цієї вершини.
Псевдо-код для глибини першого пошуку :
proc DFS_implement(G, v):
let St be a stack
St.push(v)
while St has elements
v = St.pop()
if v is not labeled as visited:
label v as visited
for all edge v to w in G.adjacentEdges(v) do
St.push(w)
Лінійний обхід також існує для DFS, який можна реалізувати трьома способами:
- Замовлення
- В порядку
- PostOrder
Зворотний порядок є дуже корисним способом проходження та використовується для топологічного сортування, а також для різних аналізів. Зберігається також стек для зберігання вузлів, розвідка яких ще триває.
Перехід графіка в DFS
У DFS виконуються наведені нижче кроки для переміщення графіка. Наприклад, заданий графік розпочнемо обхід з 1:
| Стек | Послідовність обходу | Дерево, що охоплює |
| 1 |  |
|
 | 1, 4 |  |
 | 1, 4, 3 |  |
 | 1, 4, 3, 10 |  |
 | 1, 4, 3, 10, 9 |  |
 | 1, 4, 3, 10, 9, 2 |  |
 | 1, 4, 3, 10, 9, 2, 8 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
 | 1, 4, 3, 10, 9, 2, 8, 7, 5, 6 |  |
Пояснення до алгоритму DFS
Нижче наведено кроки до алгоритму DFS з перевагами та недоліками:
Крок 1 : Вузол 1 відвідується і додається до послідовності, а також до дерева, що охоплює.
Крок 2: Досліджуються суміжні вузли 1, тобто 4, таким чином, 1 висувається в стек і 4 висувається в послідовність, а також вперед дерево.
Крок 3: Один з сусідніх вузлів 4 досліджується, і таким чином 4 висуваються до стека, а 3 входить у дерево послідовності та охоплення.
Крок 4: Суміжні вузли з 3 досліджуються шляхом натискання на стек і 10 входить у послідовність. Оскільки немає сусіднього вузла до 10, таким чином 3 вискакують із стека.
Крок 5: Досліджується ще один сусідній вузол з 3, і 3 висувається на стек, і 9 відвідується. Жоден сусідній вузол 9, таким чином, 3 не вискакує, і останній сусідній вузол 3, тобто 2, відвідується.
Аналогічний процес дотримується для всіх вузлів, поки стек не стане порожнім, що вказує на стан зупинки для алгоритму переходу. - -> пунктирними лініями на дереві, що охоплює, відносяться до задніх ребер, наявних у графі.
Таким чином, всі вузли на графіку проходять без повторення жодного з вузлів.
Переваги і недоліки
- Переваги: Ця потреба в пам'яті для цього алгоритму дуже менша. Менша складність простору та часу, ніж BFS.
- Недоліки: рішення не гарантується. Топологічне сортування. Пошук мостів графіка.
Приклад реалізації алгоритму DFS
Нижче наведено приклад реалізації алгоритму DFS:
Код:
import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)import java.util.Stack;
public class DepthFirstSearch (
static void depthFirstSearch(int()() matrix, int source)(
boolean() visited = new boolean (matrix.length);
visited(source-1) = true;
Stack stack = new Stack();
stack.push(source);
int i, x;
System.out.println("Depth of first order is");
System.out.println(source);
while(!stack.isEmpty())(
x= stack.pop();
for(i=0;i if(matrix(x-1)(i) == 1 && visited(i) == false)(
stack.push(x);
visited(i)=true;
System.out.println(i+1);
x=i+1;
i=-1;
)
)
)
)
public static void main(String() args)(
int vertices=5;
int()() mymatrix = new int(vertices)(vertices);
for(int i=0;i for(int j=0;j mymatrix(i)(j)= i+j;
)
)
depthFirstSearch(mymatrix, 5);
)
)
Вихід:
Пояснення до вищезгаданої програми: Ми склали графік, що містить 5 вершин (0, 1, 2, 3, 4) і використовували відвіданий масив для відстеження всіх відвіданих вершин. Потім для кожного вузла, суміжні вузли якого існують однаковий алгоритм, повторюється, поки всі вузли не будуть відвідані. Потім алгоритм повертається до виклику вершини і виводить його зі стека.
Висновок
Потреба в пам'яті цього графіка менша порівняно з BFS, оскільки для підтримання потрібен лише один стек. У результаті генерується дерево, що охоплює DFS, і послідовність обходу, але не є постійною. Можлива множинна послідовність обходу залежно від обраної вершини початку та вершини розвідки.
Рекомендовані статті
Це посібник з алгоритму DFS. Тут ми обговорюємо покрокове пояснення, переводимо графік у форматі таблиці з перевагами та недоліками. Ви також можете ознайомитись з іншими нашими пов’язаними статтями, щоб дізнатися більше -
- Що таке HDFS?
- Алгоритми глибокого навчання
- Команди HDFS
- Алгоритм SHA