11.14 알고리즘 강의: 그래프/ DFS && BFS

1. 그래프 : 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 자료구조

노드(Node): 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)이라고도 한다.

간선(Edge): 노드 간의 관계를 표시한 선.

인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

 

종류

- 유 방향 그래프: 일방통행 그래프, 각 간선은 한 방향으로만 진행할 수 있다

- 무 방향 그래프: 방향이 없는 그래프

 

표현 방법 ~ 여기서도 배열/링크드 리스트

인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결관계를 표현

인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결관계를 표현

 

*인접 행렬은 시간이 더 효율적이다 and 인접 리스트는 공간이 더 효율적이다

~ 실무에 대한 궁금증 : 시간이 더 효율적인 인접 행렬을 더 많이 사용할까?

 

2. DFS && BFS

DFS(알고리즘 깊이 우선 탐색, Depth First Search)

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 끝까지 탐색한 후 처음으로 복귀하여 다음 노드(단계)를 재귀적으로 탐색

BFS(알고리즘 너비 우선 탐색, Breath First Search)

시작 노드를 줌심으로 인접한 모든 노드를 우선 탐색한 후 다음 노드(단계)를 탐색하는 방법

 

DFS, BFS의 대표적인 사례: 알파고

 

DFS: 그래프의 최대 깊이만큼의 공간을 요구하므로 공간 사용량이 적으나, 최단 경로를 찾기 어렵다

출처: 강의자료. 가장 깊이까지 탐색한 후 모두 탐색했다면, 거슬러 올라간다

DFS 구현 : 재귀함수

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 = []

#1. 시작 노드(루트 노드)인 1부터 탐색합니다.
#2. 현재 방문한 노드를 visited_array에 추가합니다.
#3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문합니다.

#visited_array = [1]
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph:
        if adjacent_node not in visited_array: #탈출 조건: 탐색을 했다면 추가하지 않는다
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

DFS 구현 : 스택 **VS BFS = DFS vs BFS : 스택 VS 큐

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []
    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited

print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

 

BFS: 모든 인접 노드를 우선 탐색하므로 최단 경로를 쉽게 파악할 수 있다. 그러나 모든 인접 노드와 경로를 파악해야 하므로 시간 및 공간 사용량이 많다

 

BFS 구현 : 큐 **VS DFS = DFS vs BFS : 스택 VS 큐

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []

    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)

    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!