Làm thế nào để xác định xem hai nút được kết nối?

Question

Tôi lo ngại rằng điều này có thể đang khắc phục sự cố NP-Complete. Tôi hy vọng ai đó có thể cho tôi câu trả lời là liệu nó có hay không. Và tôi đang tìm kiếm câu trả lời nhiều hơn là chỉ có hoặc không. Tôi muốn biết tại sao. Nếu bạn có thể nói: "Đây là cơ bản vấn đề này 'x' là/không phải là NP-đầy đủ. (Wikipedia liên kết)"

(Không đây không phải là bài tập về nhà)

Có cách nào để xác định xem hai điểm được kết nối trên một đồ thị phi định hướng tùy ý. ví dụ, sau đây

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

Điểm A mặc dù M (không 'Tôi') là những điểm kiểm soát (như một van trong một đường ống khí đốt tự nhiên) mà có thể là đóng hoặc mở. Các '+' là các nút (như ống T), và tôi đoán Well và House cũng là các nút.

Tôi muốn biết nếu tôi đóng một điểm điều khiển tùy ý (ví dụ: C) cho dù Nhà và giếng vẫn được kết nối (các điểm điều khiển khác cũng có thể bị đóng). Ví dụ: nếu B, K và D bị đóng, chúng tôi vẫn có đường dẫn qua A-E-J-F-C-G-L-M và đóng C sẽ ngắt kết nối giếng và nhà. Tất nhiên; nếu chỉ D bị đóng, chỉ đóng C không ngắt kết nối Nhà.

Một cách khác để đặt điều này, là C cầu/cạnh cắt/eo đất?

Tôi có thể coi mỗi điểm điều khiển là trọng số trên biểu đồ (hoặc 0 để mở hoặc 1 cho đã đóng); và sau đó tìm đường đi ngắn nhất giữa Well và House (kết quả> = 1 sẽ chỉ ra rằng chúng đã bị ngắt kết nối. Có nhiều cách khác nhau để tôi có thể rút ngắn thuật toán để tìm đường đi ngắn nhất (ví dụ: loại bỏ đường đi khi nó đạt đến 1, dừng lại tìm kiếm một khi chúng tôi có BẤT K path con đường nào kết nối giếng và nhà, vv .. Và tất nhiên, tôi cũng có thể đặt một số giới hạn nhân tạo về số lần kiểm tra trước khi bỏ cuộc.

Ai đó phải phân loại loại này của vấn đề trước, tôi chỉ thiếu tên

Answer 1

Xem http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, trên của bạn e stop cửa hàng cho tất cả các vấn đề liên quan đến đồ thị. Tôi tin rằng vấn đề của bạn là trong thực tế giải quyết trong thời gian bậc hai.

Answer 2

không NP-đầy đủ, giải quyết với một giải pháp nổi tiếng -. Dijkstra's Algorithm

Answer 3

Đối với tôi, có vẻ như bạn đang ở một giải pháp, nhưng có thể tôi đã hiểu nhầm vấn đề. Nếu bạn làm như bạn nói, và cung cấp cho các cạnh khép kín 1 như trọng lượng, bạn chỉ có thể áp dụng thuật toán Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. Điều này sẽ giải quyết vấn đề của bạn trong O (E * lg (V))

Answer 4

Vấn đề tìm đường đi ngắn nhất không phải là NP-complete. Nó được gọi là vấn đề con đường ngắn nhất (ban đầu đủ) và có algorithms để giải quyết nhiều biến thể khác nhau của nó.

Vấn đề xác định xem hai nút được kết nối không phải là NP-hoàn thành hay không. Bạn có thể sử dụng tìm kiếm độ sâu đầu tiên bắt đầu từ một trong hai nút để xác định xem nó có được kết nối với nút khác hay không.

Answer 5

Mô tả của bạn dường như chỉ ra rằng bạn chỉ quan tâm đến việc liệu hai nút có được kết nối không, không tìm đường đi ngắn nhất.

Tìm nếu hai nút được kết nối là tương đối dễ dàng:

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. 

Nếu bạn sử dụng một bảng băm hoặc một cái gì đó tương tự cho toDoSet và doneSet, tôi tin rằng đây là một thuật toán tuyến tính.

Lưu ý rằng thuật toán này về cơ bản là phần đánh dấu của bộ sưu tập rác đánh dấu và quét.

Answer 6

Bạn không cần thuật toán Dijkstra cho vấn đề này, vì nó sử dụng một Heap mà không cần thiết và giới thiệu một yếu tố của log (N) phức tạp của bạn. Đây chỉ là tìm kiếm đầu tiên - không bao gồm các cạnh được đóng dưới dạng cạnh.

Answer 7

Giả sử rằng bạn có một ma trận kề:

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

đâu [i, j] = true bool nếu có một con đường mở giữa i và j và bool [i, i] = false.

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; 
} 

Đây là một phiên bản đệ quy của thuật toán ở trên (viết bằng Ruby):

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

Dijkstra là quá mức cần thiết !! Chỉ cần sử dụng tìm kiếm rộng đầu tiên từ A để tìm kiếm nút bạn muốn tiếp cận. Nếu bạn không thể tìm thấy nó, nó không được kết nối. Độ phức tạp là O (nm) cho mỗi tìm kiếm, ít hơn so với Dijkstra.

Hơi có liên quan là vấn đề tối đa luồng/phút cắt. Nhìn nó lên, nó có thể liên quan đến vấn đề của bạn.

Answer 9

Nếu tất cả những gì bạn cần là để xác định xem có phải 2 nút được kết nối, bạn có thể sử dụng các tập thay thế, nhanh hơn thuật toán đồ thị hay không.

1. Chia toàn bộ biểu đồ thành các cạnh. Thêm từng cạnh vào một tập hợp.
2. Trên lần lặp tiếp theo, vẽ cạnh giữa 2 nút ngoài của cạnh bạn đã thực hiện ở bước 2. Điều này có nghĩa là thêm các nút mới (với các tập tương ứng của chúng) vào tập hợp cạnh gốc. (về cơ bản thiết lập hợp nhất)
3. Lặp lại 2 cho đến khi 2 nút bạn đang tìm nằm trong cùng một tập hợp. Bạn cũng sẽ cần phải làm một kiểm tra sau bước 1 (chỉ trong trường hợp 2 nút liền kề).

Lúc đầu nút của bạn sẽ được mỗi trong bộ của nó,

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 

Như thuật toán tiến triển và kết hợp các bộ, nó tương đối giảm một nửa lượng đầu vào.

Trong ví dụ trên, tôi đang tìm xem có đường đi giữa o1 và o2 không. Tôi tìm thấy con đường này chỉ ở cuối sau khi sáp nhập tất cả các cạnh. Một số đồ thị có thể có các thành phần riêng biệt (bị ngắt kết nối) đòi hỏi bạn sẽ không thể có một bộ ở cuối. Trong trường hợp này, bạn có thể sử dụng thuật toán này để kiểm tra tính kết nối và thậm chí đếm số thành phần trong biểu đồ. Số lượng thành phần là số bộ bạn có thể nhận được khi thuật toán kết thúc.

Một đồ thị có thể (đối với cây trên):

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

Answer 10

Bất kỳ đồ thuật toán tìm đường ngắn nhất sẽ là quá mức cần thiết nếu bạn chỉ cần có để tìm thấy nếu một nút được kết nối với nhau. Một thư viện Java tốt hoàn thành đó là JGraphT. Cách sử dụng của nó khá đơn giản, đây là ví dụ về biểu đồ Số nguyên:

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 này cũng cung cấp tất cả thuật toán đường đi ngắn nhất.