2 сентября 2008 г.

Задачи на собеседованиях: графы

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

У нас есть ориентированный граф и его матрица смежности. Необходимо разработать алгоритм, вычисляющий количество узлов графа, участвующих в циклах. Речь идет просто о количестве узлов. Нас не интересуют ни количество циклов, ни количество узлов в каждом цикле. Только общее количество узлов, задействованных в циклах данного графа.

UDP: Кстати, найдя кол-во узлов мы сможем ответить на общий вопрос о наличии цикла в графе. Иногда вопрос звучит именно так.

2 комментария:

  1. по-моему, топологическая сортировка подойдёт:
    1. Помещаем все вершины в которых нет входящих дуг в очередь
    2. Пока очередь не пуста:
    - извлекаем вершину из очереди
    - уменьшаем количество входящих дуг во всех вершинах смежных с данной. Те вершины, у которых количество входящих дуг стало равным 0 - помещаем в очередь.
    3. Те вершины, у которых количество входящих дуг осталось не равным 0 - образуют циклы

    ОтветитьУдалить
  2. Я вообще-то не специалист по графам, поэтому я не знаю, как правильно :)

    Я решал эту задачу примерно так же. Только еще, имхо, нужно отбрасывать узлы, в которых нет исходящих дуг.

    И очередь я не организовывал - просто циклично проходил по матрице, отбрасывал узлы с нулевыми столбцами/строками. Когда в матрице таких узлов больше нет - оставшиеся и есть наши искомые узлы. Хотя, кажется, смысл тот же.

    ОтветитьУдалить