DFS,BFS

• DFS ( Depth First Search )

--그래프 탐색의 한 종류

--깊이 우선 탐색 이라고 부름.

--루트 노드의 임의의 노드에서 시작하여 , 

  최대로 진입할 수 있는 깊이까지 탐색한 후 다른 노드로 탐색하는 방식.

--Stack을 사용하여 데이터를 탐색.

 

장점 -- 현 경로들의 노드들만 기억하면 되므로, 저장공간 수요가 비교적 적음

        -- 목표노드가 깊은단계있을경우 해를 빨리 구할수 있음.

단점 -- 해가 없는 경로가 깊을경우 탐색이 오래걸림.

        -- 얻어진 해가 최단경로가 된다는 보장이없음.

(8) 번을 다시탐색하는게아니라, (8) 번을통해 6으로접근.

--인접행렬 ( Adjacency Martix ) 

--인접리스트

 

• BFS ( Breadth First Search ) 

-- 너비 우선 탐색이라고 부름

-- 루트 노드나 임의의 노드에서 시작하여

   인접한 노드를 먼저 확인한 후 다음 depth를 탐색

-- Queue ( ex.선착순,파이프구조 ) 를 사용하여 데이터를 탐색.  

      Queue <--> Stack (쌓는구조)

-- FIFO 원칙으로 탐색 . 

 

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

 

 

 

 

 

 

 

어라운드 허브 스튜디오 - Around Hub Studio