Проверка графа на связность

[Praud]

Помогите исправить алгоритм в коде, работает не так как надо.
Писал его сам вот по этому http://algolist.manual.ru/maths/graphs/linked.php
алгоритму.

  public void IsConnected()
        {
            int[] VertexState = new int[size];
            bool red = false;
            int k = 0;
            int finalCount = 0;

            for (int i = 0; i < size; i++)
                VertexState[i] = 1; // все черные

            VertexState[0] = 2; // красная

            do
            {
                red = true;


                for (int i = 0; i < size; i++)
                {
                    if (VertexState[i] == 2)
                    {
                        VertexState[i] = 3;
                        k = i;
                        break;
                    }
                }

                for (int i = 0; i < size; i++)
                {

                    if (graph[k][i] == 1 && VertexState[i] == 1)
                    {
                        VertexState[i] = 2;
                    }
                }

                for (int i = 0; i < size; i++)
                {
                    if (VertexState[i] == 2)
                        red = false;
                }

            } while (red == false);
            

            for (int i = 0; i < size; i++)
                if (VertexState[i] == 1)
                    finalCount++;
                  
                // Если finalCount = 0, то граф связный

      
        }

P.S - graph[i][j] - матрица смежности

[Poma][a]

работает не так как надо

Контрпример будет?

[Praud]

Будет. Допустим граф имеет 7 вершин, и graph[6][i] = 0, где i = 1...7

То есть вершина не имеет ребер. Собственно граф должен быть не связным, однако в программе finalCount выдает 0, что по алгоритму означает, что он является связным.

[Poma][a]

Не могли бы Вы дать полную матрицу смежности
А то есть подозрения на то, что граф Вы все-таки задаете неориентированный

[Praud]

0 1 1 0 1 0 0
0 0 0 1 0 1 1
1 0 0 0 1 1 0
0 1 0 0 0 1 1
1 0 1 0 0 0 0
0 1 0 0 0 0 1
0 0 0 0 0 0 0

Граф и так неориентированный вроде как

[Poma][a]

Ну дык все правильно. Вы можете из 2-ой, 4-ой, 6-ой добраться до 7-ой вершины

[Praud]

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

я просто уже самому себе не верю

[Poma][a]

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

Возьми свою матрицу и обнули i-ый столбец и i-ую строку. (Где i - произвольное число). Вот и получится у тебя две (как минимум) компоненты связности

[Praud]

Спасибо) вроде все работает и правильно показывает