티스토리 뷰
728x90
반응형
- 인접한 간선 모두 방문
- 더 이상 갈 곳이 없으면 Back Tracking
- 재귀호출, Stack
- 그래프의 전체 구조를 파악
- O(|V|²)
- 두 정점이 서로 연결되어 있는가
- 연결된 부분집합의 개수 세기
- 위상정렬
- 사이클 존재여부
//V : 정점 집합, E : 간선 집합
//visit[v] : 방문정보 저장
//Adj[v] : 정점 v의 인접 정점 집합
dfs(v) {
visit[v] = true; //방문 처리
for (인접 정점 u : Adj[v]) {
if (visit[u] == false) //인접 정점이 방문하지 않았다면 탐색
dfs(u);
}
}
728x90
반응형
'Algorithm' 카테고리의 다른 글
최단 경로 알고리즘 - Floyd Warshall (0) | 2020.04.05 |
---|---|
최단 경로 알고리즘 - Bellman Ford (0) | 2020.04.05 |
최단 경로 알고리즘 - 최소신장트리 (Minimum Spanning Tree) (0) | 2020.04.05 |
최단 경로 알고리즘 - 다익스트라 (Dijkstra) (0) | 2020.04.05 |
너비 우선 탐색 Breadth First Search (BFS) (0) | 2020.04.05 |
반응형
300x250