1.DFS

1.1 개념

1.1.1 글

• Depth First Search의 약자
• 그래프(graph, 선과 노드로 표시된 것)에서 깊이를 우선하여 노드를 찾는 방법

1.1.2 그림

• 찾는 순서: 1 → 2 → 5 → 9 → 3 → 6 → 10 → 7 → 4 → 8
  

1.2 예시

1.2.1 문제

• 위와 같은 그래프에서 DFS 형식으로 노드 접근하기

1.2.2 방법

1.2.2.1 재귀함수

① 개념: 루트노드에서 간선으로 연결된 노드를 재귀함수로 접근하는 방법
② 코드:

graph = { 						# 그래프를 코드로 구현함
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] 						# 방문한 노드를 담을 리스트


def dfs_recursion(adjacent_graph, cur_node, visited_array):

    visited_array.append(cur_node) 			# 1. 현재 노드를 방문한 노드에 담는다.
    for adjacent_node in adjacent_graph[cur_node]: 	# 2. 그래프의 주변 노드 
        if adjacent_node not in visited_array: 		# 3. 중 방문하지 않는 곳에 대해서
            dfs_recursion(adjacent_graph, adjacent_node, visited_array) # 4. 재귀함수를 이용하라

1.2.2.2 stack

① 개념: 루트노드에서 간선으로 연결된 노드를 stack을 사용해 접근하는 방법
② 코드:

graph = { 						# 그래프를 코드로 구현함
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] 						# 방문한 노드를 담을 리스트


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node] 				# 1. stack 변수에 시작할 노드를 입력한다.
    visited = [] 					# 2. 방문한 곳을 담을 변수를 선언한다.

    while stack: # 3. stack이 빌 때까지
        current_node = stack.pop() 			# 4. stack의 마지막 인자를 뽑아
        visited.append(current_node) 			# 5. 방문한 곳으로 이동시키고
        for adjacent_node in adjacent_graph[current_node]: # 6. 그래프 중 뽑힌 노드의 주변 노드 중에서
            if adjacent_node not in visited:		   # 7. 만약 방문한 곳이 아니라면
                stack.append(adjacent_node) 		   # 8. stack 변수에 추가한다.

    return visited

2.BFS

2.1 개념

2.1.1 글

• Breadth First Search의 약자
• 그래프(graph, 선과 노드로 표시된 것)에서 폭을 우선하여 노드를 찾는 방법

2.1.2 그림

• 찾는 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
  

2.2 예시

2.2.1 문제

• 위와 같은 그래프에서 BFS 형식으로 노드 접근하기

2.2.2 방법

① 개념: 루트노드에서 간선으로 연결된 노드를 queue을 사용해 접근하는 방법
② 코드:

graph = { 						# 그래프를 코드로 구현함
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = [] 						# 방문한 노드를 담을 리스트


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node] 				# 1. stack 변수에 시작할 노드를 입력한다.
    visited = [] 					# 2. 방문한 곳을 담을 변수를 선언한다.

    while stack: # 3. stack이 빌 때까지
        current_node = stack.pop(0) 			# 4. stack의 첫번째 인자를 뽑아
        visited.append(current_node) 			# 5. 방문한 곳으로 이동시키고
        for adjacent_node in adjacent_graph[current_node]: # 6. 그래프 중 뽑힌 노드의 주변 노드 중에서
            if adjacent_node not in visited:		   # 7. 만약 방문한 곳이 아니라면
                stack.append(adjacent_node) 		   # 8. stack 변수에 추가한다.

    return visited