목록dfs (1)

와드의 블로그

그래프 탐색

DFS그래프를 탐색할 때 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다.검색 속도가 BFS에 비해 느리지만 더 간단하게 구현할 수 있다.재귀를 이용하여 구현한다.DFS 구현static ArrayList> adj;static boolean[] visited;void dfs(int x) { visited[x] = true; for(int nx : adj.get(x)) { if(visited[nx]) continue; dfs(nx); }}BFS그래프를 탐색할 때 시작 노드에서 탐색을 시작하여 인접 노드를 모두 탐색하고 다음 노드를 탐색하는 방법이다.큐를 이용하여 구현한다.가중치가 없는 그래프의 최단거리를 구하는 문제에 사용할 수 있다.BFS 구현static Arra..
PS 2024. 10. 31. 18:58
이전 Prev 1 Next 다음