Page 151 - Bkhargava_-_Grokaem_algoritmy
P. 151
150 Глава 6. Поиск в ширину
6.5 Какие из следующих графов также являются деревьями?
Л. Ь. С.
Шпаргалка
о Поиск в ширину позволяет определить, существует ли путь из А в В.
о Если путь существует, то поиск в ширину находит кратчайший путь.
о Если в вашей задаче требуется найти «кратчайшее Х», попробуйте смо
делировать свою задачу графом и воспользуйтесь поиском в ширину
для ее решения.
о В направленном графе есть стрелки, а отношения действуют в направле
нии стрелки (Рама-+ Адит означает «Рама должен Адиту» ).
о В ненаправленных графах стрелок нет, а отношение идет в обе сторон·ы
(Росс - Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встреча
ется с Россом».)
о Очереди относятся к категории FIFO («первым вошел, первым вышел»).
о Стек относится к категории LIFO («последним пришел, первым вышел»).
о Людей следует проверять в порядке их
добавления в список поиска, поэтому
список поиска должен быть оформлен
в виде очереди, иначе найденный путь
не будет кратчайшим.
о Позаботьтесь о том, чтобы уже прове
ренный человек не проверялся заново,
иначе может возникнуть бесконечный
цикл .
www.trk.kg