DFS : 재귀함수(스택)로 구현
재귀 함수 실행 시 방문처리 & 값 이용
연결된 노드 재귀함수 호출
# DFS
# 동작 원리 : 스택
# 구현 방법 : 재귀 함수 이용
# 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간 소모됨
# visited 리스트가 dfs 함수 안에 있으면, dfs 함수가 재귀적으로 호출되면서 계속 리스트가 초기화되기 때문에 안됨
# vertex : 정점, edge : 간선
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [0 for _ in range(len(graph))]
def dfs(graph, visited, v):
if visited[v] == 0:
visited[v] = 1
print(v, end=" ")
for x in graph[v]:
dfs(graph, visited, x)
dfs(graph, visited, 1)
BFS : queue로 구현
queue에 넣으며 방문처리
queue에서 빼며 값 이용/ 연결된 노드 넣으며 방문처리
# BFS
# 동작 원리 : 큐
# 구현 방법 : 큐 자료구조 이용
class Queue:
def __init__(self):
self.__queue = []
self.__size = 0
def enqueue(self,x):
self.__queue.insert(0,x)
self.__size += 1
def dequeue(self):
self.__size -= 1
return self.__queue.pop()
def dequeueAll(self):
self.__queue = []
self.__size = 0
def isEmpty(self):
return self.__size == 0
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [0 for _ in range(len(graph))]
def bfs(graph, visited, v):
queue = Queue()
queue.enqueue(v)
visited[v] = 1
while True:
if queue.isEmpty(): break
v = queue.dequeue(); print(v, end=" ")
for x in graph[v]:
if visited[x] == 0:
queue.enqueue(x)
visited[x] = 1
bfs(graph, visited, 1)