algorithm
Поиск по ширине
Поиск…
Поиск кратчайшего пути от источника к другим узлам
Breadth-first-search (BFS) - это алгоритм для перемещения или поиска структур данных дерева или графика. Он начинается с корня дерева (или какого-либо произвольного узла графа, иногда называемого «ключом поиска») и сначала исследует соседние узлы, а затем переходит к соседним соседним уровням. BFS был изобретен в конце 1950-х годов Эдвардом Форрестом Муром , который использовал его для поиска кратчайшего пути из лабиринта и независимо открыл CY Lee как алгоритм маршрутизации проводов в 1961 году.
Процессы алгоритма BFS работают в этих предположениях:
- Мы не будем проходить ни одного узла более одного раза.
- Исходный узел или узел, с которого мы начинаем, находится на уровне 0.
- Узлами, которые мы можем напрямую достичь от исходного узла, являются узлы уровня 1, узлы, с которыми мы можем напрямую связаться с узлами уровня 1, являются узлами уровня 2 и т. Д.
- Уровень означает расстояние от кратчайшего пути от источника.
Давайте посмотрим пример: 
Предположим, что этот график представляет собой соединение между несколькими городами, где каждый узел обозначает город, а край между двумя узлами означает, что существует дорога, соединяющая их. Мы хотим перейти от узла 1 к узлу 10 . Итак, узел 1 является нашим источником , который является уровнем 0 . Мы отмечаем узел 1 как посещенный. Мы можем перейти к узлу 2 , узлу 3 и узлу 4 отсюда. Таким образом, они будут уровнями (0 + 1) = уровня 1 . Теперь мы помечаем их как посетили и работаем с ними.
Посещаются цветные узлы. Узлы, с которыми мы сейчас работаем, будут отмечены розовым. Мы не будем посещать один и тот же узел дважды. Из узла 2 , узла 3 и узла 4 мы можем перейти к узлу 6, узлу 7 и узлу 8 . Отметьте их как посетили. Уровень этих узлов будет уровнем (1 + 1) = уровень 2 . 
Если вы не заметили, уровень узлов просто обозначает кратчайшее расстояние пути от источника . Например: мы нашли узел 8 на уровне 2 . Таким образом, расстояние от источника до узла 8 равно 2 .
Мы еще не достигли нашего целевого узла, то есть узла 10 . Итак, давайте посмотрим на следующие узлы. мы можем напрямую перейти от узла 6 , узла 7 и узла 8 . 
Мы видим, что мы нашли узел 10 на уровне 3 . Таким образом, кратчайший путь от источника к узлу 10 равен 3. Мы искали уровень графа по уровню и находили кратчайший путь. Теперь давайте удалим те грани, которые мы не использовали: 
После удаления краев, которые мы не использовали, мы получаем дерево, называемое деревом BFS. Это дерево показывает кратчайший путь от источника ко всем другим узлам.
Поэтому наша задача будет состоять в том, чтобы перейти от источника к узлам уровня 1 . Затем от узлов уровня 1 до уровня 2 и так далее, пока мы не достигнем нашего пункта назначения. Мы можем использовать очередь для хранения узлов, которые мы будем обрабатывать. То есть для каждого узла, с которым мы собираемся работать, мы будем выталкивать все остальные узлы, которые могут быть напрямую перемещены и еще не пройдены в очереди.
Моделирование нашего примера:
Сначала мы подталкиваем источник в очередь. Наша очередь будет выглядеть так:
front
+-----+
| 1 |
+-----+
Уровень узла 1 будет равен 0. level [1] = 0 . Теперь мы начинаем нашу BFS. Сначала мы выставляем узел из нашей очереди. Мы получаем узел 1 . Мы можем перейти к узлу 4 , узлу 3 и узлу 2 из этого. Мы достигли этих узлов из узла 1 . Таким образом, уровень [4] = уровень [3] = уровень [2] = уровень [1] + 1 = 1 . Теперь мы отмечаем их как посещаемые и помещаем их в очередь.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Теперь мы поп- узел 4 и работаем с ним. Мы можем перейти к узлу 7 из узла 4 . уровень [7] = уровень [4] + 1 = 2 . Мы отмечаем узел 7 как посещенный и нажимаем его в очереди.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Из узла 3 мы можем перейти к узлу 7 и узлу 8 . Поскольку мы уже пометили узел 7 как посещенный, мы помечаем узел 8 как посещенный, мы меняем уровень [8] = уровень [3] + 1 = 2 . Мы вставляем узел 8 в очередь.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Этот процесс будет продолжаться до тех пор, пока мы не достигнем места назначения, или очередь не станет пустой. Массив уровня предоставит нам расстояние от кратчайшего пути от источника . Мы можем инициализировать массив уровней с бесконечным значением, что будет означать, что узлы еще не посещены. Наш псевдокод будет:
Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
u -> Q.pop()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
Q.push(v)
end if
end for
end while
Return level
Итерируя через массив уровней , мы можем узнать расстояние каждого узла от источника. Например: расстояние узла 10 от источника будет сохранено на уровне [10] .
Иногда нам может потребоваться напечатать не только кратчайшее расстояние, но и путь, по которому мы можем перейти к нашему узлу, который находится у вас из источника . Для этого нам нужно сохранить родительский массив. parent [source] будет NULL. Для каждого обновления в массиве уровней мы просто добавим parent[v] := u в наш псевдокод внутри цикла for. По завершении BFS, чтобы найти путь, мы перейдем назад к родительскому массиву, пока не достигнем источника, который будет обозначен значением NULL. Псевдокод будет:
Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative
if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | S.push(u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> S.pop
| end while
Сложность:
Мы посетили каждый узел один раз и каждый ребро один раз. Таким образом, сложность будет O (V + E), где V - количество узлов, а E - количество ребер.
Поиск кратчайшего пути из источника в двумерном графике
В большинстве случаев нам нужно будет найти кратчайший путь от одного источника ко всем другим узлам или конкретному узлу в двумерном графике. Скажем, например: мы хотим узнать, сколько ходов требуется для того, чтобы рыцарь достиг определенного квадрата в шахматной доске, или у нас есть массив, в котором некоторые ячейки заблокированы, нам нужно выяснить кратчайший путь из одной ячейки в другую , Мы можем перемещаться только по горизонтали и по вертикали. Также возможны диагональные движения. Для этих случаев мы можем преобразовать квадраты или ячейки в узлы и легко решить эти проблемы с помощью BFS. Теперь нашими посетителями , родителями и уровнями будут 2D массивы. Для каждого узла мы рассмотрим все возможные шаги. Чтобы найти расстояние до определенного узла, мы также проверим, дошли ли мы до пункта назначения.
Будет еще одна вещь, называемая массивом направлений. Это просто сохранит все возможные комбинации направлений, на которые мы можем пойти. Скажем, для горизонтальных и вертикальных движений наши массивы направлений будут:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Здесь dx представляет перемещение по оси x, а dy представляет перемещение по оси y. Опять же эта часть является необязательной. Вы также можете написать все возможные комбинации отдельно. Но с ним проще справиться с использованием массива направлений. Могут быть больше и даже разные комбинации для диагональных движений или движения рыцарей.
Дополнительную часть, о которой мы должны помнить, это:
- Если какая-либо ячейка заблокирована, для всех возможных ходов мы проверим, заблокирована ли ячейка или нет.
- Мы также проверим, не вышли ли мы за границы, то есть пересекли границы массива.
- Будет указано количество строк и столбцов.
Наш псевдокод будет:
Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
for j from 1 to column
visited[i][j] := false
end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
top := Q.pop
for i from 1 to m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i]
if temp is inside the row and column and top doesn't equal to blocksign
visited[temp.x][temp.y] := true
level[temp.x][temp.y] := level[top.x][top.y] + 1
Q.push(temp)
end if
end for
end while
Return level
Как мы уже говорили ранее, BFS работает только для невзвешенных графиков. Для взвешенных графов нам понадобится алгоритм Дейкстры . Для отрицательных краевых циклов нам нужен алгоритм Беллмана-Форда . Снова этот алгоритм является алгоритмом кратчайшего пути с одним источником. Если нам нужно выяснить расстояние от каждого узла до всех других узлов, нам понадобится алгоритм Флойда-Варшалла .
Связанные компоненты ненаправленного графика с использованием BFS.
BFS можно использовать для поиска связанных компонентов неориентированного графа . Мы также можем найти, связан ли данный граф или нет. Наше последующее обсуждение предполагает, что мы имеем дело с неориентированными графами. Определение связного графа:
График связан, если есть путь между каждой парой вершин.
Ниже приводится связанный граф .
Следующий график не подключен и имеет 2 подключенных компонента:
- Подключенный компонент 1: {a, b, c, d, e}
- Подключенный компонент 2: {f}
BFS - алгоритм обхода графика. Итак, начиная с случайного узла источника, если по окончании алгоритма все узлы посещаются, то граф подключен, иначе он не подключен.
PseudoCode для алгоритма.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
C для определения того, подключен ли неориентированный граф или нет:
#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100
void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
int v;
struct node *next;
};
typedef struct node Node;
typedef struct node *Nodeptr;
Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.
int main()
{
int n,e;//n is number of vertices, e is number of edges.
int i,j;
char **graph;//adjacency matrix
printf("Enter number of vertices:");
scanf("%d",&n);
if(n < 0 || n > MAXVERTICES)
{
fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
return -1;
}
graph = malloc(n * sizeof(char *));
visited = malloc(n*sizeof(char));
for(i = 0;i < n;++i)
{
graph[i] = malloc(n*sizeof(int));
visited[i] = 'N';//initially all vertices are not visited.
for(j = 0;j < n;++j)
graph[i][j] = 0;
}
printf("enter number of edges and then enter them in pairs:");
scanf("%d",&e);
for(i = 0;i < e;++i)
{
int u,v;
scanf("%d%d",&u,&v);
graph[u-1][v-1] = 1;
graph[v-1][u-1] = 1;
}
if(isConnected(graph,n))
printf("The graph is connected");
else printf("The graph is NOT connected\n");
}
void enqueue(int vertex)
{
if(Qfront == NULL)
{
Qfront = malloc(sizeof(Node));
Qfront->v = vertex;
Qfront->next = NULL;
Qrear = Qfront;
}
else
{
Nodeptr newNode = malloc(sizeof(Node));
newNode->v = vertex;
newNode->next = NULL;
Qrear->next = newNode;
Qrear = newNode;
}
}
int deque()
{
if(Qfront == NULL)
{
printf("Q is empty , returning -1\n");
return -1;
}
else
{
int v = Qfront->v;
Nodeptr temp= Qfront;
if(Qfront == Qrear)
{
Qfront = Qfront->next;
Qrear = NULL;
}
else
Qfront = Qfront->next;
free(temp);
return v;
}
}
int isConnected(char **graph,int noOfVertices)
{
int i;
//let random source vertex be vertex 0;
BFS(graph,0,noOfVertices);
for(i = 0;i < noOfVertices;++i)
if(visited[i] == 'N')
return 0;//0 implies false;
return 1;//1 implies true;
}
void BFS(char **graph,int v,int noOfVertices)
{
int i,vertex;
visited[v] = 'Y';
enqueue(v);
while((vertex = deque()) != -1)
{
for(i = 0;i < noOfVertices;++i)
if(graph[vertex][i] == 1 && visited[i] == 'N')
{
enqueue(i);
visited[i] = 'Y';
}
}
}
Для поиска всех подключенных компонентов неориентированного графа нам нужно только добавить 2 строки кода в функцию BFS. Идея состоит в том, чтобы вызвать функцию BFS до тех пор, пока не будут посещены все вершины.
Строки, которые необходимо добавить:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
А ТАКЖЕ
printf("%d ",vertex+1);
add this as first line of while loop in BFS
и мы определяем следующую функцию:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}