[그래프] 23. DFS 알고리즘 시간 복잡도 분석

DFS를 실행시키는 데 시간이 얼마나 걸리는지 알아보자. 총 Node의 수를 V 엣지의 수를 E 라고 하자. DFS 알고리즘 (처음에 모든 노드를 방문하지 않았다고 표시) 시작점 노드를 옅은 회색 표시 후, 스택에 넣는다 스택에 아무 노드도 없을 때까지: 1. 스택에서 가장 위 노드를 꺼냅니다 2. 짙은 회색(방문

[그래프] 22. DFS로 연결된 역 찾기

실습과제 DFS 알고리즘 시작점 노드를 옅은 회색 표시 후, 스택에 넣는다 스택에 아무 노드도 없을 때까지: 스택에서 가장 위 노드를 꺼냅니다 짙은 회색(방문 처리) 표시를 합니다 이 노드에 인접해 있는 노드들을 돌면서: 노란색 노드면: 옅은 회색으로 표시한다 스택에 넣는다

[그래프] 21. DFS 알고리즘

먼저 아래와 같은 그래프와 빈 스택이 있다고 하자. BFS와 마찬가지로 DFS에서도 이미 찾은 Node를 다시 탐색하지 않아야 되기 때문에 모든 Node마다 방문한 Node 인지 아닌지 구별해 준다. DFS에서는 BFS랑은 다르게 세 가지 색을 쓰겠다. 먼저

[그래프] 20. 스택

BFS에서 큐가 중요했던 것처럼 DFS에서도 중요한 추상 자료형이 있다. 본격적으로 DFS에 대해서 배워보기 전에 이번 레슨에서 짚고 넘어가자. 스택 복습할 추상 자료형은 바로 스택이다. 기본 자료형 토픽에 조금 더 구체적인 설명이 있긴 하니까 여기서는 좀 더 간략하게 알아보자. 스택은 맨 뒤에서 데이터 추가 맨 뒤

[그래프] 19. DFS(Depth First Search) 개념

DFS의 Depth는 영어로 깊이를 뜻한다. DFS는 깊이를 우선적으로 탐색하겠다. 라는 말이다 예시를 보자. 아래 그래프를 보자. A 를 시작점으로 탐색을 하고 싶다. 먼저 A에 인접한 Node 하나로 간다.