지시 된 그래프가 강력하게 연결되어 있는지 확인하는 알고리즘

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

문제

지시 된 그래프가 있는지 확인해야합니다 강력하게 연결되었습니다, 다시 말해, 모든 노드에 다른 노드에 도달 할 수있는 경우 (반드시 직접 에지를 통해).

이 작업을 수행하는 한 가지 방법은 모든 노드에서 DFS와 BFS를 실행하는 것이며 다른 모든 것이 여전히 도달 할 수 있음을 알 수 있습니다.

그렇게 할 수있는 더 좋은 접근법이 있습니까?

도움이 되었습니까?

해결책

타잔 강력하게 연결된 구성 요소 알고리즘 (또는 Gabow 's 변형) 물론 충분할 것입니다. 강하게 연결된 구성 요소가 하나만 있으면 그래프가 강력하게 연결됩니다.

둘 다 선형 시간입니다.

일반적인 깊이의 첫 번째 검색과 마찬가지로, 각 노드의 상태를 추적합니다 : 새, 보이지만 여전히 열려 있습니다 (통화 스택에 있습니다). 또한, 처음 노드에 도달했을 때 깊이를 저장하고 노드에서 도달 할 수있는 가장 낮은 깊이를 저장합니다 (노드를 완료 한 후에 알 수 있음). 가장 낮은 도달 깊이가 자체 깊이와 같으면 노드는 강하게 연결된 구성 요소의 루트입니다. 루트에서 노드에 도달하는 깊이가 가능한 최소가 아닌 경우에도 작동합니다.

전체 그래프가 단일 SCC인지, 단일 노드에서 DFS를 시작하고, 완료되면, 가장 낮은 도달 깊이가 0이고 모든 노드가 방문되면 전체 그래프가 강력하게 연결되어 있습니다.

다른 팁

다음 알고리즘을 고려하십시오.

  1. 임의의 정점에서 시작하십시오 v 그래프의 G, 그리고 실행 a DFS(G, v).

    • 만약에 DFS(G, v) 그래프의 다른 모든 정점에 도달하지 못합니다 G, 그런 다음 일부 정점이 있습니다 u, 지시 된 경로가 없도록 v 에게 u, 따라서 G ~이다 크게 연결되지 않았습니다.

    • 모든 정점에 도달하면 v 그래프의 다른 모든 정점에 G.

  2. 지시 된 그래프의 모든 모서리의 방향을 바꾸십시오. G.

  3. 다시 실행하십시오 DFS 시작 v.

    • DFS가 모든 정점에 도달하지 못하면 일부 정점이 있습니다. u, 원래 그래프에는 지시 된 경로가 없습니다. u 에게 v.

    • 반면에, 모든 정점에 도달하면 원본 그래프에서 모든 정점에서 지시 된 경로가 있습니다 u 에게 v.

따라서 G가 두 DFS를 "통과"하면 강력하게 연결됩니다. 또한 DFS가 실행되기 때문에 O(n + m) 시간,이 알고리즘은 실행됩니다 O(2(n + m)) = O(n + m) 시간, 2 개의 DFS 트래버스가 필요하기 때문입니다.

모든 노드에 주어진 그래프에서 다른 모든 노드와의 경로가 있는지 확인합니다.

1. 모든 노드의 DFS/BFS :

타잔의 알고리즘 모든 노드에 깊이가 있다고 가정합니다 d[i]. 처음에는 뿌리가 가장 작은 깊이를 가지고 있습니다. 그리고 우리는 포스트 주문 DFS 업데이트를합니다 d[i] = min(d[j]) 모든 이웃을 위해 j 의 i. 실제로 BFS는 또한 축소 규칙과 함께 잘 작동합니다 d[i] = min(d[j]) 여기.

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

전달 경로가있는 경우 u 에게 v, 그 다음에 d[u] <= d[v]. SCC에서 d[v] <= d[u] <= d[v], 따라서 SCC의 모든 노드는 동일한 깊이를 갖습니다. 그래프가 SCC인지 여부를 알리기 위해 모든 노드가 동일한 지 확인합니다. d[i].

2. 단일 노드에서 두 개의 DFS/BFS :

단순화 된 버전입니다 Kosaraju의 알고리즘. 루트에서 시작하여 모든 노드에 DFS/BFS에 도달 할 수 있는지 확인합니다. 그런 다음 모든 모서리의 방향을 바꾸십시오. 모든 노드가 같은 루트에서 다시 도달 할 수 있는지 확인합니다. 보다 C ++ 코드.

당신은 다음을 계산할 수 있습니다 모든 페어 최단 경로 그리고 어떤 것이 무한한 지 확인하십시오.

Tarjan의 알고리즘이 이미 언급되었습니다. 그러나 나는 보통 발견합니다 Kosaraju의 알고리즘 그래프의 두 개의 횡단이 필요하더라도 따라갈 수 있습니다. IIRC, 그것은 또한 CLRS에서 잘 설명되어 있습니다.

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

이것을하는 한 가지 방법은 라플라시안 매트릭스 그래프의 경우 고유 값을 계산하고 마지막으로 0을 계산하십시오. 하나의 제로 고유 값 만 존재하면 그래프가 강력하게 연결됩니다.

참고 : 지시 된 그래프에 대한 Laplacian 행렬을 작성하는 약간 다른 방법에주의하십시오.

그래프의 두 DFS 트래버스를 수행하는 Kosaraju의 DFS 기반 간단한 알고리즘을 사용할 수 있습니다.

아이디어는 모든 노드에서 정점 V에서 도달 할 수 있고 모든 노드가 V에 도달 할 수 있다면 그래프가 강력하게 연결됩니다. 알고리즘의 2 단계에서 v에서 모든 정점이 도달 할 수 있는지 확인합니다. 4 단계에서는 모든 정점이 V에 도달 할 수 있는지 확인합니다 (모든 정점이 V에서 도달 할 수있는 경우 모든 정점이 v에 도달 할 수 있습니다. 그래프).

알고리즘 : 1) 방문하지 않은대로 모든 정점을 초기화합니다.

2) 임의의 vertex v에서 시작하는 DFS Traversal을 수행하십시오. DFS Traversal이 모든 정점을 방문하지 않으면 False를 반환하십시오.

3) 모든 아크를 역전 시키십시오 (또는 그래프의 전환 또는 반대로 찾기)

4) 반전 된 그래프에서 모든 정점을 방문하지 않은 것으로 표시하십시오.

5) 동일한 vertex v (2 단계와 동일)에서 시작하여 역전 된 그래프의 DFS 트래버스를 수행합니다. DFS Traversal이 모든 정점을 방문하지 않으면 False를 반환하십시오. 그렇지 않으면 True를 반환합니다.

시간 복잡성 : 위의 구현의 시간 복잡성은 그래프가 인접력 목록 표현을 사용하여 표시되는 경우 깊이의 첫 번째 검색과 동일합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top