Увод у ДФС алгоритам
ДФС је познат као алгоритам дубинске прве претраге који пружа кораке за прелазак сваког чвора графикона без понављања чвора. Овај алгоритам је исти као и прва дубина дубине за дрво, али се разликује у одржавању Боолеан-а да би се проверило да ли је чвор већ посећен или не. Ово је важно за кретање графова, јер у графу постоје и циклуси. У овом алгоритму се одржава сноп за чување суспендираних чворова током проласка. Назван је тако по томе што прво путујемо до дубине сваког суседног чвора, а затим настављамо са преласком другог суседног чвора.
Објасните ДФС алгоритам
Овај алгоритам је у супротности са БФС алгоритмом где посећују све суседне чворове, а затим следе суседи до суседних чворова. Почиње истраживање графикона са једног чвора и истражује његову дубину пре него што се повуче назад. Две ствари су узете у обзир у овом алгоритму:
- Посета вертеку: Избор вертекса или чвора графикона за прелазак.
- Истраживање краљежнице: Прелазак свих чворова поред те краљежнице.
Псеудо код за дубину прве претраге :
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)
Линеарна траверза постоји и за ДФС која се може имплементирати на 3 начина:
- Предбиљежи
- У реду
- ПостОрдер
Обрнути постордер је врло користан начин за кретање и користи се у тополошком сортирању као и у разним анализама. Такође се одржава сноп за чување чворова чије је истраживање још увек у току.
Прелаз графикона у ДФС-у
У ДФС-у следећи кораци се крећу да би се прешао граф. На пример, дани граф, почнимо са кретањем од 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 |  |
Објашњење алгоритму ДФС
Испод су кораци ка ДФС алгоритму са предностима и недостацима:
1. корак: Посећује се чвор 1 и додаје се низу као и стаблу које се протеже.
Корак 2: Испитују се суседни чворови од 1 који је 4, тако да се 1 гурне у слој и 4 се гурне у редослед као и распоређено стабло.
Корак 3: Истражује се један од суседних чворова са 4 и тако се 4 гура у сноп, а 3 улази у стабло редоследа и распона.
Корак 4: Суседни чворови од 3 истражују се притиском на сноп и 10 улази у низ. Како нема суседног чвора 10, тако ће 3 искочити из снопа.
Корак 5: Истражује се други суседни чвор од 3 и 3 се гура у сноп и посећује се 9. Ниједан суседни чвор од 9 није искочен, а последњи суседни чвор од 3, тј. 2 је посећен.
Сличан поступак се прати за све чворове док сноп не постане празан што указује на стање заустављања алгоритма за кретање. - -> испрекидане линије на дрвету које се протеже односе се на задње ивице на графу.
На овај начин, сви чворови на графикону су попречни без понављања било којег чвора.
Предности и мане
- Предности: Ова меморијска потреба за овим алгоритмом је врло мања. Мања сложеност простора и времена у односу на БФС.
- Недостаци: Решење није загарантовано Апликације. Тополошка сортирање. Проналажење мостова графикона.
Пример примене ДФС алгоритма
Испод је пример примене ДФС алгоритма:
Шифра:
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) и користили посјећени низ да бисмо пратили све посјећене врхове. Затим се за сваки чвор чији суседни чворови постоје исти алгоритам понавља све док се сви чворови не посете. Тада се алгоритам враћа на вертек позивања и убацује га из снопа.
Закључак
Потребна меморија овог графикона је мања у поређењу са БФС-ом јер је потребан само један сноп. ДФС распона стабла и редослед кретања се генеришу као резултат, али нису константни. Могуће је вишеструко кретање које се креће у зависности од изабране почетне и вертикалне верзије.
Препоручени чланци
Ово је водич за ДФС алгоритам. Овде смо расправљали о корак по корак објашњењем, прешли граф у формату табеле са предностима и недостацима. Можете и да прођете кроз остале сродне чланке да бисте сазнали више -
- Шта је ХДФС?
- Алгоритми дубоког учења
- ХДФС команде
- СХА Алгоритам