Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > .NET для новичков > Проверка ориентированного графа на наличие циклов.

Автор: Kostja 22.3.2011, 21:24

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

Код


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