Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646695 Wed, 13 Jan 2016 09:38:10 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646695 Хотя, если уж по уму, ... тогда вообще нету смысла этот параметр использовать в функции, а просто сделать глобальную переменную (константу).]]> JoeUser C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646694 Wed, 13 Jan 2016 09:30:53 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646694 Цитата JoeUser @
Попробуй свой совет осуществить и увидишь неработающий вариант. :lol: Учитель блин. :lol:

Твой вариант: http://ideone.com/mYQlxh
Твой измененый вариант: http://ideone.com/nGAher
ЗЫЖ
Цитата
Учитель блин. :lol:
]]> KILLER C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646691 Wed, 13 Jan 2016 08:53:33 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646691 Цитата KILLER @
Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю.


Именно так и надо! Мне там нужны локальные копии! Попробуй свой совет осуществить и увидишь неработающий вариант. :lol: Учитель блин. :lol:]]> JoeUser C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646686 Wed, 13 Jan 2016 08:43:24 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646686 Цитата JoeUser @
Экономим на вызовах :)

Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю.]]> KILLER C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646655 Wed, 13 Jan 2016 01:31:35 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646655 Цитата Black*Eternal @
По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна?

Проверку очередной вершины нужно делать не в теле функции, а до входа в нее. Экономим на вызовах :)]]> JoeUser C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646593 Tue, 12 Jan 2016 16:01:46 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646593 Цитата JoeUser @
Фиксю

Блин, ничего себе. Вот это решение... Удивило, что оно настолько короткое. Сейчас буду разбираться, спасибо!

По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна? :)]]> Black*Eternal C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646509 Mon, 11 Jan 2016 19:22:06 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646509 Цитата Black*Eternal @
Может кто поможет пофиксить?

Фиксю :lol: Онлайн-тест тут.

    #include <iostream>
    #include <vector>
    #include <map>
     
    typedef std::vector<uint> PathType;
    typedef std::map<uint,bool> VisType;
    typedef std::map<uint,std::vector<uint>> RelType;
     
    void PrintPath(uint I, PathType P, VisType V, RelType R) {
      if (V.find(I) != V.end()) return;
      P.push_back(I); V[I]=true;
      for(const auto& x: P) std::cout << ":" << x; std::cout << std::endl;
      for(const auto& i: R[I]) PrintPath(i,P,V,R);
    }
     
    int main() {
      VisType Vis;
      PathType Path;
      RelType Rel = {
        {0,{1,5,6}},
        {1,{0,2,6}},
        {2,{1,3,6}},
        {3,{2,4,6}},
        {4,{3,5,6}},
        {5,{0,4,6}},
        {6,{0,1,2,3,4,5}}
      };
      for(auto const& i:Rel) PrintPath(i.first,Path,Vis,Rel);
    }


Добавлено
Add: Программулина, вроде правильная, но не оптимальная. Вопрос ТС - а в чем "неоптимальность"? ;)]]> JoeUser C/C++: Прочее https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646496 Mon, 11 Jan 2016 16:45:37 +0000 Перебор всех значений связанного графа. Помогите разобраться в чём проблема... https://forum.sources.ru/index.php?showtopic=407625&view=findpost&p=3646496 user posted image

Элементы - простые индексы от 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 );
     
    }
]]> Black*Eternal C/C++: Прочее