'깊이우선탐색' 태그의 글 목록

[알고리즘] DFS(Depth First Search, 깊이 우선 탐색)

DFS란? - 그래프 탐색 알고리즘 - 갈 수 있는 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문하는 탐색 방법 - 스택으로 구현이 가능하다. 스택 대신 재귀함수를 사용해서 구현하는 경우도 많다. 재귀함수 사용 시 종료 조건을 반드시 명시해야 한다. DFS 구현 - 동작 과정 1) 탐색 시작 노드를 스택에 삽입 후 방문처리 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 존재하면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다. def dfs(graph, start): vist = list() stack = list() stack.a..

୨┈┈┈ Study┈┈┈୧/↘ Algorithm 2021.05.04

일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

𝕕𝕖𝕧𝕖𝕝𝕠𝕡 𝕣𝕖𝕔𝕠𝕣𝕕

깊이우선탐색 1

티스토리툴바