Определить цикл в направленном графике из текстового файла
Я пытаюсь прочитать значения из текстового файла, а затем определить, является ли график, который он представляет, DAG или нет. Мне интересно, какой самый быстрый способ приблизиться к этому с точки зрения эффективности времени.
Вот текстовый файл
3
2
1,2,
2,3
Я думал о составлении списка смежности с заданной информацией, а затем оттуда ушел. Любая помощь с благодарностью
Решение
Один из способов, хотя и не самый быстрый, — это топологически сортировать график. Граф имеет цикл тогда и только тогда, когда алгоритм терпит неудачу (см. Алгоритм Кана).
Время работы O(|V| + |E|), где |V| это число вершин и |E| количество ребер
Есть статья Бендера и соавторов. (Роберт Тарьян — один из авторов), НОВЫЙ ПОДХОД К ОБНАРУЖЕНИЮ ЦИКЛОВОГО ОБНАРУЖЕНИЯ И РОДСТВЕННЫХ ПРОБЛЕМ, на который вы, возможно, захотите взглянуть.
Другой соответствующий документ Обнаружение инкрементного цикла, топологическое упорядочение и тщательное обслуживание компонентов Bu Haeupler et al. (Тарьян снова один из авторов).
Другие решения
Вы можете просто пройти весь граф, используя Поиск в глубину. Общая сложность времени O (| V | + | E |), | V | и | E | будучи числом вершин и ребер, соответственно.
При прохождении графа с использованием DFS вы встретите 3 типа вершин:
- Те, на которых ты еще не ступил.
- Те, которые вы сейчас открываете. (то есть или себя или своих детей)
- Те, которые вы полностью исследовали (т.е. включая его потомков)
При реализации DFS вы можете отслеживать, в каком состоянии находится каждая вершина в данный момент времени, что обычно называется раскраска вершины. В основном вершины, которые вы не начали исследовать (тип 1), будут белыми, те, которые вы исследуете, будут серыми, а те, которые вы полностью обнаружили (т.е. исчерпаны), будут черными.
На соответствующем примечании, когда ваша DFS работает, она встретит 4 типа ребер в зависимости от типа их исходных и конечных вершин, src и dest, соответственно.
- Край дерева: src имеет тип 2 и dest имеет тип 1
- Задний край: src имеет тип 2 и dest имеет тип 2
- Передний край: src имеет тип 2, dest имеет тип 3, а src является предком dest
- Cross Edge: src типа 2, dest типа 3 и src не предок дест
Хотя они подробно изложены в графах алгоритмов разделы большинства учебников алгоритмов, передние и поперечные края не совсем соответствуют вашим потребностям. Все, что вам нужно учитывать, это отслеживать, сталкивались ли вы с задний край(то есть от серой вершины до другой серой вершины), когда вы пересекаете дерево.
Если вы сталкиваетесь с задним краем, это означает, что у вас есть возможность выйти из вершины U своему предку v. Предок чувствует себя немного странно в этом контексте, так как это не дерево, а граф. Тем не менее, имея в виду, что направленные ребра как бы образуют отношения, аналогичные тем, которые имеют родительские и дочерние узлы в дереве, может быть более интуитивно понятно понять идею. Ведь ребра типа 1 называются края дерева по причине, верно?
Подводя итог, исследовать все вершины с поиском по глубине (т. е. не сдавайтесь после того, как исследуете одну дерево в вашем графике) и искать задний край. Если вы найдете один, у вас есть цикл.