VPF::Перебор всех путей цикличного графа (С++)

Proger10

Дата 11.1.2016, 19:26 (ссылка)

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

Загрузка ...

Опытный

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

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

Есть граф, элементы которого связаны по схеме:
http://s013.radikal.ru/i322/1601/ba/7ee5be3d71d0.png

Элементы - простые индексы от 0 до 6 включительно.
Хочу перечислить всевозможные пути, например:
0, 1
0, 1, 2, 6, 5
0, 1, 2, 6, 5, 4
0, 5, 6, 4
....

У меня правильно перебирает только первый путь, но дальше выводятся пути из несвязанных элементов. Почему это происходит? Может кто поможет пофиксить? Уже пару дней бьюсь, не могу понять в чём причина такого поведения.

Код



void goElement( std::vector< std::vector< unsigned short > > &relationsArr, unsigned short goElementId, std::vector< unsigned short > visitedIndexesPathArr ) {

    printf( "\nВход в элемент: %i\n", goElementId );

    // Проверяем пути для посещения - если имеются для текущего элемента:
    for ( unsigned short i = 0; i < relationsArr[ goElementId ].size(); i++ ) {
    
        printf( "\t> Возможный путь: %i для %i элемента", relationsArr[ goElementId ][ i ], goElementId );
        
        bool notVisited = true; // Проверяем - не посещали ли мы relationsArr[ goElementId ][ i ] (возможный путь для посещения) уже в нашем пути
        for ( unsigned short i1 = 0; notVisited && ( i1 < visitedIndexesPathArr.size() ); i1++ )
            if ( relationsArr[ goElementId ][ i ] == visitedIndexesPathArr[ i1 ] )
                notVisited = false;
        
        if ( notVisited ) {
        
            printf( " - не посещён! Посещаем...\n" );
            
            visitedIndexesPathArr.push_back( relationsArr[ goElementId ][ i ] ); // запоминаем его как посещённый
            goElement( relationsArr, relationsArr[ goElementId ][ i ], visitedIndexesPathArr ); // Посещаем следующий
            
        } else {
        
            printf( " - посещён\n" );
        
        }
        
    }
    
    printf( "\t\tВсе посещены, финальный путь: " );
    for ( unsigned short i2 = 0; i2 < visitedIndexesPathArr.size(); i2++ )
        printf( "%i, ", visitedIndexesPathArr[ i2 ] );
    printf( "\n" );

}

int main() {
    
    std::vector< std::vector< unsigned short > > relationsArr { 
        {1,5,6},
        {0,2,6},
        {1,3,6},
        {2,4,6},
        {3,5,6},
        {0,4,6},
        {0,1,2,3,4,5}
    };
    
    std::vector< unsigned short > visitedIndexesPathArr;
    visitedIndexesPathArr.push_back( 0 );
    goElement( relationsArr, 0, visitedIndexesPathArr );

}

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