유 방향 그래프가 비순환인지 어떻게 확인합니까? 그리고 알고리즘은 어떻게 호출됩니까? 참고로 부탁드립니다.
답변
나는 그래프를 토폴로지 적 으로 정렬 하려고하는데 , 할 수 없다면 사이클이있는 것입니다.
답변
단순한 깊이 우선 검색은 주기를 찾기에 충분 하지 않습니다 . 주기가없는 DFS에서 노드를 여러 번 방문 할 수 있습니다. 시작 위치에 따라 전체 그래프를 방문하지 못할 수도 있습니다.
다음과 같이 그래프의 연결된 구성 요소에서주기를 확인할 수 있습니다. 나가는 가장자리 만있는 노드를 찾습니다. 그러한 노드가 없으면주기가 있습니다. 해당 노드에서 DFS를 시작합니다. 각 에지를 순회 할 때 에지가 이미 스택에있는 노드를 가리키는 지 확인하십시오. 이것은주기의 존재를 나타냅니다. 그러한 에지를 찾지 못하면 연결된 구성 요소에 사이클이없는 것입니다.
Rutger Prins가 지적했듯이 그래프가 연결되지 않은 경우 연결된 각 구성 요소에 대해 검색을 반복해야합니다.
참고로 Tarjan의 강력한 연결 구성 요소 알고리즘 은 밀접한 관련이 있습니다. 또한주기의 존재 여부를보고하는 것이 아니라주기를 찾는 데 도움이됩니다.
답변
책 Introduction to Algorithms(제 2 판) 의 Lemma 22.11은 다음과 같이 설명합니다.
유 방향 그래프 G는 G의 깊이 우선 검색이 뒷 모서리를 생성하지 않는 경우에만 비순환입니다.
답변
Solution1：Kahn 알고리즘은주기를 확인합니다 . 주요 아이디어 : 정도가 0 인 노드가 대기열에 추가되는 대기열을 유지합니다. 그런 다음 대기열이 비워 질 때까지 노드를 하나씩 떼어냅니다. 노드의 인에지가 존재하는지 확인하십시오.
Solution2 : 강력한 연결 구성 요소를 확인하는 Tarjan 알고리즘 .
솔루션 3 : DFS . 정수 배열을 사용하여 노드의 현재 상태에 태그를 지정합니다. 즉 0은이 노드가 이전에 방문한 적이 없음을 의미합니다. -1-이 노드가 방문되었고 하위 노드가 방문 중임을 의미합니다. 1-이 노드가 방문되었으며 완료되었음을 의미합니다. 따라서 DFS를 수행하는 동안 노드의 상태가 -1이면주기가 존재해야 함을 의미합니다.
답변
ShuggyCoUk가 제공하는 솔루션은 모든 노드를 검사하지 않을 수 있으므로 불완전합니다.
def isDAG(nodes V):
while there is an unvisited node v in V:
bool cycleFound = dfs(v)
if cyclefound:
return false
return true
이것은 시간 복잡도 O (n + m) 또는 O (n ^ 2)
답변
나는 이것이 오래된 주제라는 것을 알고 있지만 미래의 검색 자들을 위해 여기에 내가 만든 C # 구현이 있습니다 (가장 효율적이라는 주장은 없습니다!). 이것은 각 노드를 식별하기 위해 간단한 정수를 사용하도록 설계되었습니다. 노드 객체 해시를 제공하고 적절하게 같으면 원하는대로 꾸밀 수 있습니다.
매우 깊은 그래프의 경우 각 노드에서 해시 세트를 생성하므로 오버 헤드가 높을 수 있습니다 (폭에 걸쳐 파괴됨).
검색하려는 노드와 해당 노드로가는 경로를 입력합니다.
- 단일 루트 노드가있는 그래프의 경우 해당 노드와 빈 해시 세트를 보냅니다.
- 루트 노드가 여러 개인 그래프의 경우 해당 노드에 대해 foreach로 래핑하고 각 반복에 대해 새로운 빈 해시 세트를 전달합니다.
-
주어진 노드 아래의주기를 확인할 때 빈 해시 세트와 함께 해당 노드를 전달하십시오.
private bool FindCycle(int node, HashSet<int> path) { if (path.Contains(node)) return true; var extendedPath = new HashSet<int>(path) {node}; foreach (var child in GetChildren(node)) { if (FindCycle(child, extendedPath)) return true; } return false; }
답변
DFS 수행 중에는 백 엣지가 없어야하며 DFS를 수행하는 동안 이미 방문한 노드를 추적하여 현재 노드와 기존 노드 사이에 엣지를 만나면 그래프에주기가 있습니다.
