그래프(Graph)

• 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조
• 연결 관계에 초점이 맞춰져 있음

- 노드(Node): 연결 관계를 가진 각 데이터. 정점(Vertex)이라고도 함
- 간선(Edge): 노드 간의 관계를 표시한 선.
- 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

- 그래프 종류 
  1) 유방향 그래프(Directed Graph): 방향이 있는 간선을 가짐. 간선은 단방향 관계를 나타내며, 
							    각 간선은 한 방향으로만 진행할 수 있음
  2) 무방향 그래프(Undirected Graph):  방향이 없는 간선을 가짐
  
- 컴퓨터에서 표현하는 방법
  1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
  2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3   
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현하면 다음과 같습니다!
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2. 이번에는 인접 리스트로 표현해보겠습니다!
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

# 두 방식의 차이 (시간 vs 공간)
인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있습니다.
그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 합니다.

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 합니다.
따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 합니다.
대신 모든 조합의 연결 여부를 저장할 필요가 없으니  O(노드 + 간선) 만큼의 공간을 사용하면 됩니다.

DFS & BFS

• 자료의 검색, 트리나 그래프를 탐색하는 방법
• 정렬된 데이터를 이분 탐색하는 것처럼 효율적인 방법이 있는 반면, 모든 경우의 수를 전부 탐색해야하는 경우 사용
• DFS는 끝까지 파고드는 것, BFS는 갈라진 모든 경우의 수를 탐색해보고 오는 것

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

• 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색
• 그래프의 최대 깊이 만큼의 공간을 요구(공간을 적게 쓰지만 최단경로를 탐색하기 어려움)

1. 루트 노드부터 시작
2. 현재 방문한 노드를 visited에 추가
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문
4. 2부터 반복(재귀)

Q. 인접 리스트가 주어질 때, 모든 노드를 DFS 순서대로 방문하시오.

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

# 1. 루트 노드인 1부터 탐색
# 2. 현재 방문 노드를 visited_array에 추가
# 3. 현재 방문 노드와 인접 노드 중 방문하지 않은 노드에 방문

def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:
        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] 이 출력되어야 합니다!

에러

재귀함수를 통해서는 무한정 깊어지는 노드가 있는 경우 에러가 생길 수 있음!

재귀 대신 스택을 이용하여 문제풀기(순서는 달라질 수 있음)

1. 루트 노드를 스택에 넣기
2. 현재 스택의 노드를 빼서 visited 에 추가한
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가
4. 2부터 반복
5. 스택이 비면 탐색을 종료

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]			# 1
    visited = []

    while stack:
        cur_node = stack.pop()		# 1  -> stack = []					# 9	
        visited.append(cur_node)	# 1  -> visited = [1]
        for adjacent_node in adjacent_graph[cur_node]:  # 2, 5, 9 		# 10
            if adjacent_node not in visited:
                stack.append(adjacent_node)  # -> stack = [2, 5, 9]		# [2, 5, 10]

    return visited

print(dfs_stack(graph, 1))  # 1 이 시작노드
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

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

• 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법
• 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용
• 최단 경로를 쉽게 찾을 수 있지만 모든 분기 수를 다 저장하다보니 공간과 시간이 많이 쓰임

BFS 는 현재 인접한 노드 먼저 방문해야 함
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
가장 처음에 넣은 노드를 꺼내서 탐색하면 됨 

가장 처음에 넣은 노드들..? → 큐를 이용하면 BFS 를 구현!

1. 루트 노드를 큐에 넣음
2. 현재 큐의 노드를 빼서 visited 에 추가
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가
4. 2부터 반복
5. 큐가 비면 탐색을 종료

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

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

    while queue:			 # 앞에서 뽑아오겠다
        cur_node = queue.pop(0)    				# 1, queue = []		2
        visited.append(cur_node)				# visited = [1]		[1, 2]
        for adj_node in adj_graph[cur_node]:	# 2, 3, 4			1, 5
            if adj_node not in visited:
                queue.append(adj_node)			# [2, 3, 4]			[3, 4, 5]

    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]