깊이 우선 탐색 Depth First Search (DFS)
인접한 간선 모두 방문 더 이상 갈 곳이 없으면 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); } }
Algorithm
2020. 4. 5. 19:14
반응형
300x250