방향이 틀린 그래프에주기가 있는지 감지합니다.

사이클이 존재하면 내 질문에 DETECTING이 관련됩니다. 사이클이있는 곳에서만 사이클이 발생하지만 상관 없습니다. 특히 (최대로) 스패닝 트리 알고리즘을 구현하려고합니다. 내림차순으로 가장자리를 정렬 한 다음 그 시점에서 한 가장자리를 선택하여 IFF에서 순환을 일으키지 않는 그래프 가장자리 집합에 넣습니다.방향이 틀린 그래프에주기가 있는지 감지합니다.

무연 그래프의 경우 no_of_edges> no_of_vertices - 1을 확인하기에 충분하다는 것을 알았습니다. 이게 옳은 거니? 나는 이것이 사실이 아닌 경우를 찾기 위해 노력하고 있습니다. 나는 할 수 없습니다. 물론 이것이 이것이 옳다는 것을 의미하지는 않습니다.

감사

그래프 분리, 또는 하나 이상의 가장자리는 주어진 두 노드 사이 인 경우

출처

2011-11-16 George Eracleous

가능한 [중복 된 그래프의 순환] (http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph) –

http://en.wikipedia.org/wiki를 참조하십시오./Cycle_detection_ (graph_theory) #Cycle_detection –

Kruskal의 알고리즘처럼 보이지만, "disjoint sets"데이터 구조를 살펴보십시오. http://en.wikipedia.org/wiki/Disjoint-set_data_structure – abeln

DFS 검색을 실행하십시오. 그것이 DFS의 중지 조건이기 때문에 자동으로 루프를 감지합니다. 이미 스택에있는 노드를 입력하면 멈추고,주기를 찾은 것입니다.

출처

2011-11-16 00:43:16

, 당신의 생각은 실패합니다. 두 노드 사이에 하나의 가장자리가 있다고 규정하면 연결 상태를 확인해야합니다.

그래, 연결된 그래프에서 모서리 수가 < = 정점 수 -1 인 경우 예가 가능합니다.

출처

2011-11-16 00:13:21 bdares

오른쪽 ...너가 확실히 맞아. 연결 상태를 확인해야하므로 대부분의 노드 사이에 하나의 가장자리가 있습니다. –

기본적으로 귀하의 아이디어는 정확합니다. 하지만 어떤 함정이있을 수 있습니다 :

1) 먼저 확인하는 DFS를 실행하고 연결된 모든 구성 요소를 찾을 조건 여부 no_of_edges < = no_of_vertices - 연결된 모든 구성 요소 1.

2) 연결된 각 구성 요소에 여러 가장자리가 있는지 확인하십시오.

출처

2011-11-16 00:17:27 derekhh

방향이 틀린 그래프에주기가 있는지 감지합니다.

답변

관련 문제