두 노드가 연결되어 있는지 확인하는 방법은 무엇입니까?

Question

이 문제는 NP-Complete 문제에서 해결 될 수 있습니다. 나는 누군가가 내게 그것이 옳은지 아닌지에 대한 답을 줄 수 있기를 바라고있다. 그리고 저는 예 또는 아니오보다 더 많은 답을 찾고 있습니다. 이유를 알고 싶습니다. 당신이 말할 수있는 경우

있는지 확인하는 방법이 있나요

은 (없음이 숙제를하지 않습니다) "이것은 기본적으로이 문제에 'X'입니다/NP-완료. (위키 백과 링크) 아니다" 임의의 무향 그래프 상에 2 점이 접속되어있다. 예를 들어, 다음

Well 
    | 
    | 
    A 
    | 
    +--B--+--C--+--D--+ 
    |  |  |  | 
    |  |  |  | 
    E  F  G  H 
    |  |  |  | 
    |  |  |  | 
    +--J--+--K--+--L--+ 
        | 
        | 
        M 
        | 
        | 
        House 

점 A 비록 M (단, 'I')의 개폐가 될 수있다 (천연 가스 파이프, 밸브 등)의 제어 포인트가된다. 없다 '+'는 노드 (파이프 T와 같은)이며 Well과 House도 노드라고 생각합니다.

임의의 제어점 (예 : C)을 종료했는지 여부와 Well and House가 여전히 연결되어 있는지 (다른 제어점도 닫혀있을 수 있음) 알고 싶습니다. 예를 들어, B, K 및 D가 닫히면 A-E-J-F-C-G-L-M을 통해 경로가 있고 C를 닫으면 Cree와 House가 연결 해제됩니다. 당연하지; D가 닫히면 C 만 닫으면 집이 분리되지 않습니다.

이것을 삽입하는 또 다른 방법은 C 브리지/커팅 엣지/협부 (isthmus)입니까?

그래프에서 각 조절 점을 가중치로 처리 할 수 ​​있습니다 (열린 경우 0, 닫은 경우 1). 그리고 Well과 House 사이의 최단 경로를 찾는다 (결과> = 1은 연결이 끊어 졌음을 나타낼 것이다.) 최단 경로를 찾는 알고리즘을 단락시킬 수있는 다양한 방법이있다 (예를 들어, 경로가 1에 도달하면 폐기한다. 우리가 우물과 집 등을 연결하는 어떤 길을 찾으면 검색) 물론, 포기하기 전에 확인해야 할 홉 수에 대한 인위적인 제한을 넣을 수도 있습니다.

누군가가이 분류에 속해야합니다 이전 문제, 그냥 이름을 누락

Answer 1

이 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm을 참조 온을 모든 그래프 관련 문제에 대한 e stop shop. 나는 당신의 문제가 2 차적인 시간에서 풀 수 있다고 믿습니다.

Answer 2

하지 NP-완료, 잘 알려진 방법으로 해결할 -. Dijkstra's Algorithm

Answer 3

나에게는 해결책을 찾고있는 것 같지만 문제를 오해 한 것일 수 있습니다. 당신이 말하고, 닫힌 모서리 1을 가중치로 쓴다면 Dijkstra의 알고리즘 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm을 적용하면됩니다. 이 문제는 O (E * lg (V))에서 해결해야합니다.

Answer 4

가장 짧은 경로를 찾는 문제는 NP 완료되지 않습니다. 최단 경로 문제 (원래는 충분 함)라고 불리우며 다양한 변형을 해결하기 위해 algorithms이 있습니다.

두 노드가 연결되어 있는지 확인하는 문제는 NP 완성도 아닙니다. 두 노드 중 하나에서 시작하는 깊이 우선 검색을 사용하여 두 노드가 다른 노드에 연결되어 있는지 확인할 수 있습니다.

Answer 5

설명은 두 노드가 연결되어 있는지 여부와 가장 짧은 경로를 찾지 못했는지 여부 만 나타냅니다.두 개의 노드가 연결되어있는 경우 찾기

는

상대적으로 쉽다 :

Create two sets of nodes: toDoSet and doneSet 
Add the source node to the toDoSet 
while (toDoSet is not empty) { 
    Remove the first element from toDoList 
    Add it to doneList 
    foreach (node reachable from the removed node) { 
    if (the node equals the destination node) { 
     return success 
    } 
    if (the node is not in doneSet) { 
     add it to toDoSet 
    } 
    } 
} 

return failure. 

당신이 해시 테이블 또는 toDoSet 및 doneSet 비슷한 무언가를 사용하는 경우, 나는이 선형 알고리즘을 믿습니다.

이 알고리즘은 기본적으로 마크 앤 스위프 가비지 수집의 마크 부분입니다.

Answer 6

필요하지 않은 힙을 사용하고 복잡도에 log (N) 요소를 도입하므로 Dijkstra의 알고리즘이이 문제에 필요하지 않습니다. 이것은 폭 넓은 첫 검색 일뿐입니다. 닫힌 가장자리를 가장자리로 포함하지 마십시오.

Answer 7

는 인접성 매트릭스를 가지고 있다고 가정하면 : i와 j와 BOOL [I, I = 거짓 사이의 개방 통로가있는 경우 부울 [I, J]가 참 =

bool[,] adj = new bool[n, n]; 

.

public bool pathExists(int[,] adj, int start, int end) 
{ 
    List<int> visited = new List<int>(); 
    List<int> inprocess = new List<int>(); 
    inprocess.Add(start); 

    while(inprocess.Count > 0) 
    { 
    int cur = inprocess[0]; 
    inprocess.RemoveAt(0); 
    if(cur == end) 
     return true; 
    if(visited.Contains(cur)) 
     continue; 
    visited.Add(cur); 
    for(int i = 0; i < adj.Length; i++) 
     if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i)) 
     inprocess.Add(i); 
    } 
    return false; 
} 

여기 (루비로 작성) 상기 알고리즘 재귀 버전 :

def connected? from, to, edges 
    return true if from == to 
    return true if edges.include?([from, to]) 
    return true if edges.include?([to, from]) 

    adjacent = edges.find_all { |e| e.include? from } 
        .flatten 
        .reject { |e| e == from } 

    return adjacent.map do |a| 
    connected? a, to, edges.reject { |e| e.include? from } 
    end.any? 
end 

Answer 8

익스트라이 과도 함을! A에서 폭 넓은 첫 번째 검색을 사용하여 도달하려는 노드를 검색하십시오. 찾을 수 없다면 연결되어 있지 않습니다. 복잡성은 각 검색에 대해 O (nm)이며 Dijkstra보다 작습니다.

다소 관련이있는 것은 max-flow/min-cut 문제입니다. 그것을 보아라, 그것은 당신의 문제와 관련이 있을지도 모른다.

Answer 9

2 개의 노드가 연결되어 있는지 확인하는 것이 필요하면 그래프 알고리즘보다 빠른 집합을 사용할 수 있습니다.

1. 전체 그래프를 가장자리로 나눕니다. 각 모서리를 세트에 추가하십시오.
2. 다음 반복에서 2 단계에서 만든 모서리의 2 외부 노드 사이에 모서리를 그립니다. 이는 원래 모서리가 있던 세트에 새 노드를 추가하는 것을 의미합니다. (기본적으로 병합을 설정 함)
3. 찾고있는 2 개의 노드가 같은 세트에 들어갈 때까지 2를 반복하십시오. 1 단계 후에도 점검해야합니다 (2 개의 노드가 인접한 경우). 알고리즘이 진행하고 세트를 병합으로 먼저 노드가 세트의 각 될 것입니다에서

,

o o1 o o o o o o2 
\/ \/ \/ \/
o o  o o  o o  o o 
    \ /  \ /
    o o o o   o o o o 
     \    /
     o o1 o o o o o o2 

, 그것은 상대적으로 입력을 반으로.

위의 예에서 o1과 o2 사이에 경로가 있는지 확인하려고했습니다. 모든 경로를 병합 한 끝에이 경로 만 찾았습니다. 일부 그래프에는 분리 된 구성 요소가있을 수 있습니다 (연결이 끊어짐). 결국 하나의 세트를 가질 수 없습니다. 이 경우이 알고리즘을 사용하여 연결성을 테스트하고 그래프의 구성 요소 수를 계산할 수도 있습니다. 구성 요소의 수는 알고리즘이 완료 될 때 얻을 수있는 세트 수입니다.

(위의 트리) 가능한 그래프 : 당신이 필요로하는 모든 노드가 서로 연결되어 있는지 찾을 경우

o-o1-o-o-o2 
    | | 
    o o 
     | 
     o 

Answer 10

모든 그래프 최단 경로 알고리즘은 잔인한 것입니다. 그 좋은 자바 라이브러리는 JGraphT입니다. 그것은 여기에, 사용이 매우 간단합니다의 정수 그래프의 예 :

public void loadGraph() { 
    // first we create a new undirected graph of Integers 
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class); 

    // then we add some nodes 
    graph.addVertex(1); 
    graph.addVertex(2); 
    graph.addVertex(3); 
    graph.addVertex(4); 
    graph.addVertex(5); 
    graph.addVertex(6); 
    graph.addVertex(7); 
    graph.addVertex(8); 
    graph.addVertex(9); 
    graph.addVertex(10); 
    graph.addVertex(11); 
    graph.addVertex(12); 
    graph.addVertex(13); 
    graph.addVertex(14); 
    graph.addVertex(15); 
    graph.addVertex(16); 

    // then we connect the nodes 
    graph.addEdge(1, 2); 
    graph.addEdge(2, 3); 
    graph.addEdge(3, 4); 
    graph.addEdge(3, 5); 
    graph.addEdge(5, 6); 
    graph.addEdge(6, 7); 
    graph.addEdge(7, 8); 
    graph.addEdge(8, 9); 
    graph.addEdge(9, 10); 
    graph.addEdge(10, 11); 
    graph.addEdge(11, 12); 
    graph.addEdge(13, 14); 
    graph.addEdge(14, 15); 
    graph.addEdge(15, 16); 

    // finally we use ConnectivityInspector to check nodes connectivity 
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph); 

    debug(inspector, 1, 2); 
    debug(inspector, 1, 4); 
    debug(inspector, 1, 3); 
    debug(inspector, 1, 12); 
    debug(inspector, 16, 5); 
} 

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) { 
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2))); 
} 

이 LIB는 또한뿐만 아니라 모든 최단 경로 알고리즘을 제공합니다.