자료구조알고리즘/이론
그래프 - DFS 구현 (2)
포시
2023. 4. 24. 04:43
728x90
개요
그래프 - DFS 구현
DFS 알고리즘 구현 스택, 큐 자료구조 활용 need_visit stack visited queue * BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있다. 개념 위 그래프에 대해 DFS를 구현한
4sii.tistory.com
위 내용과 이어진다.
이전에는 알파벳으로 된 노드들로 DFS하는 방법을 알아봤는데
이번엔 숫자로 이루어진 DFS 알고리즘을 알아볼 것이다.
특히, 각 노드들에 대해 작은 순서부터 진행한다는 큰 특징이 있는데
코딩테스트에서 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] * len(graph)
dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5728x90