DFS & BFS

그래프 기본 개념(+트리)

Graph는 일련의 노드(node, vertex, 정점) 집합 V와 엣지(edge, 간선) 집합 E로 구성된 자료구조

보통 정점에는 Data가 들어가고, 간선은 그 Data들 간의 관계를 표현( G = (V, E) )

간선으로 연결된 두 정점은 관계가 있다고 말할 수 있으며, 이를 인접(Adjacent)하다고 한다.

→ 그래프의 구성 요소

• vertex(정점)
• edge(간선)

 

<트리와의 차이>

 

트리는 사이클이 존재하면 X.

즉, 그래프가 더 큰 범위

그래프의 특정한 경우가 트리인 것!

반대로 그래프의 모든 정점이 각각 연결되어있다면 - 완전그래프

그래프의 종류

• 방향 그래프 VS 무방향 그래프
• 가중치 그래프
• 완전 그래프
• 부분 그래프 vs 신장 그래프(spanning tree)

*degree

• 방향 그래프 : in-degree+out-degree
• 무방향 그래프 : 간선 수 * 2

1. 인접 행렬
   • 장점: 두 노드의 간선의 존재 여부를 바로 알 수 있음
   • 단점: 모든 관계를 기록함으로 노드의 개수가 많을 수록 불필요한 메모리 낭비가 일어남
2. 인접 리스트
   • 장점: 연결된 것들만 기록함 / 어떤 노드의 인접한 노드들을 바로 알 수 있음
   • 단점: 두 노드가 연결되어 있는지 확인이 인접 행렬보다 느림

→ 간선이 많이 존재하는 밀집 그래프 : 인접 행렬

→ 간선이 적은 희소 그래프 : 인접 리스트

DFS

DFS(깊이 우선 탐색), Depth-First Search

깊이 우선 탐색은 앞선 너비 우선 탐색과는 달리 Root Node부터 시작하여 가장 깊은 곳까지 탐색한 후 돌아서 모든 정점을 방문하는 방법이다.

 

위의 그림과 같이 깊이 우선 탐색에서는 한 쪽 노드를 선택하면 그 노드로부터의 가장 깊은 곳까지 탐색한 후 동일 높이의 노드를 탐색한다.

 

DFS를 구현하기 위해서는 후입선출의 자료구조인 스택을 이용한다.기본 원리는 정점을 처음 방문할 때 스택에 삽입하고, 해당 스택에서 방문할 수 있는 vertex를 탐색하며 방문한 다음에, 방문할 수 있는 vertex가 더이상 존재하지 않을 때 스택에서 제거해주는 것이다.

 

구현에서는 스택 자료구조를 직접 이용해줄 수도 있고, 재귀 호출을 통해 스택을 간접적으로 사용해줄 수도 있다.

BFS에 비해 저장공간의 필요성이 적고, 찾아야 할 노드가 깊은 단계에 있을 수록 유리하다.

 

BFS

BFS(너비 우선 탐색), Breadth-First Search

Root Node인 0부터 출발하여 Root로부터 인접한 Node들부터 탐색하고, 점점 탐색 범위를 넓혀나가고 있다. 이런 점에서 이러한 그래프 탐색 방식을 너비 우선 탐색이라고 부른다.

 

BFS를 구현하기 위해서는 Queue를 이용할 수 있다.대상이 무방향 그래프라고 가정할 때, 기본 원리는 정점을 처음으로 방문할 때 큐에 삽입하고, 큐에정점을 하나씩 Dequeue 하면서 그에 인접한 정점들을 큐로 삽입하는 식으로 진행한다.

 

이는 큐가 빌 때까지 지속하며, 새로운 원소를 큐에 삽입할 때에는 이미 방문한 정점이 아닌 경우에만 삽입해 준다.