На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: JoeUser, Qraizer
  
> Перебор всех значений связанного графа. Помогите разобраться в чём проблема..., Код, почти работающей, "попытки" - прилагается
    Есть граф, элементы которого связаны по схеме:
    user posted image

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


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

    ExpandedWrap disabled
      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 @
      Может кто поможет пофиксить?

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

      ExpandedWrap disabled
        #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: Программулина, вроде правильная, но не оптимальная. Вопрос ТС - а в чем "неоптимальность"? ;)
      Мои программные ништякиhttp://majestio.info
        Цитата JoeUser @
        Фиксю

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

        По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна? :)
          Цитата Black*Eternal @
          По неоптимальности - очень интересный вопрос. Честно говоря, даже не представляю, в чём она не оптимальна?

          Проверку очередной вершины нужно делать не в теле функции, а до входа в нее. Экономим на вызовах :)
          Мои программные ништякиhttp://majestio.info
            Цитата JoeUser @
            Экономим на вызовах :)

            Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю.
            Сообщение отредактировано: KILLER -
              Цитата KILLER @
              Лучше бы ты сэкономил на передаче параметров в функцию. Сейчас ты вектора и мапы передаешь туда по значению, что приводит к копированию содержимого контейнеров во внутренюю переменную при каждом вызове функции и передаче туда контейнеров - это крайне неэффективно, надо по ссылке или хотя бы по указателю.


              Именно так и надо! Мне там нужны локальные копии! Попробуй свой совет осуществить и увидишь неработающий вариант. :lol: Учитель блин. :lol:
              Мои программные ништякиhttp://majestio.info
                Цитата JoeUser @
                Попробуй свой совет осуществить и увидишь неработающий вариант. :lol: Учитель блин. :lol:

                Твой вариант: http://ideone.com/mYQlxh
                Твой измененый вариант: http://ideone.com/nGAher
                ЗЫЖ
                Цитата
                Учитель блин. :lol:
                  На счет одного значения - согласен, но если все передавать по указателю или ссылке - будет не то.
                  Хотя, если уж по уму, ... тогда вообще нету смысла этот параметр использовать в функции, а просто сделать глобальную переменную (константу).
                  Мои программные ништякиhttp://majestio.info
                  1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script Execution time: 0,1034 ]   [ 15 queries used ]   [ Generated: 21.07.19, 06:42 GMT ]