수달이네 기술 블로그

9. 그래프 순회

그래프 순회순회: 모든 정점과 간선을 검사하여 그래프를 탐색하는 체계적인 절차깊이 우선 탐색(DFS-Depth first search)=n개의 정점과 m개의 간선을 가진 그래프에 O(n+m)의 시간 소요해결 가능한 문제G의 모든 정점과 간선을 방문G가 연결 그래프인지 확인G의 연결 요소들을 계싼G의 신장 숲을 계산이중연결요소 계산알고리즘기본적인 그래프에 대해 그래프의 간선을모든 정점을 Fresh, 즉, 아직 방문하지 않았음으로 표시해준다.모든 간선 또한 방문하지 않았음으로 만들어준다.모든 정점을 반복문으로 돌아가며 방문하지 않았으면 rDFS(DFS의 재귀함수)를 호출한다rDFS들어온 해당 정점을 방문했다고 표시한다.다음 정점이 방문하지 않았느냐 확인, 방문하지 않았으면 들어가서 재귀호출방문했으면 뒤로 돌..
알고리즘 공부 2025. 12. 17. 22:51
이전 Prev 1 Next 다음