Алгоритм поиска в ширину на графе
Речь пойдет, как вы уже наверное догадались, о графах, а именно о алгоритме обхода графа в ширину.
Чтобы проникнуться в суть графов, попробуйте решить следующую, довольно известную задачу:
Река, огибающая остров, делится на два рукава, через которые переброшены 7 мостов (см. рисунок ниже). Спрашивается, можно ли совершить такую прогулку, чтобы за один раз перейти все эти мосты, не переходя ни через один мост два или более раз?
Суть алгоритма поиска в ширину в том, что мы обходим связный граф таким образом, что сначала мы рассматриваем родителя, потом по очереди рассматриваем его предков, потом рассматриваем предков его предков и т.д.(см. рисунок ниже)
Порядок обхода вершин графа.
Можно объяснить алгоритм двумя способами:
1.Первой вершине (родителю всех остальных вершин) приписываем метку 1. Рассматриваем все смежные с ней вершины и приписываем им метку 2. Дальше рассматриваем окружение вершин с меткой 2 и присваиваем метку 3 всем вершинам, кроме самой главной (родителя всех вершин).
2. Второй способ объяснения (по моему более понятнее, ну по крайней мере писать его легче) подразумевает под собой имитирование «горения» графа. Т.е. мы поджигаем самую первую вершину, дальше огонь перекидывается на смежные с ней вершины, с них на смежные с ними и т.д. Со смыслом я думаю мы разобрались, однако для меня основной проблемой стала реализация алгоритма. (Программист я не очень то начитанный, поэтому не вините меня).
Ну напишу я пока что примерную реализацию на С++:
queue <int> turn;//Это наша очередь, хранящая номера вершин
int used[1000];//массив, хранящий состояние вершины("сгорела","не сгорела")
int matrix[1000][1000];//матрица, хранящая информацию о смежности вершин
void bfs ( ) //собственно сама функция
{
while ( !turn.empty() ) //проверяем, пуста ли очередь
{
int ind=turn.front();//берем из очереди крайний элемент
turn.pop();//удаляем его
for ( int i=0; i<1000; i++ )//смотрим, с какими вершинами смежна вершина ind
{
if ( matrix[ind][i]==1 )
{
turn.push(i);//добавляем в очередь вершину i
}
}
}
}
Поясню немного.
Данный код совершает обход по связному графу в ширину. Предполагается, что нам известны данные о смежности вершин ( которые хранятся в матрице смежности matrix[] ) Если вершины i и j смежные, то matrix[i][j]=1 Ну вроде бы все. Профессиональные кодеры, пожалуйста, не ругайтесь за такое кривое объяснение и ещё более кривой код (но я частенько нуждаюсь в кривых, но довольно простых кодах).