안녕하세요. 오늘은 DFS와 BFS알고리즘에 대해서 알아 보겠습니다.
DFS와 BFS는 그래프의 완전탐색 알고리즘입니다.
시간복잡도
두 알고리즘의 시간 복잡도에 대해서 먼저 설명드리겠습니다.
인접리스트형식으로 표현된 그래프와 인접행렬법으로 표현된 그래프에서의 시간복잡도는 다릅니다.
우선 인접행렬법(V by V 행렬 : V은 정점의 개수 입니다.)에서는 O(V^2)입니다.
각각의 노드에서 모든 노드로 간선이 있는지 여부를 알아야 하기 때문입니다.
두번째로 인접리스트형식(V: 정점의 개수, E: 간선의 개수)으로 표현된 그래프에서는 O(V+E)입니다.
각각의 노드에서 다른 노드로 간선이 리스트형식으로 존재함을 알기 때문에 V+E로 모두 탐색 가능합니다.
알고리즘 설명
DFS부터 알고리즘 설명 드리겠습니다.
DFS는 깊이 우선 탐색으로 인접노드의 Depth를 우선적으로 먼저 탐색하면서 stack에 지나온 위치를 저장합니다.
더 이상 갈곳이 없으면 stack에서 pop하고 다시 push를 합니다.
즉 최대 깊이 만큼 push를 하고 더 이상 push할 수 없으면 pop을 하고 다음 탐색가능한 곳을 push합니다.
다음으로 BFS 알고리즘 설명 드리겠습니다.
BFS 알고리즘은 넓이 우선 탐색으로 모든 인접 노드를 queue에 저장합니다.
queue에 있는 노드를 pop하면서 각각의 노드에서 인접 노드를 다시 queue에 push합니다.
인접 노드를 모두 push를 하고 더 이상 push할 수 없으면 pop을 하고 다음 탐색가능한 곳을 push합니다.
오늘은 BFS와 DFS 알고리즘에 대해서 설명하였습니다.
질문이 있으시면 댓글로 남겨주세요.
다들 오늘도 좋은 하루 되세요.