심층적으로 검색하십시오. DFS


DFS DFS
깊이 우선 검색(DFS)은 그래프의 주요 알고리즘 중 하나입니다. 알고리즘은 O(N + M)에서 실행됩니다.
 
알고리즘
우선 맨 위부터 시작하여 이 맨 위의 하위 항목을 고려하고 입력한 적이 없는 경우 해당 항목에서 DFS를 시작합니다.


Training problem

DFS: 시작(C++)

DFS DFS
깊이 우선 검색(DFS)은 그래프의 주요 알고리즘 중 하나입니다. 알고리즘은 O(N + M)에서 실행됩니다.
 
알고리즘
우선 맨 위부터 시작하여 이 맨 위의 하위 항목을 고려하고 입력한 적이 없는 경우 해당 항목에서 DFS를 시작합니다.


Training problem

DFS: 시작(Python)

이분 그래프
 
이분 그래프 - 정점을 두 세트로 나누어 각 에지가 다른 세트의 정점.


종종 이분 그래프의 맥락에서 색상 정점이라는 개념이 사용됩니다. 그래프를 두 부분으로 나누는 것을 꼭짓점에 색상을 두 가지 색상으로 지정합니다. 각 가장자리는 서로 다른 색상의 정점을 연결해야 합니다.

DFS. 
 

알고리즘

우리는 임의의 정점에서 페인팅을 시작하여 임의의 색상으로 페인팅합니다.
각 가장자리를 통과할 때 다음 정점을 반대 색상으로 칠합니다.
인접한 정점을 반복하는 동안 현재 정점과 동일한 색상으로 이미 칠해진 정점을 찾으면 그래프에 홀수 주기가 있는 것입니다. 이는 이분법이 아님을 의미합니다.

Training problem

이분 그래프

알고리즘은 다음과 같이 설명할 수 있습니다.
n개의 꼭지점과 m개의 모서리가 있는 유향 그래프가 주어집니다. 각 가장자리가 낮은 번호의 정점에서 높은 번호의 정점으로 이어지는 방식으로 정점의 번호를 다시 지정해야 합니다.
즉, 그래프의 모든 모서리에 의해 주어진 순서에 해당하는 정점의 순열(위상적 순서)을 찾아야 합니다.
깊이 우선 검색(dfs(v))
을 사용합니다.
\(dfs(v)\) 에서 종료할 때 목록의 시작 부분에 정점을 추가하면 끝 이 목록에서 토폴로지 정렬을 얻습니다.
따라서 원하는 토폴로지 정렬 — 종료 시간의 내림차순으로 정렬됩니다.

Training problem

토폴로지 정렬