DFS(Depth-First Search),BFS(Breadth-First Search) 개념 정리 - 자료구조 복습

어쨌든 마지막 약자가 Searching 이라 검색 부분에 있을줄 알았는데 자료구조 그래프(1)(2)에 있었다.

호달달..

 

그래프란?

모델을 수학적으로 나타내고, → 컴퓨터로 옮겨서 → 그래프라는 자료구조로 나타내는 방식 

- 그래프는 정점(vertex)와 에지(edge)의 집합으로 구성

- 정점 집합과 에치 집합의 순서쌍

 

쉽게 말하면 정점은 꼭지점이고 에지는 꼭짓점을 이은 선

 

정점이 4개이고 edge도 4개인 그래프

 

 

 

 

 

 

그래프 상에서의 정의는 이렇지만 정점과 에지의 개념도 살펴볼 필요가 있다.

 

정점(Vertex)

- 여러가지 특성을 가질 수 있는 객체를 의미

- 노드(node)로 불리는 것이 더 정확

- V(G): 그래프 G의 정점들의 집합 ex) V(위의 그래프)=0,1,2,3

 

에지(Edge)

- 정점들간의 관계를 의미

- 간선 또는 링크(link)라고도 부름 //얘는 보통 edge로 부르심

- E(G): 그래프 G의 에지들의 집합

- 에지는 방향성이 있기도하고 없기도 함( 상황따라)

 

그래프의 사용예시

 

 

 

깊이 우선 탐색(DFS: depth-first search)

 

-어떤 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌ㅇ와서 그곳에서 부터 다른방향으로 다시 탐색

-갈림길로 돌아가기 위해서는 스택이 필요

 

너비우선 탐색

-시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점은 나중에 방문하는 운행 방법

- 큐를 사용하여 구현 가능

 

 

*DFS 인접행렬 알고리즘

*DFS 인접리스트 알고리즘