목록dfs (1)

KKanging

[알고리즘]DFS/BFS(그래프 탐색 알고리즘) 개념과 구현(JAVA)

우선 그래프 이론과 큐와 스택을 모른다면 그래프 큐 스택 을보고 오시기 바랍니다. 그래프를 탐색하는 방법 DFS (깊이 우선 탐색) BFS (너비 우선 탐색) DFS(Depth-First-Search) 관련 있는 노드를 최대한 깊이 있게 탐색하는 방법 구현 방법 stack 재귀함수 구현 방법 우선 방문한 정점을 다시 방문하는 일이 없도록 visited 배열을 만들어 준다. 0은 아직 방문하지 않았다는 의미 시작 정점 하나부터 stack에 넣는다. 그리고 stack의 있는 원소를 pop 한다 pop 된 정점과 연결되어 있는 정점을 stack에 push 한다. pop 된 정점과 연결되어 있는 visited 원소를 1로 바꾼다. 이제 핵심 로직을 반복하면 된다. 4가 pop 되고 4와 연결되어 있는 정점을 찾..
cs/알고리즘 2023. 7. 27. 02:18
이전 Prev 1 Next 다음