Задача про графы, которую часто задают на собеседованиях. Для людей, которые ранее не сталкивались с графами, неплохая разминка для мозгов.
У нас есть ориентированный граф и его матрица смежности. Необходимо разработать алгоритм, вычисляющий количество узлов графа, участвующих в циклах. Речь идет просто о количестве узлов. Нас не интересуют ни количество циклов, ни количество узлов в каждом цикле. Только общее количество узлов, задействованных в циклах данного графа.
UDP: Кстати, найдя кол-во узлов мы сможем ответить на общий вопрос о наличии цикла в графе. Иногда вопрос звучит именно так.
по-моему, топологическая сортировка подойдёт:
ОтветитьУдалить1. Помещаем все вершины в которых нет входящих дуг в очередь
2. Пока очередь не пуста:
- извлекаем вершину из очереди
- уменьшаем количество входящих дуг во всех вершинах смежных с данной. Те вершины, у которых количество входящих дуг стало равным 0 - помещаем в очередь.
3. Те вершины, у которых количество входящих дуг осталось не равным 0 - образуют циклы
Я вообще-то не специалист по графам, поэтому я не знаю, как правильно :)
ОтветитьУдалитьЯ решал эту задачу примерно так же. Только еще, имхо, нужно отбрасывать узлы, в которых нет исходящих дуг.
И очередь я не организовывал - просто циклично проходил по матрице, отбрасывал узлы с нулевыми столбцами/строками. Когда в матрице таких узлов больше нет - оставшиеся и есть наши искомые узлы. Хотя, кажется, смысл тот же.