VPF::[C/C++]Цикл что проходит через все вершины графа

sas8899

Дата 6.1.2008, 22:55 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Буду благодарен за любую помощь.

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

Это сообщение отредактировал(а) sas8899 - 6.1.2008, 22:57

Sartorius

Дата 6.1.2008, 23:38 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

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

Код


#include <stdio.h>
#include <assert.h>

const unsigned VERTEX_COUNT = 5;

unsigned char aGraph[VERTEX_COUNT][VERTEX_COUNT] = {
    //{0, 1, 0, 0, 0}, // тута ест повтор вершины
    //{0, 0, 1, 0, 0},
    //{1, 0, 0, 1, 0},
    //{0, 0, 0, 0, 4},
    //{0, 0, 1, 0, 0}

    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0}, // те же вершины но есть и цикл без повтора
    {1, 0, 0, 1, 0},
    {0, 0, 0, 0, 4},
    {1, 0, 1, 0, 0}
};

unsigned char aVertexVisited[VERTEX_COUNT] = {0};

bool isAllVertexVisited()
{
    for (int i = 0; i < VERTEX_COUNT; i++)
    {
        if (!aVertexVisited[i])
        {
            return (false);
        }
    }

    return (true);
}

bool isGlobalCycle(int vertex)
{
    assert(vertex < VERTEX_COUNT);

    if (vertex == 0 && isAllVertexVisited() )  // вернулись в начало - ура
    {
        return (true);
    }

    if (aVertexVisited[vertex])
    {
        return (false); // посетили уже второй раз
    }

    aVertexVisited[vertex] = 1; // зашли в вершину

    for (int i = 0; i < VERTEX_COUNT; i++)
    {
        if (aGraph[vertex][i])
        {
            if (isGlobalCycle(i))
            {
                return (true);
            }
        }
    }

    aVertexVisited[vertex] = 0; // возврат и продолжение поиска

    return (false);
}


void main()
{
    printf("%d", isGlobalCycle(0));
}

ЗЫ тип матрицы ты не указал, так что я на свое усмотрение использовал матрицу связности smile

ЗЗЫ эээ. че с часами на форуме? у мну сейчас 23 45 smile

Это сообщение отредактировал(а) Sartorius - 6.1.2008, 23:43

sas8899

Дата 7.1.2008, 18:20 (ссылка)

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

Загрузка ...

Новичок

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

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

Sartorius, спасибо большое, все работает smile

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