DFS, BFS

새로 배운 것만 정리했다.

파이썬에서는 그래프를 인접 행렬과 인접 리스트로 표현한다.

1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현
   -여기서는 연결되어 있지 않은 노드들은 값을 무한으로 준다. 자기 자신으로의 방향은 값이 0.

2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현
   -모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
   인접 리스트는 연결 리스트라는 가죠구조를 이용하는데, 파이썬에서는 그냥 2차원 리스트를 이용하면 된다고 한다.

두 방식의 차이점?

• 메모리 측면: 인접 행렬은 모든 관계를 저장하므로 노드 개수가 많아질수록 메모리가 낭비된다. 하지만 인접 리스트 방식은 연결된 정보만을 저장하기에 메모리 측면에서 효율적이다.
• 정보를 얻는 속도: 인접 리스트 방식이 인접 행렬 방식에 비해 특정 두 노드의 연결 여부에 대한 정보를 얻을 때 더 느리다. 연결된 데이터를 하나씩 확인해야 하기 때문이다.

DFS 구현: 스택을 사용하기 때문에 재귀함수를 이용하면 간단히 구현할 수 있다

#DFS

graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
visited = [False] * 9

def DFS(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            DFS(graph, i, visited)

DFS(graph, 1, visited)

BFS 구현: 큐를 사용하면 된다. 먼저 들어온 것부터 나가게 되므로 가까운 노드부터 탐색할 수 있기 때문이다. 또한 일반적으로 DFS보다 수행시간이 좋다고 한다.

+재귀함수로 DFS를 구현하면 컴퓨터 시스템의 동작 특정상 실제 프로그램의 수행시간이 느려질 수 있기 때문에 스택 라이브러리를 사용하는 테크닉을 사용할 때도 있다고 한다.

#BFS

from collections import deque

def BFS(graph, v, visited):
    queue = deque([v])
    visited[v] = True
    while queue:
        a = queue.popleft()
        print(a, end = ' ')
        for i in graph[a]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]
visited = [False] * 9

BFS(graph, 1, visited)