DFS/BFS

그래프 표현 방식

• 인접 행렬 방식

INF = 99999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

• 인접 리스트 방식

	# 행이 3개인 2차원 리스트로 인접 리스트 표현
    graph = [[] for _ in range(3)]
    
    # 노드 0에 연결된 노드 정보 저장(노드, 거리)
    graph[0].append((1,7))
    graph[0].append((2,5))
    
    # 노드 1에 연결된 노드 정보 저장(노드, 거리)
    graph[1].append((0,7))
    
    # 노드 2에 연결된 노드 정보 저장(노드, 거리)
    graph[2].append((0,5))
    
    print(graph)

둘의 차이

• 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비, 인접 리스트 방식은 메모리를 효율적으로 사용
• 인접 리스트 방식은 두 노드가 연결돼 있는지에 대한 정보를 얻는 속도가 느림

DFS

• 작동방식
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

# DFS 메서드 정의
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs[graph, i, visited)
            
# 각 노드가 연결된 정보를 리스트 자료형 표현
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형 표현
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

1 2 7 6 8 3 4 5 순으로 방문

BFS

• 작동방식
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	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 함수 호출
bfs(graph, 1, visited)

1 2 3 8 7 4 5 6