Поиск пути на направленном графе

Опубликовано Sep 30, 2011 в Деревья и графы | Нет комментариев


Поиск пути на направленном графе

Дан направленный граф. Напишите функцию, которая могла бы ответить – есть ли путь между двумя заданными вершинами.

1 Цель задания быстрая проверка базовых знаний основных структур данных, алгоритмов и средств их реализации
2 Время выполнения 30 минут
3 Формат выполнения код пишется на компьютере или бумаге по выбору, без доступа к документации

Критерии оценки FulcrumWeb:

Нужно продемонстрировать знание стандартных алгоритмов обхода графов.

Ожидаемые вопросы:

  1. Нужно ли использовать какую-то определенную структуру данных для хранения графа или я могу выбрать любой вариант? Можно ли использовать STL контейнеры?
  2. Одинакова ли стоимость перемещения по любому из ребер?
  3. Можно ли считать, что в графе нет циклов?

Оценка результатов:

В условии нет никаких намеков, на то как хранить граф, как нет и сигнатуры функции. Поэтому, если предоставлена полная свобода (ответ на первый вопрос) и не нужно искать сам путь, то существует очень простое решение, основанное на возведение в степень матрицы инциденций графа, которое можно знать как готовое, но маловероятно изобрести на ходу. Недостатки этого решения – требуется много памяти и оно очень затратно по времени.

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

Для начинающего программиста годится любая реализация с использование любой структуры данных, возможно содержащая ошибки, которые будут исправлены после указания на них. В решении обязательно не должно быть утечек памяти.

Для более опытного кандидата, особенно, если заявлен опыт работы с подобными структурами данных, приветствуется решение, основанное на хранении графа в виде связных структур данных. Замечательно, если будет дана оценка сложности реализованного алгоритма.


Оставить комментарий

Ваш адрес email не будет опубликован.


*