<algorithm> 3. DFS

DFS

  깊이 우선 탐색으로 갈 길을 정해서 갈 수 없을 때 까지 갔다가 돌아오는 것을 의미한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import java.util.ArrayList;     public class MyDfs {       boolean[] visited;     ArrayList<MyEdge>[] graph;          public MyDfs(ArrayList<MyEdge>[] graph) {         System.out.println("됨?");                  this.graph = graph;              visited=new boolean[graph.length];                  for(int i=0;i<graph.length;i++){             visited[i]=false;         }         for(int i=0;i<graph.length;i++){             if(!visited[i]){                 dfs(i);             }         }          }     public void dfs(int i) {            visited[i]=true;                        System.out.print(" "+i+"->");                     for(MyEdge e:graph[i]){                if(!visited[e.adj]){                    dfs(e.adj);                }               }         }          }   class MyEdge {       int adj;       public MyEdge(int adj) {         super();         this.adj = adj;     } } Colored by Color Scripter

cs

정리

재귀가 들어가서 처음에는 복잡하게 보일 수 있지만 간단하다.

 방문하지 않은 정점-> 방문(true) ->출력 -> 방문한 정점의 인접 정점 탐색 -> 재귀