Как определить, связаны ли два узла?

Question

Я обеспокоен тем, что это может работать над проблемой NP-Complete. Я надеюсь, что кто-то может дать мне ответ относительно того, является ли это или нет. И я ищу больше ответа, чем просто да или нет. Я хотел бы знать почему. Если вы можете сказать: «По сути, это проблема« x », которая является / не является NP-Complete. (Ссылка на Википедию)»

(Нет, это не домашняя работа)

Есть ли способ определить, связаны ли две точки на произвольном неориентированном графе. например, следующее

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

Точки A, хотя M (без 'I') являются контрольными точками (как клапан в трубе природного газа), которые могут быть открыты или закрыты. '+' - это узлы (например, труба Т), и я думаю, что колодец и дом тоже являются узлами.

Я хотел бы знать, закрываю ли я произвольную контрольную точку (например, C), все ли скважина и дом все еще связаны (другие контрольные точки также могут быть закрыты). Например, если B, K и D закрыты, у нас все еще есть путь через A-E-J-F-C-G-L-M, и закрытие C отключит колодец и дом. Конечно; если только D был закрыт, закрытие только C не разъединяет Дом.

Другой способ выразить это, является ли C мостом / острым краем / перешейком?

Я мог бы рассматривать каждую контрольную точку как вес на графике (0 для открытого или 1 для закрытого); а затем найти кратчайший путь между скважиной и домом (результат> = 1 будет означать, что они были отключены. Существуют различные способы, которыми я могу закорочить алгоритм нахождения кратчайшего пути (например, сбросить путь, когда он достигнет 1, остановить когда мы ищем, у нас есть ЛЮБОЙ путь, соединяющий колодец с домом и т. д.) И, конечно, я также могу установить искусственный лимит на количество прыжков, которые нужно проверить, прежде чем сдаться.

Кто-то, должно быть, уже классифицировал подобные проблемы раньше, я просто скучаю по названию.

Answer 1

Похоже, ваше описание указывает на то, что вы просто заинтересованы в том, соединены ли два узла, а не в поиске кратчайшего пути.

Найти, если два узла соединены, относительно просто:

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 toDoSet
  Add it to doneSet
  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 2

См. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, ваш универсальный магазин для всех проблем, связанных с графиком. Я считаю, что ваша проблема на самом деле разрешима в квадратичное время.

Answer 3

Вам не нужен алгоритм Дейкстры для этой задачи, так как он использует кучу, которая не нужна и вводит коэффициент log (N) для вашей сложности. Это только поиск в ширину - не включайте закрытые ребра в качестве ребер.

Answer 4

Проблема поиска кратчайшего пути не является NP-полной. Она называется «проблема кратчайшего пути» (достаточно изначально), и для ее решения существует множество алгоритмов .

Проблема определения того, соединены ли два узла, также не является NP-полной. Вы можете использовать поиск в глубину, начиная с любого узла, чтобы определить, подключен ли он к другому узлу.

Answer 5

Предполагая, что у вас есть матрица смежности:

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

Где bool [i, j] = true, если между i и j есть открытый путь, а 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;
}

Вот рекурсивная версия алгоритма выше (написана на 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 6

Мне кажется, что вы нашли решение, но, возможно, я неправильно понял проблему. Если вы делаете так, как говорите, и называете закрытые ребра 1 весом, вы можете просто применить алгоритм Дейкстры, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. Это должно решить вашу проблему в O (E * lg (V))

Answer 7

не NP-завершено, решено известным решением - Алгоритм Дейкстры

Answer 8

Если все, что вам нужно, это определить, подключены ли 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 9

Я вижу, что вы получили ответ, что он определенно не является NP-Complete, и это тоже очень старый вопрос.

Однако я просто предложу другой подход к проблеме. Вы можете использовать непересекающиеся множества для этого. В большинстве случаев для данного сценария такой подход приведет к более быстрому времени, чем обход графика (это включает постоянное время для большого количества тестов). Однако построение графика может занять много времени, если используется объединение по рангу или сжатию пути.

Вы можете прочитать о структуре данных здесь .

Answer 10

Любой алгоритм кратчайшего пути графа будет излишним, если все, что вам нужно, - это найти, подключен ли узел к другому. Хорошая библиотека Java, которая выполняет это 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)));
}

Эта библиотека также предлагает все алгоритмы кратчайших путей.