그래프 순회 알고리즘

Graph Traversal (그래프 순회) 대표적인 두 가지 방법 DFS (Depth-First Search) BFS (Breadth-First Search) 동일한 Tree를 각각 DFS/BFS로 방문하기 DFS : 깊이 먼저, 스택 (Stack) 자료구조 활용 BFS : 너비 먼저, 큐 (Queue) 자료구조 활용 깊이 우선 탐색 (Depth-First Search; DFS) (1) 정점 i를 방문한다. (2) 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다. (3) 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다. (4) 스택이 공백이 되면 연산을 종료한다. DFS(s) { // s 는 시작 정점 for (i←0; i
oneonlee
'그래프 순회 알고리즘' 태그의 글 목록