Найти цикл в ориентированном графе

20.03.2011, 16:27. Показов 3913. Ответов 0

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

Добрый день! У меня такая трабла. Дан ориентированный граф, заданный весовой матрицей. Найти цикл в этом графе.

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

C#
1
2
3
4
5
6
7
8
9
10
11
public void Search(int v, int [,] w)
      {
          Color[v] = 1;//раскрашиваем входную вершину в серый цвет
          for (int i = 0; i < Size; i++)
          {
              if ((w[v, i] != 100) && (w[v, i] != 0) && (Color[i] == 0)) Search(i, W);//проходимся по всем белым вершинам
              if (Color[i] == 1) Console.WriteLine("Цикл есть");
              else Console.WriteLine("Цикла нет");
          }
          Color[v] = 2;
      }

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

20.03.2011, 16:27

Ответы с готовыми решениями:

Поиск в ширину с помощью списка инцидентности в ориентированном графе
Здравствуйте, коллеги! Помогите пожалуйста с реализацией поиска в ширину с помощью списка инцидентности для случая когда граф...

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

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами
Ребята день добрый. Задание у меня вот такое: Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

20.03.2011, 16:27

Помогаю со студенческими работами здесь

Удаление цикла в ориентированном графе
Помогите реализовать такой вот алгоритм: Задан ориентированный граф. Необходимо найти и удалить из него все циклы. Пример графа: 1 2 ...

Смежные вершины в ориентированном графе
Какие вершины называются смежными в ориентированном графе?

Поиск пути в ориентированном графе
Вот как звучит сама задача. Дан список пар городов, между которыми есть авиарейсы. Найти два города, между которыми есть по крайней мере ...

Поиск циклов в ориентированном графе
Доброго времени суток. Может кому-нибудь из вас не составит особого труда, или возможно кто-то писал похожую программу. В общем, я написал...

Поиск в ориентированном графе на Visual Prolog 7.5
Задать ориентированный граф и определить: - все узлы, доступные с заданного за один шаг; - то же за 2 шага; - все узлы, из которых...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

Наверх