Алгоритм поиска в ширину
ОПТИМИЗАЦИОННЫЕ АЛГОРИТМЫ НА ГРАФАХ
Лекция 10
(BFS, breadth-first search )
BFS(G, s)
Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины a. Иначе говоря, сначала посещается сама вершина a, затем все вершины, смежные с a, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от на расстоянии 2, и т.д.
Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной a. Вначале все вершины помечаются как новые. Первой посещается вершина a, она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины x. Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину x с новой вершиной y, то вершина y посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.
Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале.
BFS(G, s)
(DFS, depth-first search)
Поиск в глубину - вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, "бэктрекинг", "поиск с возвращением".
Понятия новой, открытой, закрытой и активной вершин для поиска в глубину имеют такой же смысл, как и для поиска в ширину. Отметим, что всегда имеется не более чем одна активная вершина.
Обход начинается с посещения заданной стартовой вершины a, которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине a ребро (a,y) и посещается вершина y. Она становится открытой и активной. Заметим, что при поиске в ширину вершина a оставалась активной до тех пор, пока не были исследованы все инцидентные ей ребра. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине x, уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер (x,y), это ребро исследуется. Если вершина y новая, то она посещается и превращается в открытую.
Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина.
u KUtKOC6YJlmAwV9VPKa1iEOHlNrIXJnfSNPN92MSdXuCyWsza+8lhQN7gT4kqLtXn2hUxxC793Dd PXd59i8AAAD//wMAUEsDBBQABgAIAAAAIQCRpOX03QAAAAUBAAAPAAAAZHJzL2Rvd25yZXYueG1s TI/NTsMwEITvSLyDtUjcqNOkjSDEqRCICz2lRW2Pbrz5Ue11FLtpeHsMl/ay0mhGM9/mq8loNuLg OksC5rMIGFJlVUeNgO/t59MzMOclKaktoYAfdLAq7u9ymSl7oRLHjW9YKCGXSQGt933GuataNNLN bI8UvNoORvogh4arQV5CudE8jqKUG9lRWGhlj+8tVqfN2QhQpR7d/quux3WcrMuP5WGX7BZCPD5M b6/APE7+GoY//IAORWA62jMpx7SA8Ij/v8FL05cY2FFAki6WwIuc39IXvwAAAP//AwBQSwECLQAU AAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnht bFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVs c1BLAQItABQABgAIAAAAIQDv7T+eKAYAAL8pAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9j LnhtbFBLAQItABQABgAIAAAAIQCRpOX03QAAAAUBAAAPAAAAAAAAAAAAAAAAAIIIAABkcnMvZG93 bnJldi54bWxQSwUGAAAAAAQABADzAAAAjAkAAAAA ">
m S5dOlyhp/luJ3zLT7ecxhnpfv6TzakMCp5vA8XX+saOTeq3g0HtQdXQX0cluNvKAkxr08ViR6cfR xyvSR50oHPSxp486odrRR71WF9VHJwgsp0nH7jOuezJhUMqvTil1GvW1KCUETFhHjz5AU/SvKvW7 93Dd/deE678AAAD//wMAUEsDBBQABgAIAAAAIQCBKPkG3QAAAAUBAAAPAAAAZHJzL2Rvd25yZXYu eG1sTI/BTsMwEETvSPyDtUjcqENDCwpxKoQE4hIEpSoc3XgbR43XIXZb8/csXOCy0mhGM2/LRXK9 OOAYOk8KLicZCKTGm45aBau3h4sbECFqMrr3hAq+MMCiOj0pdWH8kV7xsIyt4BIKhVZgYxwKKUNj 0ekw8QMSe1s/Oh1Zjq00oz5yuevlNMvm0umOeMHqAe8tNrvl3inY5fk6fTy+2+7leVvX8dPgU6qV Oj9Ld7cgIqb4F4YffEaHipk2fk8miF4BPxJ/L3vX+fwKxEZBPpvOQFal/E9ffQMAAP//AwBQSwEC LQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNd LnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8u cmVsc1BLAQItABQABgAIAAAAIQAy5FhDZAYAAOIwAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJv RG9jLnhtbFBLAQItABQABgAIAAAAIQCBKPkG3QAAAAUBAAAPAAAAAAAAAAAAAAAAAL4IAABkcnMv ZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAyAkAAAAA ">
2014-02-02
932
