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

Я обеспокоен тем, что это может работать над проблемой NP-Complete. Я надеюсь, что кто-то может дать мне ответ, есть ли это или нет. И я ищу больше ответа, чем просто да или нет. Хотелось бы знать, почему. Если вы можете сказать: "Это в основном эта проблема" x ", которая/не является NP-Complete (ссылка на wikipedia)"

(Нет, это не домашнее задание)

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

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

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

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

Другим способом для этого является C-мост/режущий край/перешеек?

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

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

10 ответов

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


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

Обнаружено, что соединение двух узлов относительно просто:

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, я считаю, что это линейный алгоритм.

Обратите внимание, что этот алгоритм в основном является меткой части сбора мусора маркировки и прокрутки.


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


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

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


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


не NP-полный, разрешенный с помощью известного решения - Dijkstra Algorithm


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

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

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

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


Дейкстра - это излишество!! Просто используйте ширину первого поиска из A, чтобы найти node, который вы хотите достичь. Если вы не можете найти его, он не подключен. Сложность - O (nm) для каждого поиска, что меньше, чем Dijkstra.

В некоторой степени это проблема с максимальным потоком/минимумом. Посмотрите, это может быть актуально для вашей проблемы.


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

  • Разделить весь граф на ребра. Добавьте каждое ребро в набор.
  • На следующей итерации нарисуйте края между двумя внешними узлами края, которые вы сделали на шаге 2. Это означает добавление новых узлов (с их соответствующими наборами) в набор, из которого был исходный край. (в основном слияние)
  • Повторите 2 до тех пор, пока 2 узла, которые вы ищете, не будут в одном наборе. Вам также необходимо выполнить проверку после шага 1 (на всякий случай, если два узла смежны).

Сначала ваши узлы будут каждый в своем наборе,

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


Любой алгоритм кратчайшего пути графика будет излишним, если вам нужно только выяснить, подключен ли node к другому. Хорошая библиотека 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 ********************* to check nodes connectivity
 *********************<integer, defaultedge=""> inspector = new *********************<>(graph);
 debug(inspector, 1, 2);
 debug(inspector, 1, 4);
 debug(inspector, 1, 3);
 debug(inspector, 1, 12);
 debug(inspector, 16, 5);
}
private void debug(*********************<integer, defaultedge=""> inspector, Integer n1, Integer n2) {
 System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}
</integer,></integer,></integer,>

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

licensed under cc by-sa 3.0 with attribution.