순환 그래프를 최단 경로 부분 그래프의 최소 수로 분해하십시오.

Question

순환 그래프가 주어지면이 그래프를 비순환 부분 그래프로 분해하는 알고리즘을 찾고 있습니다. 각 서브 그래프에는 루트 정점이 있으며,이 정점은 최단 경로가 계산 된 소스입니다. 예를 들어,주기가 3,4 사이에 아래에 순환 적 그래프를 부여하고, 5

가

     +-------------------------+ 
         |       | 
         |       | 
      +----------+----------+    | 
      v   |   v    | 
+---+  +---+  +---+  +---+  +---+ | 
| 1 | --> | 3 | <--> | 4 | <--> | 5 | --> | 6 | | 
+---+  +---+  +---+  +---+  +---+ | 
        ^      | 
         |       | 
         |       | 
        +---+      | 
        | 2 |      | 
        +---+      | 
        +---+      | 
        | 7 | <---------------------+ 
        +---+ 

1에 대한 최단 경로 서브 그래프가 될 것이다 :

+---+  +---+  +---+  +---+ 
| 1 | --> | 3 | --> | 4 | --> | 7 | 
+---+  +---+  +---+  +---+ 
      | 
      | 
      v 
      +---+  +---+ 
      | 5 | --> | 6 | 
      +---+  +---+ 

최단 경로 서브 그래프 (2)에 대한 것이다 :

는

  +---+ 
      | 7 | 
      +---+ 
      ^
      | 
      | 
+---+  +---+  +---+  +---+ 
| 2 | --> | 4 | --> | 5 | --> | 6 | 
+---+  +---+  +---+  +---+ 
      | 
      | 
      v 
      +---+ 
      | 3 | 
      +---+ 

5에 대한 최단 경로 sugraph가 될 것이다 :

0,123,902

3에 대한 최단 경로 하위 그래프는 1의 하위 집합이며 4는 2의 하위 집합입니다. 6 및 7은 잎이다.

현재 나의 (순진한) 해결책은주기를 막기 위해 방문한 노드에 플래그를 지정하여 각 노드에 대해 BFS를 수행하는 것입니다. 그런 다음 하위 그래프가 서로 다른 서브 그래프인지 확인하여 최소 수의 고유 한 하위 그래프를 만듭니다. 더 나은,보다 공식적인 솔루션에 대한 아이디어가 있습니까?

편집 제 상황의 그래프는 가중치가 적용되지 않지만 후계에 대한 일반적인 해결책이 좋습니다.

(http://bloodgate.com/graph-demo로 만든 그래프)

Answer 1

templatetypedef는 "BFS"의 OP의 사용은 그래프 하중이 줄어들 것이 좋습니다.

은 여기에 루트로부터 도달 서브 그래프의 크기, 최종 컬렉션의 각 루트에 대해, 합에 비례 한 시간으로 운영되는 알고리즘이다. 예를 들어, 경계 정도의 그래프는 출력 크기의 순서입니다. 나는 "짧은 경로는"길이 렉스 위해 적어도 의미 있다고 가정거야 고유성을 위해서

. 고차원에서는 정점을 처리하는 순서를 계산하여 정점 u의 BFS 트리가 정점 v를 포함하면 v가 앞에 정렬됩니다. 각 정점은 선형 시간으로 처리됩니다. 정점은 포함 된 정점을 결정하는 것을 포함합니다.

순서

는 위상 적으로 강한 구성 요소를 정렬 한 다음 임의의 각 단일 구성 요소 내에서 정점을 주문, 강한 구성 요소를 찾아 계산됩니다. u에서 도달 할 수있는 꼭지점 집합이 v에서 도달 할 수있는 꼭지점의 적절한 수퍼 집합 인 경우에만 u를 포함합니다.

꼭지점 u를 처리하려면 u에서 BFS 트리를 계산 한 다음 하위 트리에있는 꼭지점 집합 하위 트리를 벗어나는 아크가 없습니다. 이들은 하위 포함됩니다. 각각의 버텍스 v에 대해 왼쪽 끝 점이 입력 시간이고 오른쪽 끝 점이 종료 시간 인 간격 I (v)를 기록하여 트리 깊이를 먼저 트래버스하여 후자를 결정합니다. 각 버텍스 v에 대해 I (v)와 모든 I (w)가 포함 된 최소 간격 J (v)를 호 v -> w로 계산합니다. DFS를 사용하여 v의 모든 자손 w에 대해 K (w)를 포함하는 가장 작은 간격 K (v)를 각 정점 v에 대해 계산합니다 .K (v) = I (v) 인 경우에만 u 이외의 정점 v가 포함됩니다. .

왜이 일을해야합니까? 우리는 v에 뿌리를 둔 나무의 하위 트리가 v에 뿌리를 둔 나무의 하위 집합이라는 것을 압니다 .u가 v를 포함한다고 가정합니다 (다시 말하면,이 두 나무는 동일합니다). 그런 다음 v의 하위 트리에있는 모든 호의 머리 부분이 v의 하위 트리로 이동합니다. 그렇지 않으면 헤드가 탐험되어야합니다. 반대로, u가 v를 포함하지 않는다고 가정하자. v에 뿌리를 둔 트리는 v의 서브 트리가 아닌 정점을 포함하므로 v의 서브 트리를 떠나는 호가있다.

나는이 설명이 당신에게 유용 희망하지만 실제 문제는 더 나은 방법이있을 수있는 subquadratic 공간, 빠른 지점 간 최단 경로 쿼리를 포함한다는 우려하고있다.

Answer 2

당신이 shortest path tree 일부 정점에 뿌리를 둔 하나의 최단 경로 트리를 찾기 위해, 당신은 다 익스트라의 알고리즘을 사용할 수 있습니다이라고 위에 열거 한 나무의 각 모두 발견 소스 노드에서 다른 모든 노드까지의 최단 경로 및 해당 노드에 도달하는 데 사용되는 에지를 보여줍니다. 그래프에 음의 모서리가없는 것으로 가정하면 단일 노드에 대한 최단 경로 트리가 즉시 제공됩니다. 모든 나무를 나열하려면 각 노드에서 시작하는 Dijkstra의 알고리즘을 실행하면됩니다. 피보나치 힙을 감안할 때 이것은 매우 빠르며 O (VE + V log V)로 실행됩니다.

피보나치 힙이 없거나 밀집된 그래프를 사용 중이거나 부정적인주기가있는 경우 Floyd-Warshall 알고리즘을 사용할 수 있습니다. 이 알고리즘은 시간 O (V)에서 실행되고 네거티브 에지가 있더라도 각 노드에 대해 서로 다른 노드에 대한 최단 경로를 계산합니다. 여기에서 모든 최단 경로 나무를 아주 쉽게 복구 할 수 있습니다.

희망이 도움이됩니다.

편집 : 그래프 하중이 줄어들면, 분명히 시간 O에서 M은 (n)이 증식하는 데 필요한 시간입니다 (M (n)이 로그 N)을, 실행이 문제를 해결하기위한 정말 좋은 알고리즘이있다 작은 수의 행렬 O (n ^2.3) 주변에서 문제가 해결 될 수있는 가장 좋은 알고리즘이 될 것입니다. 알고리즘에 대한 논문이 있습니다 here하지만 페이 월의 배후에 있습니다. 실제로 거대한 그래프 (수만 노드)를 다룰 때 나는이 더 강력한 알고리즘을 사용하는 것에 대해 걱정할 필요가 없다고 생각하지만 여전히 알고있는 것이 좋다.