VPF::Проверка ориентированного графа на наличие циклов.

Kostja

Дата 22.3.2011, 21:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 22.3.2011

Репутация: нет
Всего: нет

Доброго времени суток! Такая проблема. Необходимо проверить ориентированный граф на наличие циклов. Граф задан весовой матрицей.
Мой код:

Код


public void SCycle(int v,int[,] W)
        {
            Color[v] = 1;//красим, выбранную в качестве начальной, вершину в серый цвет (изначально все вершины белые)
            for (int i = 0; i < Size; i++)
            {
                if ((W[v, i] != 99) && (W[v, i] != 0) && (Color[i] == 0)) SCycle(i, W);//99 - нет прямого пути, 0 - нет ребра из вершины в саму себя 
                else if (Color[i] == 1) Console.WriteLine("цикл есть");//если пришли в серую вершину, то цикл есть
                else Console.WriteLine("Цикла нет");//иначе цикла нет
            }
            Color[v] = 2;//завершая обработку вершины красим её в черный
        }

При запуске программы из вершины "0" над матрицей:    0   99   1
                                                                                              2    0    4
                                                                                             99   3    0
Выдаёт:         цикл    есть
                      цикла   нет
                      цикл    есть
                      цикл    есть
                      цикл    есть
                      цикл    есть
                      цикл    есть

Не понятно почему так. Такое ощущение, что алгоритм работает не правильно. Где в нем ошибка? Или он работает правильно, просто я не понимаю как. Спасибо. smile

Это сообщение отредактировал(а) Kostja - 23.3.2011, 16:15

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| .NET для новичков \| Следующая тема »