DFS & BFS

그래프

정점과 간선으로 이루어져있는 자료구조로, 정점 간의 연결 관계가 간선을 이용해 표현됨
인접 행렬 또는 인접 리스트로 표현할 수 있다.

인접행렬

두 정점 i, j 가 연결관계에 있다면 graph[i][j] 값을 1로, 그렇지 않다면 graph[i][j] 값을 0으로 정의해 표현한다.

양방향 그래프라면 인접 행렬이 대칭인 모양이 되며, 단방향 그래프라면 대칭 X
그래프에서 정점의 수를 V, 간선의 수를 E라고 했을 때 인접 행렬 이용시 공간복잡도는 $O(V^2)$

인접리스트

V개의 동적배열을 만들어 관리해야 함. i번째 정점에 해당하는 동적 배열을 graph[i] 라고 한다면, graph[i] 에 해당하는 동적 배열에 정점 i에 연결된 모든 정점 번호가 들어가야 함.

인접리스트의 경우, V개의 동적배열을 관리하는 리스트 1개와, 각 간선별로 정점이 2개씩 동적 배열에 각각 추가되므로 (1번 정점과 3번 정점이 연결되어 있을 경우, 1→3, 3→1) 공간복잡도는 $O(V+E)$

BFS (인접행렬)

특정 정점에서 시작하여 갈 수 있는 곳까지 쭉 따라 들어갔다가 더 이상 갈 곳이 없으면 빠져나오는 방식의 그래프 탐색 방법, **깊이 우선 탐색**이라고 불림

💡 1→2→5→3→4→6→7

****인접행렬로 방문 구현: graph라는 2차원 배열을 만들어 두 정점이 연결되어 있다면 1, 아니라면 0****

def dfs(vertex):
	for curr_v in range(1, vertices_num + 1):
		if graph[vertex][curr_v] and not visited[curr_v]:
			print(curr_v)
			**visite[curr_v] = True**
			dfs(curr_v)

그래프 탐색 알고리즘의 2가지 대원칙

1. 시작점으로부터 연결된 모든 정점을 전부 방문해야 한다.
2. 이미 방문한 정점은 다시는 방문하지 않는다.

vertices_num = 7
edges_num = 6

graph = [
	[0 for _ in range(vertices_num + 1)]
	for _ in range(vertices_num + 1)
]

visited = [False for _ in range(vertices_num + 1)]

print(f"처음: {visited}")

def dfs(vertex):
	# curr_v = 1, 2, 3, 4, 5, 6, 7 까지
	for curr_v in range(1, vertices_num + 1):
		print(f"* current vertex: [{vertex}][{curr_v}]")
		if graph[vertex][curr_v] and not visited[curr_v]:
			print(f"if 그래프 행렬의 정점 [{vertex}]와 [{curr_v}]가 간선으로 연결되어 {graph[vertex][curr_v]}이고 방문 여부가 {visited[curr_v]} 일 때")
		#	print(curr_v)
			visited[curr_v] = True
			print(visited)
			# 여기에서, graph[vertex] 의 정점과 이어진 curr_v 로 다시 시작하는 거니까 dfs(curr_v) 가 되는 거잖아
			dfs(curr_v)
		# 여긴 디버깅용, 지우자
		else:
			print("조건 불충족")

# 여기에서 인접 행렬을 입력해주었음
start_points = [1, 1, 1, 2, 4, 6]
end_points = [2, 3, 4, 5, 6, 7]

#
for start, end in zip(start_points, end_points):
	graph[start][end] = 1
	graph[end][start] = 1

print(f"입력한 그래프의 행렬: \n{graph}")

root_vertex = 1 # root 에서 탐색 시작
print(root_vertex)
visited[root_vertex] = True # 방문했으니 True 이때 graph[1][1] = True
dfs(root_vertex)

BFS (인접리스트)

먼저 graph라는 이름의 1차원 배열을 만들고, graph[i] 는 각각 i번째 정점에 연결되어 있는 정점들 목록을 관리하는 동적배열이 되어야 함

구현 시, 인접행렬과 마찬가지로 재귀함수를 작성해야 하는데 이때 연결된 정점을 찾아내는 방법만 조금 다름 → 현재 위치를 vertex라고 했을 떄, 인접리스트에서는 연결된 정점이 전부 graph[vertex] 안에 리스트 형태로 들어있게 됨

def dfs(vertex):
	for curr_v in graph[vertex]:
		if not visited[curr_v]:
			print(curr_v)
			visited[curr_v] = True
			dfs(curr_v)

따라서 graph[vertex] 안에 들어있는 원소들은 순서대로 순회하면 해당 원소( curr_v) 는 그즉시 vertex에 연결되어있는 원소가 된다.

즉, 1번 정점에서 시작해 **연결되어 있으며 아직 방문해본 적 없는 정점**이 발견되면 visited 를 true로 변경한 뒤, 다시 재귀적으로 해당 위치로 dfs 함수를 호출

-> 아래는 실제 코드

vertices_num = 7
edges_num = 6

# graph 
graph = [
	[0 for _ in range(vertices_num + 1)]
	for _ in range(vertices_num + 1)
]

visited = [False for _ in range(vertices_num + 1)]

print(f"처음: {visited}")

def dfs(vertex):
	# curr_v = 1, 2, 3, 4, 5, 6, 7 까지
	for curr_v in range(1, vertices_num + 1):
		print(f"* current vertex: [{vertex}][{curr_v}]")
		if graph[vertex][curr_v] and not visited[curr_v]:
			print(f"if 그래프 행렬의 정점 [{vertex}]와 [{curr_v}]가 간선으로 연결되어 {graph[vertex][curr_v]}이고 방문 여부가 {visited[curr_v]} 일 때")
		#	print(curr_v)
			visited[curr_v] = True
			print(visited)
			# 여기에서, graph[vertex] 의 정점과 이어진 curr_v 로 다시 시작하는 거니까 dfs(curr_v) 
			dfs(curr_v)
		# 여긴 디버깅용, 지우자
		else:
			print("조건 불충족")


# 여기에서 인접 행렬을 입력해주었음
start_points = [1, 1, 1, 2, 4, 6]
end_points = [2, 3, 4, 5, 6, 7]

#
for start, end in zip(start_points, end_points):
	graph[start][end] = 1
	graph[end][start] = 1


print(f"입력한 그래프의 행렬: \n{graph}")


root_vertex = 1 # root 에서 탐색 시작
print(root_vertex)
visited[root_vertex] = True # 방문했으니 True 이때 graph[1][1] = True
dfs(root_vertex)


>>> output

처음: [False, False, False, False, False, False, False, False]
입력한 그래프의 행렬: 
[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0, 0, 0], [0, 1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0, 1, 0]]
1
* current vertex: [1][1]
조건 불충족
* current vertex: [1][2]
if 그래프 행렬의 정점 [1]와 [2]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, False, False, False, False, False]
* current vertex: [2][1]
조건 불충족
* current vertex: [2][2]
조건 불충족
* current vertex: [2][3]
조건 불충족
* current vertex: [2][4]
조건 불충족
* current vertex: [2][5]
if 그래프 행렬의 정점 [2]와 [5]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, False, False, True, False, False]
* current vertex: [5][1]
조건 불충족
* current vertex: [5][2]
조건 불충족
* current vertex: [5][3]
조건 불충족
* current vertex: [5][4]
조건 불충족
* current vertex: [5][5]
조건 불충족
* current vertex: [5][6]
조건 불충족
* current vertex: [5][7]
조건 불충족
* current vertex: [2][6]
조건 불충족
* current vertex: [2][7]
조건 불충족
* current vertex: [1][3]
if 그래프 행렬의 정점 [1]와 [3]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, True, False, True, False, False]
* current vertex: [3][1]
조건 불충족
* current vertex: [3][2]
조건 불충족
* current vertex: [3][3]
조건 불충족
* current vertex: [3][4]
조건 불충족
* current vertex: [3][5]
조건 불충족
* current vertex: [3][6]
조건 불충족
* current vertex: [3][7]
조건 불충족
* current vertex: [1][4]
if 그래프 행렬의 정점 [1]와 [4]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, True, True, True, False, False]
* current vertex: [4][1]
조건 불충족
* current vertex: [4][2]
조건 불충족
* current vertex: [4][3]
조건 불충족
* current vertex: [4][4]
조건 불충족
* current vertex: [4][5]
조건 불충족
* current vertex: [4][6]
if 그래프 행렬의 정점 [4]와 [6]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, True, True, True, True, False]
* current vertex: [6][1]
조건 불충족
* current vertex: [6][2]
조건 불충족
* current vertex: [6][3]
조건 불충족
* current vertex: [6][4]
조건 불충족
* current vertex: [6][5]
조건 불충족
* current vertex: [6][6]
조건 불충족
* current vertex: [6][7]
if 그래프 행렬의 정점 [6]와 [7]가 간선으로 연결되어 1이고 방문 여부가 False 일 때
[False, True, True, True, True, True, True, True]
* current vertex: [7][1]
조건 불충족
* current vertex: [7][2]
조건 불충족
* current vertex: [7][3]
조건 불충족
* current vertex: [7][4]
조건 불충족
* current vertex: [7][5]
조건 불충족
* current vertex: [7][6]
조건 불충족
* current vertex: [7][7]
조건 불충족
* current vertex: [4][7]
조건 불충족
* current vertex: [1][5]
조건 불충족
* current vertex: [1][6]
조건 불충족
* current vertex: [1][7]
조건 불충족

인접리스트

vertices_num = 7
graph = [[] for _ in range(vertices_num + 1)]
print(graph)

visited = [False for _ in range(vertices_num + 1)]


# 인접리스트로 그래프 표현
start_points = [1, 1, 1, 2, 4, 6]
end_points = [2, 3, 4, 5, 6, 7]

for start, end in zip(start_points, end_points):
	graph[start].append(end)
	graph[end].append(start)

print(graph)
root_vertex = 1
print(root_vertex)
# 마찬가지로 [1] 은 방문처리
visited[root_vertex] = True
print(visited)
print(f"test: 주어진 행렬리스트에서 1에 연결된 애들은 {graph[1]}\n\n")

# graph = 그래프를 인접 리스트로 표현한 것, 리스트 형태임

def dfs_list(vertex):
    for curr_v in graph[vertex]:
        print(f"**current vertex: {vertex}, 해당 리스트엔 {graph[vertex]} 존재, {curr_v} 시작")
        if not visited[curr_v]:
            print(f"아직 방문 안 한 {curr_v} 에 방문처리")
            visited[curr_v] = True
            dfs_list(curr_v)
        # 디버깅용
        else:
            print("조건 미충족, pass")


dfs_list(root_vertex)

• 위처럼 vertex 1에서 시작했을 때 [2, 3, 4] 를 차례로 순회
  이때 [1] -> [2] 에서 [1, 5] 가 연결된 노드일 때 아직 방문 안 한 [5] 에 들리고, 방문처리 뒤 [5] 에 연결된 [2] 로 다시 dfs(2) 순회하려했으나 이미 방문처리가 된 노드이므로
• 다시 dfs(1) 로 돌아감.
• 이처럼 가장 깊은 곳까지 방문했다가, 갈 곳이 더이상 없으면 다시 빠져나와서 위로 돌아감.