[Algorithm] Graph - DFS(깊이우선탐색)/BFS(너비우선탐색)

- Graph

현상이나 사물을 정점 vertex과 간선 edge으로 표현한 것. 

: Graph G = (V, E)

두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 

 

- 그래프와 트리의 차이

트리는 사이클을 허용하지 않는 그래프

 

- 그래프의 표현

1. N x N 행렬로 표현

2. N개의 연결 리스트로 표현

 

- 그래프 탐색 대표적 두 가지 방법

1. DFS 너비우선탐색

2. BFS 깊이우선탐색

 

 

- DFS

스택 자료구조를 이용한다.

 

- 과정

0. 모든 노드를 not visited로 표시한다. 

1. 탐색 시작 노드를 스택에 삽입하고, visited로 표시한다. 

2. 스택의 최상단 노드에 not visited인 인접 노드가 있으면 스택에 넣고 visited로 표시한다. 

    not visited인 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 1, 2번 과정을 반복한다.

 

 

- BFS

큐 자료구조를 이용한다.

 

- 과정

0. 모든 노드를 not visited로 표시한다. 

1. 탐색 시작 노드를 큐에 삽입하고 visited로 표시한다. 

2. 첫번째 노드를 deque하고

    not visited 상태인 인접 노드들을 모두 큐에 add. add한 인접 노드들을 모두 visited로 표시한다. (순서 무관)

3. 1, 2번 과정을 반복한다.