Подсчет непересекающихся орграфов

У меня есть двумерный массив boolean[][] с именем matrix, который кодирует ориентированный граф так, что если matrix[i][j] == true, то вершина j соединена с вершиной i (обратное не обязательно верно) .
Я пытаюсь создать метод Java, который будет определять, сколько у меня непересекающихся ориентированных графов.

Итак, для примера, если вершина 0 была соединена с вершиной 1, а вершина 2 была соединена с вершиной 3 (<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array), у меня было бы 2 непересекающихся орграфа.

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


java arrays math directed-graph
person arshajii    schedule 22.05.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Начните со списка всех узлов в дереве. Считайте это вашими непосещенными узлами.

Затем повторяйте следующий процесс, пока ваш список непосещенных узлов не исчезнет.

  1. Создайте пустой набор, «набор узлов», для представления узлов, которые находятся в графе текущего узла.
  2. Выполнить поиск, начиная с текущего узла. Для каждого узла, с которым вы сталкиваетесь при поиске, удалите его из списка непосещенных узлов, затем: (1) если узел уже существует в другом наборе узлов, объедините текущий набор узлов и этот другой набор узлов и остановите поиск с этот узел, или (2) если этот узел уже существует в текущем наборе узлов, остановите поиск с этого узла, или (3) если вы никогда не видели этот узел, добавьте его в текущий набор узлов.

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

person cheeken    schedule 22.05.2012

arrow_upward
1
arrow_downward

Кажется, что вам не нужно сильное соединение, поэтому очень эффективный алгоритм для непересекающихся лесов сделает дело. После фазы объединения вам нужно будет только подсчитать узлы с parent = self

P.S. лекция Седжвика об этом

person MBo    schedule 22.05.2012