고정 간선이 있는 유방향 그래프에서 주기 종속성 제거

StackOverflow https://stackoverflow.com/questions/1006071

문제

방향성 순환 그래프가 있습니다.일부 가장자리는 고정되어 있어 제거할 수 없습니다.사이클을 깨기 위해 다른 모서리를 제거할 수도 있습니다.

이 그래프에서 순환을 제거하는 가장 좋은 방법은 무엇입니까?순회는 가능한 한 많은 DFS여야 하며 지정된 노드에서 시작되어야 합니다.

도움이 되었습니까?

해결책 3

내 문제를 해결하기 위해 다음 알고리즘을 사용했습니다.

다음으로 표시된 모든 고정 모서리의 그래프로 시작합니다. 확인됨

시작 노드에서 확인된 모든 가장자리와 아직 확인되지 않은 가장자리를 통해 반복됩니다.그러나 아직 확인되지 않은 가장자리를 재귀적으로 내려오려는 경우 먼저 가장자리가 이동하는 노드에 확인된 가장자리를 따라 현재 검색 트리의 노드에 대한 경로가 있는지 확인하십시오(예:노드 방문 플래그가 설정됨).이 확인은 확인된 모든 에지를 따라 반복적으로 수행되어야 하지만 이는 나에게 너무 느리기 때문에 노드가 방문 중인지 또는 연결된 것으로 확인된 노드 중 하나가 방문 중인지 확인하기 위해 여기에서 해결하겠습니다.이것은 대부분의 경우를 다루지만 때때로 그래프에 주기를 남겨둡니다.

위의 단계 후에 나는 그래프에 남아 있는 강하게 연결된 구성 요소를 찾기 위해 Tarjan의 알고리즘을 사용합니다(이 작업은 O(V + E) 시간에 완료될 수 있습니다).제 경우에는 강하게 연결된 구성 요소의 수가 매우 적으므로 강하게 연결된 각 구성 요소를 살펴보고 각각 제거 가능한 가장자리를 하나씩 제거합니다.그런 다음 그래프에 더 이상 사이클이 남지 않을 때까지 이 단계를 다시 수행합니다.

이것은 잘 작동하고 충분히 빠릅니다.

다른 팁

당신이 할 수있는 것은 dijkstra의 알고리즘을 사용하는 것입니다. 고정 가장자리 만 포함 된 그래프로 시작하십시오. 그런 다음 이미 가지고있는 그래프로 시작하여 알고리즘의 적응을 적용하십시오.

  1. 시작 노드로 시작하고 시작 노드의 구성 요소에서 모든 고정 가장자리가 시작됩니다. 이것이 나무라고 가정합니다.
  2. 트리에 가장 가까운 노드를 추가하십시오.
  3. 또한 방금 추가 한 노드의 구성 요소에 고정 가장자리를 추가하십시오.
  4. 모든 노드가 트리에 있으면 끝을 끝내십시오. 그렇지 않으면 4 단계로 이동하십시오.

물론 이것은 고정 가장자리로만 구성된 그래프에 사이클이 포함되어 있지 않다고 가정합니다. 그렇다면 솔루션이 없습니다 (즉, 가장자리가없는 하위 그래프이지만 모든 고정 가장자리가 포함되어 있음).

지시 된 그래프의 경우 조금 더 복잡합니다. 이 경우 고정 가장자리 그래프의 구성 요소는 트리 여야합니다. dijkstra와 같은 알고리즘에서는이 노드의 루트 만 트리에 추가해야합니다.

그래프가 연결되어 있어야하는지 또는 모든 사이클을 파괴하기 위해 "소형"수의 고정되지 않은 가장자리를 제거하려는 경우 또는 전 세계 최소 최소 수의 필요한 경우 문제가 지정되지 않았기 때문에 문제가 절제됩니다. 고정되지 않은 가장자리를 제거합니다.

그래프가 연결되어 있지 않으면 모든 모서리를 통과하고 고정되지 않은 모든 모서리를 제거하십시오. 고정 가장자리를 제거하지 않고 제거 할 수있는 모든 사이클이 제거됩니다.

순수한 DFS 인 가장자리를 제거하기 위해 간단한 욕심 많은 알고리즘을 원한다면 고정되지 않은 가장자리의 일부를 제거 할 때 그래프가 연결되어 있으면 이와 같은 것을 사용할 수 있습니다.

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top