Существует ли эффективный алгоритм, который принимает на вход ориентированный циклический граф и возвращает размер каждого подграфа, происходящего из каждого из узлов? Под «эффективным» я подразумеваю нечто более эффективное, чем выполнение DFS на каждом из узлов.
Размер каждого подграфа, происходящего из каждого узла в ориентированном циклическом графе
Ответы (1)
Время поиска в глубину пропорционально количеству ребер, достижимых из каждого узла, что потенциально равно O(E), поэтому выполнение поиска в глубину из каждого узла равно O(VE), где V — количество вершин, а E — количество ребер. Предполагая, что средний граф имеет O (V ^ 2) ребер, это O (V ^ 3) в среднем и худшем случае. В лучшем случае повторный поиск в глубину занимает время O(V) на графе без ребер.
Один из простых способов сделать это лучше — по крайней мере теоретически — использовать матрицу смежности. A, напишите единицы по диагонали так, чтобы каждый узел был достижим из самого себя, найдите и-или степень матрицы A^(V-1), а затем подсчитайте количество единиц в каждой строке. Временная сложность этого подхода:
- O(V^2) для построения матрицы смежности,
- O(f(V) * log V) для вычисления степени матрицы с использованием алгоритма возведения в квадрат и умножения для умножения матриц log V, где f(V) — сложность алгоритма умножения матриц,
- O(V^2) для подсчета единиц в каждой строке результата.
временная сложность матричного умножения может составлять всего O(n^2,373) в зависимости от того, какой алгоритм вы используете, поэтому общая сложность приведенного выше алгоритма составляет около O (V ^ 2,373 log V). Это превосходит повторяющиеся поиски в глубину в среднем и худшем случае, но не в лучшем случае.
Тем не менее, этот ответ является чисто теоретическим, потому что алгоритмы умножения матриц, которые достигают низкой временной сложности, обычно имеют довольно большие постоянные коэффициенты, так что на самом деле они не быстрее для матриц разумных размеров. Это также, вероятно, не лучшее, что вы можете сделать; но это отвечает на экзистенциальный вопрос «есть ли что-то более эффективное?».
person
kaya3
schedule
16.01.2020
Спасибо за быстрый ответ. Это отвечает на мой вопрос, если мы предположим, что средний граф относится к ребрам O (V ^ 2), что дает нам наихудший, а не средний случай. Конечно, любые комментарии о существовании оптимального (в среднем случае) алгоритма, решающего задачу, были бы очень признательны. Если такого алгоритма не существует, учитывая мое незнание теории графов, любые намеки на другие алгоритмы, которые потенциально могут быть адаптированы для решения проблемы, также будут полезны.
- person panos; 16.01.2020
O(V^2) ребер — это средний случай для случайного графа, а также наихудший случай; существует V(V-1)/2 возможных ребер, поэтому в случайном графе половина из них будет ребрами, а другая половина - неребрами, что дает среднее значение V(V-1)/4 ребер, которое находится в O (В^2). Если ваш график нарисован из какого-то другого распределения, в котором ребра не случайны (с фиксированной вероятностью), то возможно, что средний граф из этого распределения имеет меньше, чем O (V ^ 2) ребер; например, если ваш график всегда является деревом.
- person kaya3; 16.01.2020
