Есть граф, элементы которого связаны по схеме:
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 );
}
|
|