Описание тега kosaraju-algorithm

Вопросы с тегом
Алгоритм линейного времени для поиска сильно связных компонент ориентированного графа
1 ответ

Алгоритм Косараю для SCCs, не рекурсивный

У меня есть реализация алгоритма Косараю для поиска SCC в Python. Приведенный ниже код содержит рекурсивную (отлично подходит для небольших тестовых случаев) версию и нерекурсивную (которая мне в конечном счете нужна из-за размера реального набора д…
17 дек '18 в 11:12
0 ответов

Размер (число ребер) сильно связных компонент (SCC) в графе с использованием алгоритма Косараю

Я кодировал двухпроходный алгоритм Косараю в Python 3, текущая реализация находит SCC и определяет размер каждого SCC на основе количества узлов в каждом SCC. Затем определяются самые большие SCC. Как я могу изменить код, чтобы он мог рассчитать раз…
17 янв '19 в 04:30
1 ответ

Алгоритм Косараю для поиска SCC, но отслеживать границу между SCC?

В настоящее время у меня есть рабочая реализация алгоритма Косараджи, которая, учитывая ориентированный граф без весов, будет печатать SCC в графе. Я хотел бы адаптировать его так, чтобы он также указывал, где находятся границы между SCC. Вот код: f…
06 ноя '17 в 11:43
3 ответа

Хвостовая рекурсия в F#: переполнение стека

Я пытаюсь реализовать алгоритм Косараджу на большом графике как часть задания [MOOC Algo I Stanford on Coursera] https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm Текущий код работает на небольшом графике, но я нажимаю на переполнение стека во вр…
19 янв '16 в 15:59
3 ответа

Как преодолеть проблему переполнения стека при поиске SCC?

Это код, который я написал, чтобы найти SCC, использующие двухпроходный алгоритм Косараджу. Когда я запускаю метод main, я получаю StackOverFlowError в SCC.revDFS. Как избежать ошибки переполнения стека при большом количестве рекурсивных вызовов? im…
01 май '17 в 22:02
1 ответ

Итеративная DFS на графике с порядком после посещения

В настоящее время я пытаюсь реализовать алгоритм Косараю на ориентированном графе, чтобы найти все сильно связанные компоненты. Я прекрасно понимаю, как работает этот алгоритм, но у меня есть некоторые проблемы при получении порядка DFS после посеще…
14 июн '18 в 11:47
1 ответ

Алгоритм Косараю для SCC

Может кто-нибудь объяснить мне логику алгоритма Косараю для поиска подключенного компонента? Я прочитал описание, хотя я не могу понять, как DFS на обращенном графике может определять количество сильно связанных компонентов. def dfs(visited, stack, …
08 дек '18 в 06:35
1 ответ

Нерекурсивная реализация двухпроходного алгоритма Косараю, выполняемая навсегда для большого набора данных

Я закодировал это для задания, которое прошло его крайний срок. Эта реализация прекрасно работает с различными меньшими тестовыми примерами и отображает размеры 5 самых сильных компонентов на графике, как и должно быть. Но, кажется, выполняется вечн…
13 дек '15 в 22:29
3 ответа

Зачем нам нужно запускать DFS на дополнении графа в алгоритме Косараю?

Существует знаменитый алгоритм поиска сильно связанных компонентов, называемый Kosaraju's algorithm, который использует два DFS для решения этой проблемы, и работает в θ(|V| + |E|) время. Сначала мы используем DFS для дополнения графа (G R) чтобы вы…
03 янв '14 в 10:15
0 ответов

Как я могу использовать BFS для поиска связанных компонентов в орграфе?

Я знаю, что kosaraju-алгоритм, который использует DFS, может найти связанные компоненты в графе. Но как насчет использования BFS вместо DFS? Например, может ли DFS быть заменена на BFS в алгоритме Косараю, и функциональная корректность алгоритма все…
05 май '17 в 15:32
0 ответов

Как найти действительный набор литералов из 2-SAT

это проблема 2-выполнимости. Я могу определить, удовлетворяются ли условия 2, используя алгоритм Косараю. Например, для первого теста, +1 +3 +2 -1 +2 -3 -1 -2 Я получил этот график импликации. Здесь я представил -1 до -3, используя узел 4-6. Итак, …
08 сен '17 в 08:31
1 ответ

Требуется шаблон регулярных выражений в JavaScript. Можете ли вы помочь кому-нибудь по этому требованию?

Требуется регулярное выражение как Pettern 1: разрешить только буквы с минимальной 1 точкой и максимум 3 точками. 2: разрешить необязательный как '-' специальный символ. Пример: raj.gopal-reddy или raj.reddy.gopal
28 май '19 в 05:57
1 ответ

2-SAT значения переменной

Задача 2-SAT, поиск значения для переменных Я использую это решение для нахождения удовлетворенности для данной формулы. (проверяя ГТК). Есть ли эффективный способ (эффективный означает не хуже, чем полиномиальное время в моем случае), как найти зна…
21 апр '19 в 14:42
0 ответов

Why my C++14 KosaRaju algo getting TLE when a similar written code runs much faster

TLE code completes at 2.1 secs. I'm also passing many things through reference but it's still throwing a TLE. Why this code takes so much time? here is the problem at hackerearth: https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed4…
13 апр '20 в 17:19
0 ответов

Как сделать список смежности из ОГРОМНОГО txt файла?

У меня есть ОГРОМНЫЙ файл, содержащий ребра ориентированного графа, и мне нужно составить список смежности, чтобы вычислить его сильно связанные компоненты с помощью алгоритма Косараджу. Проблема в том, что я не могу эффективно прочитать этот огромн…
06 май '20 в 14:05
0 ответов

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

Ниже приведен псевдокод алгоритма Косараджу для поиска всех сильно связанных компонентов в графе. В настоящее время он возвращает все вершины для каждого SCC. Как его изменить, чтобы он возвращал все ребра для каждого SCC stack STACK void DFS(int so…
12 июл '20 в 09:58
0 ответов

Сильно связанные компоненты - стек

Можно ли реализовать поиск сильно связанных компонентов на основе имеющегося у меня кода? Я не могу придумать, как это сделать. Я попытался реализовать Kosaraju, но безуспешно, потому что он рекурсивный и я использую стек. Все реализации Kosaraju ра…
08 июн '20 в 09:27
1 ответ

Алгоритм Косараджу - вычисление SCC

Для данного ориентированного графа G мне нужно вычислить его сильно связные компоненты (SCC), используя алгоритм Косараджу. Насколько я понял, шаги алгоритма следующие: Пусть Grev = G, все дуги перевернуты. Запустите DFS (поиск в глубину) на Grev, ч…
06 июл '20 в 12:38
0 ответов

Завершение выполнения кода - Сильно связанные компоненты - Kosaraju

Я нашел в сети код алгоритма Косараджу. Я понимаю общую идею алгоритма и могу следовать объяснениям на абстрактном уровне. Однако, когда дело доходит до самого кода, мой ограниченный опыт программирования не дает мне понять, что происходит. Я привед…
08 июн '20 в 12:45
0 ответов

Как я могу избавиться от этой проблемы переполнения стека в python для алгоритма Косараджу?

Я новый программист и прохожу Стэнфордский курс алгоритмов на edX. Одно из заданий программирования - найти компоненты сильной связности с использованием алгоритма Косараджу на графе с ~1000 000 вершин. Моя реализация - это самый простой перевод псе…
04 сен '20 в 01:07