vopros wrote:
1) Describe how you would find whether there is a loop in the graph
Поиск цикла в орграфе - это просто банальный поиск в глубину (DFS). С стандартной DFS-терминологии ("белые", "серые" и "черные" вершины), в графе есть цикл если и только если в процессе DFS вы, пройдя через очередное ребро, наткнулись на "серую" вершину.
Андрей вот бы вы еще пример кода привели, было бы просто замечательно.
Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
в рамках предложенного решения, следует ли окрашивать ноды попавшие в цикл в цвет отличный от черного (например красный) ?
для того чтобы знать является ли эта черная нода часть цикла или же я там прошел успешно.
Вывести нужно все циклы
vopros wrote:
в рамках предложенного решения, следует ли окрашивать ноды попавшие в цикл в цвет отличный от черного (например красный) ?
для того чтобы знать является ли эта черная нода часть цикла или же я там прошел успешно.
Вывести нужно все циклы
Ну если хочется все циклы именно вывести/пометить и именно все, то, наверное, можно их и красить в красный. Т.е. если мы увидели при проходе вниз серый нод, мы знаем, что это начало цикла. мы можем его запомнить и двигаться наверх, попутно окрашивая все в красный (или выводя на экран), до тех пор, пока не вернемся на него, после чего продолжить обход, как ни в чем не бывало - ловить другие циклы
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
2) как покрасить чёрным хвостик с которого начинали если он не является частью loop?
Пока что у меня идея - после нахождения loop продолжаем красить уже из серого в чёрный; тупики при возврате перекрашиваем обратно в серый; как находит чёрный всё, loop чёрные ноды, выходим из циклов/рекурсий без каких либо действий по покраске.
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
2) как покрасить чёрным хвостик с которого начинали если он не является частью loop?
Пока что у меня идея - после нахождения loop продолжаем красить уже из серого в чёрный; тупики при возврате перекрашиваем обратно в серый; как находит чёрный всё, loop чёрные ноды, выходим из циклов/рекурсий без каких либо действий по покраске.
вот вам пример. Есть 2 пути и оба не зацикливаются
сначала проходим A-B-C-D-F
Затем идем B-E-D - вопрос: какого цвета буде D? - тут мы были, цикла нет.
You do not have the required permissions to view the files attached to this post.
Это если у нас ответлений только 2, и мы начинаем с одного и ищем другое. Теперь, прошли B-E-D, нашли D - как нам пометить, что C часть петли? И как не включить A?
Я вижу так. Берём произвольныю ноду и идём от неё вглубь перебирая каждую хорду, красим в серый: C-D-F-D-E-B-A-B-C. Нашли серый, значит есть петля. Продолжаем идти дальше, только уже красим в чёрный: C-D-F-(тупик, возвращаемся, F возвращаем в серый)-D-E-B-C. Дошли до чёрного - всё, все чёрные образую петлю.
Подходит для любой сложности графа, начинать можем от любого элемента.
Есть менее трудоёмкое решение?
PS: Ну или красим тупики в чёрный, как находим серый разворачиваем всё взад ничего не перекрашивая, петля - серые.
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
2) как покрасить чёрным хвостик с которого начинали если он не является частью loop?
Пока что у меня идея - после нахождения loop продолжаем красить уже из серого в чёрный; тупики при возврате перекрашиваем обратно в серый; как находит чёрный всё, loop чёрные ноды, выходим из циклов/рекурсий без каких либо действий по покраске.
1) красим в красное, пока не вернемся на тот нод, который был началом цикла. после этого возвращаясь еще выше будем опять красить в черное
2) потому что в красное мы красим только до тех пор, пока не вернулись в начало. поскольку циклов может быть несколько, нам нужно будет засовывать их в какой-нибудь стек или что-то типа того
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
2) как покрасить чёрным хвостик с которого начинали если он не является частью loop?
Пока что у меня идея - после нахождения loop продолжаем красить уже из серого в чёрный; тупики при возврате перекрашиваем обратно в серый; как находит чёрный всё, loop чёрные ноды, выходим из циклов/рекурсий без каких либо действий по покраске.
вот вам пример. Есть 2 пути и оба не зацикливаются
сначала проходим A-B-C-D-F
Затем идем B-E-D - вопрос: какого цвета буде D? - тут мы были, цикла нет.
Ну, мы прошли A-B-C-D-F, на обратном пути красим в черный F, D, C. потом идем B-E и упираемся в черный D - там уже были, циклов нет. возвращаемся, красим в черный E,B,A
Alex M. Jake wrote:Это если у нас ответлений только 2, и мы начинаем с одного и ищем другое. Теперь, прошли B-E-D, нашли D - как нам пометить, что C часть петли? И как не включить A?
Я вижу так. Берём произвольныю ноду и идём от неё вглубь перебирая каждую хорду, красим в серый: C-D-F-D-E-B-A-B-C. Нашли серый, значит есть петля. Продолжаем идти дальше, только уже красим в чёрный: C-D-F-(тупик, возвращаемся, F возвращаем в серый)-D-E-B-C. Дошли до чёрного - всё, все чёрные образую петлю.
Подходит для любой сложности графа, начинать можем от любого элемента.
Есть менее трудоёмкое решение?
PS: Ну или красим тупики в чёрный, как находим серый разворачиваем всё взад ничего не перекрашивая, петля - серые.
Черный в нашей легенде - те ветки, которые проверили и петель там нет. Белый - ноды, где не были еще. Серый - те, которые в процессе проверки. Три "цвета" нужно, чтобы найти сам факт наличия петель. Четвертый нужен, чтобы их покрасить
avitya wrote:Для нахождения факта, что петля есть нужно 2 цвета, "видел"/"невидел", и на следующем шаге будь то дфс или бфс, если нода уже виденная, то цикл есть.
не сработает, взгляните на картинку выше, нода D виденная, а циклов нет.
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
Ни во что не красим. И никакого "красного" не надо. В постановке задачи не было ни требования перечисления всех циклов, ни требования перечисления вершин первого найденного цикла. В постановке задачи требовалось лишь ответить на вопрос о том, есть ли в графе хоть один цикл. Поэтому, встретив при обходже "серую" вершину, мы уже ничего не красим, а просто тут же завершаем алгоритм с ответом "да, в графе есть цикл".
АццкоМото wrote:Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное
Не очень понятно:
1) во что красим когда раскручиваем всё назад после нахождения loop?
Ни во что не красим. И никакого "красного" не надо. В постановке задачи не было ни требования перечисления всех циклов, ни требования перечисления вершин первого найденного цикла. В постановке задачи требовалось лишь ответить на вопрос о том, есть ли в графе хоть один цикл. Поэтому, встретив при обходже "серую" вершину, мы уже ничего не красим, а просто тут же завершаем алгоритм с ответом "да, в графе есть цикл".
то что цикл есть, это уже всем было понятно до программиста, задача программиста была найти где.
Да постановка задачи не самая лучшая.
В идеале должны даваться тестовые входные и выходные данные.
Но интервьювер на это, к сожалению, редко способен.
Я написал вариант с нахождением всех циклов. Правда без закрашивания.
С закрашиванием было бы оптимальнее.
vopros wrote:
Я написал вариант с нахождением всех циклов. Правда без закрашивания.
Меня когда в Квалкомме спрашивали, я минут 10 кряхтел, пытаясь одним "цветом" обойтись (для просто есть циклы/нету) Наверное, это потешно смотрелось, за то было очевидно, что сам допетрил
vopros wrote:
Я написал вариант с нахождением всех циклов. Правда без закрашивания.
Меня когда в Квалкомме спрашивали, я минут 10 кряхтел, пытаясь одним "цветом" обойтись (для просто есть циклы/нету) Наверное, это потешно смотрелось, за то было очевидно, что сам допетрил
vopros wrote:
Я написал вариант с нахождением всех циклов. Правда без закрашивания.
Меня когда в Квалкомме спрашивали, я минут 10 кряхтел, пытаясь одним "цветом" обойтись (для просто есть циклы/нету) Наверное, это потешно смотрелось, за то было очевидно, что сам допетрил
Ну я фиг его знает. Может, он и простой, но в классическом представлении графа, где каждый нод имеет указатели ссылки на 0+ других нодов, вот этот шаг весьма затруднителен:
if m has no other incoming edges then
т.к. мы for any given m we can easily find all the outgoing edges, not incoming
а второй алгоритм по ссылке - фактически как раз тот трехцветный, который впервые в ветке вслух назвал AndreyT
АццкоМото wrote:
т.к. мы for any given m we can easily find all the outgoing edges, not incoming
Ну это будет три строки кода предобработки.
Как это?
Заполнить структуру данных вроде Multimap<Long, Long> где ключ - вершина в которую входит ребро, а значение - из которой выходит, и из нее элементарно достается то что вам нужно
АццкоМото wrote:
т.к. мы for any given m we can easily find all the outgoing edges, not incoming
Ну это будет три строки кода предобработки.
Как это?
Заполнить структуру данных вроде Multimap<Long, Long> где ключ - вершина в которую входит ребро, а значение - из которой выходит, и из нее элементарно достается то что вам нужно
Ну и что мы получаем? Мы должны сделать один полный проход по дереву, чтобы заполнить эту структуру, а потом сделать еще один проход этим "простым" алгоритмом, в то время, как при "покраске" нам нужен 1 проход и по 2 бита на нод. Где ж тут простота?
АццкоМото wrote:
т.к. мы for any given m we can easily find all the outgoing edges, not incoming
Ну это будет три строки кода предобработки.
Как это?
Заполнить структуру данных вроде Multimap<Long, Long> где ключ - вершина в которую входит ребро, а значение - из которой выходит, и из нее элементарно достается то что вам нужно
Мы должны сделать один полный проход по дереву, чтобы заполнить эту структуру.
Очевидно это зависит от входного формата программу, может быть и лучше, может и хуже, или вообще одинаково если граф читается из файла.
crypto5 wrote:
Очевидно это зависит от входного формата программу, может быть и лучше, может и хуже, или вообще одинаково если граф читается из файла.
Разумеется, именно поэтому и было изначально сказано но в классическом представлении графа, где каждый нод имеет указатели ссылки на 0+ других нодов, вот этот шаг весьма затруднителен
crypto5 wrote:
Очевидно это зависит от входного формата программу, может быть и лучше, может и хуже, или вообще одинаково если граф читается из файла.
Разумеется, именно поэтому и было изначально сказано но в классическом представлении графа, где каждый нод имеет указатели ссылки на 0+ других нодов, вот этот шаг весьма затруднителен
Ок, в таком представлении он действительно будет затруднителен, правда это уже дополнительное условие к исходной задаче, и представление о котором вы говорите далеко не единственное "классическое".
Не знаю как у них там технари и программеры -может все из себя и шибко умные, а рекрутинг с эйчаром не упускают возможности чудить по-полной... чудаки на букву М.
Наверное, это потешно смотрелось, за то было очевидно, что сам допетрил
