DFS,BFS

DFS & BFS

DFS

깊이 우선 탐색 (Depth First Search) 방식으로 LIFO인 Stack를 활용해서 순차적으로 탐색을 진행하게 된다.

Code

def dfs(vertex):
  visited[vertex]=True
  print(vertex,end=" ")

  for adj_vertex in graph[vertex]:
    if not visited[adj_vertex]:
      dfs(adj_vertex)

위와 같이 Adjacency List로 구현된 Graph에서 DFS 수행시 모든 정점과 간선을 한번씩 검사를 진행하게 되므로 시간복잡도는 O(V+E) 이다 다만, Adjacency Matrix으로 구현된 경우 DFS 수행시 모든 정점에 대해 다른 나머지 정점을 모두 검사하게 되므로 이때는 시간 복잡도가 O(V²) 이다.

BFS

너비 우선 탐색(Breadth First Search) 방식으로 LIFO인 Stack를 활용해서 순차적으로 탐색을 진행하게 된다.

Code

queue=deque()
while queue:
  vertex=queue.popleft()
  print(vertex,end=" ")

  for adj_vertex in graph[vertex]:
    if not visited[adj_vertex]:
      queue.append(adj_vertex)
      visited[adj_vertex]=True

BFS의 시간 복잡도는 DFS와 동일하다.

Adjacency List: O(V+E)

Adjacency Matrix: O(V²)

Question Types

주로 나오는 빈출 유형으로는 경로 존재 여부, 인접해 있는 그룹의 개수 찾기, 미로 찾기, 등의 유형이 있다.