[Algorithm] DFS와 BFS || Depth-First & Breadth-First Search

❕ 인접 행렬

인접 행렬은(Adjacency Matrix)로 2차원 배열을 이용하여 그래프의 연결 관계를 표현하는 방식이다.

INF = 999999999

graph = [
		[0, 7, 5],
		[7, 0, INF],
		[5, INF, 0]
]

print(graph)

 

❕ 인접 리스트(Adjacency List)

리스트로 그래프의 연결 관계 표현하는 방식

graph = [ [] for _ in range(3)]

# 노드와 거리
graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

print(graph)

 
메모리 : 인접 리스트 win
속도 : 인접 행렬 win
 

📌DFS (스택)

DFS(Depth-First Search), 깊은 부분을 우선적으로 탐색하는 알고리즘.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
반복.

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(graph, 1, visited)

📌BFS (큐)

BFS(Breadth First Search), 가까운 노드부터 탐색하는 알고리즘
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
반복.

from collections import deque

def bfs(graph, start, visited):
			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(graph, 1, visited)

 
 
출처) 이것이 코딩테스트다 with Python