В этом видео мы обсудим расстояние в графах. Давайте рассмотрим граф, и расстоянием между вершинами называется длина кратчайшего пути между этими вершинами. Мы можем зафиксировать вершину A, и тогда ее соседи будут на расстоянии один (это вершины B и C), а соседи этих соседей будут на расстоянии два (это только вершина D), ну и так далее, мы можем посмотреть на большие расстояния соседей, соседи соседей — это вершина на расстоянии три, в данном случае это вершина E. И дальше вершина F будет на расстоянии четыре. Хорошо. Где возникают расстояния? В соцсетях, например, расстояние — это длина минимальной цепочки знакомств между людьми. А в транспортных графах расстояния в принципе носят естественный смысл. И оказывается, что важно искать кратчайшие расстояния, а также важно искать близкие вершины. И то и то оказываются важными задачами, которые часто возникают. Хорошо, но как же вычислять расстояние от вершины до всех остальных в графе? Оказывается, что для этого очень удобен поиск в ширину. Мы начинаем с самой вершины, мы добавляем в наш список рассматриваемых вершин все вершины на расстоянии один, мы также перебираем все их и добавляем в наш список рассматриваемых вершин те, которые на расстоянии два. Перебираем их и добавляем те, которые на расстоянии три, ну и так далее. Вот, собственно, реализация. Что мы делаем? Мы начинаем с вершины v, фиксируем у нее расстояние ноль, а дальше мы создаем очередь. Очередь, в отличие от стеков, элемент, который первый попал в очередь, из нее первым же и уйдет. И пока у нас очередь не пуста, мы берем из нее элемент и перебираем всех его соседей, и если для них расстояние еще не посчитано, то мы вычисляем для них расстояние и добавляем их в очередь. Давайте посмотрим на примере: вот этот же код, и давайте разберем это на примере. Перебирать вершины будем, как обычно, в алфавитном порядке, и начинаем, таким образом, с вершины A. В принципе, мы запустим этот поиск для вершины A. Для нее расстояние ноль, и мы добавляем ее в очередь. Вершины, которые сейчас находятся в очереди, мы будем помечать темным цветом. И дальше мы запускаем цикл. Если очередь не пустая, а она не пустая, мы вытаскиваем из него элемент, это элемент A, и дальше мы перебираем соседей (давайте оранжевым цветом помечать ту вершину, которую мы в данный момент рассматриваем, вершину S). Мы перебираем ее соседей и добавляем их в очередь, и вычисляем для них расстояние. Первой будет вершина B, мы добавим ее в очередь, вычисляем расстояние, и второй будет вершина C. После этого рассмотрение вершины A закончилось, мы заканчиваем это делать и переходим к следующей вершине, мы должны взять следующую вершину из очереди — это вершина B, она попала в очередь раньше, чем C. Вершину A мы помечаем светлым цветом, это значит, что вершина уже разобрана, для нее расстояние уже вычислено, мы ее сейчас уже не рассматриваем, и она уже не в очереди. Хорошо, сейчас мы рассматриваем вершину B, мы перебираем ее соседей, и первый сосед — это C (но он уже рассмотрен, для него расстояние вычислено, поэтому для него мы ничего не делаем), а второй сосед — это E, и его мы еще не рассматривали. Мы вычисляем для нее расстояние, оно оказывается равно двум, и мы добавляем его в очередь. На этом рассмотрение B заканчивается, мы заканчиваем с B и переходим к следующему элементу в очереди — это C. Значит, для C у нас есть соседи, которые еще не рассмотрены, мы вычисляем для них расстояние, это расстояние будет три, и это сосед D. Добавляем D в очередь, и С, соответственно, с C заканчиваем рассмотрение. Берем следующий элемент из очереди, и следующим у нас в очередь попал элемент E, вот его мы и берем. Но, в принципе, все соседи E уже рассмотрены, поэтому мы тут же и заканчиваем рассмотрение E, и тут же и переходим к рассмотрению D, которое тут же заканчивается. Вот что будет, если мы запустим эту процедуру на этом графе. Хорошо. На самом деле, видно, что мы поддерживаем очередь в каждый момент из вершин, которые мы сейчас рассматриваем, давайте это тоже нарисуем, проговорим все это еще раз. Мы начали с вершины A, она попала в нашу очередь, и тут же мы ее оттуда вытащили и рассматриваем соседей, соседи ее попадают в эту очередь. После этого рассмотрение A заканчивается, мы переходим к следующему элементу в очереди — это B, и B вытаскиваем из очереди, мы теперь его рассматриваем, добавляем в очередь E. Дальше мы заканчиваем с B, и мы переходим к следующему элементу очереди — это C, из-за C у нас в очередь добавляется D. С C мы заканчиваем, и следующий элемент, который мы рассматриваем в очереди, это E, с ним все быстро заканчивается, и последний элемент в очереди D, с ним тоже все быстро заканчивается. Рассмотрение закончилось, поиск завершился. Отличие от поиска в глубину здесь, по существу, в том, что мы используем очередь вместо стека. В поиске в глубину мы использовали стек и в таком порядке перебирали вершины, а здесь мы используем очередь, это основное отличие. Итак, пути играют важную роль при изучении графов, и связность оказывается важным свойством графа. Поиск в глубину и поиск в ширину можно использовать для обхода графов, но какой именно из них лучше использовать, зависит от задачи. Для поиска в ширину, например, поиск в ширину удобен для задачи подсчета расстояний, а для поиска в глубину мы увидим еще примеры, когда он оказывается удобным.
