Page 151 - Bkhargava_-_Grokaem_algoritmy
P. 151

150    Глава 6.  Поиск в ширину


       6.5   Какие из следующих графов также являются деревьями?


                       Л.               Ь.            С.












       Шпаргалка


       о Поиск в ширину позволяет определить, существует ли путь из А в В.
       о Если путь существует, то поиск в ширину находит кратчайший путь.

       о Если в вашей задаче требуется найти «кратчайшее Х», попробуйте смо­
          делировать свою задачу графом и воспользуйтесь поиском в ширину
          для ее решения.
       о В направленном графе есть стрелки, а отношения действуют в направле­
          нии стрелки (Рама-+ Адит означает «Рама должен Адиту» ).

       о В ненаправленных графах стрелок нет, а отношение идет в обе сторон·ы
          (Росс - Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встреча­
          ется с Россом».)

       о Очереди относятся к категории FIFO («первым вошел, первым вышел»).
       о Стек относится к категории LIFO («последним пришел, первым вышел»).

       о Людей следует проверять в порядке их
          добавления в список поиска, поэтому
          список поиска должен быть оформлен
          в виде очереди, иначе найденный путь
          не будет кратчайшим.

       о Позаботьтесь о том, чтобы уже прове­
          ренный человек не проверялся заново,
          иначе может возникнуть бесконечный
          цикл .

                                                         www.trk.kg
   146   147   148   149   150   151   152   153   154   155   156