algorithm
Szerokie wyszukiwanie
Szukaj…
Znalezienie najkrótszej ścieżki od źródła do innych węzłów
Szerokość-pierwsze wyszukiwanie (BFS) to algorytm do przechodzenia lub wyszukiwania struktur danych drzewa lub wykresu. Zaczyna się od katalogu głównego drzewa (lub dowolnego dowolnego węzła wykresu, czasami nazywanego „kluczem wyszukiwania”) i najpierw eksploruje sąsiednie węzły, a następnie przechodzi do sąsiadów następnego poziomu. BFS został wynaleziony pod koniec lat 50. ubiegłego wieku przez Edwarda Forresta Moore'a , który wykorzystał go do znalezienia najkrótszej ścieżki z labiryntu i odkrył niezależnie przez CY Lee jako algorytm routingu drutu w 1961 r.
Procesy algorytmu BFS działają przy następujących założeniach:
- Nie przejdziemy żadnego węzła więcej niż raz.
- Węzeł źródłowy lub węzeł, z którego zaczynamy, znajduje się na poziomie 0.
- Węzły, do których możemy bezpośrednio dotrzeć z węzła źródłowego, są węzłami poziomu 1, węzły, do których możemy dotrzeć bezpośrednio z węzłów poziomu 1, są węzłami poziomu 2 i tak dalej.
- Poziom oznacza odległość najkrótszej ścieżki od źródła.
Zobaczmy przykład: 
Załóżmy, że ten wykres przedstawia połączenie między wieloma miastami, gdzie każdy węzeł oznacza miasto, a krawędź między dwoma węzłami oznacza, że istnieje droga łącząca je. Chcemy przejść od węzła 1 do węzła 10 . Zatem węzeł 1 jest naszym źródłem , którym jest poziom 0 . Oznaczamy węzeł 1 jako odwiedzony. Możemy przejść do węzła 2 , węzła 3 i węzła 4 stąd. Będą więc na poziomie (0 + 1) = węzły poziomu 1 . Teraz oznaczymy je jako odwiedzone i będziemy z nimi pracować.
Kolorowe węzły są odwiedzane. Węzły, z którymi obecnie pracujemy, zostaną oznaczone na różowo. Nie odwiedzimy dwa razy tego samego węzła. Z węzła 2 , węzła 3 i węzła 4 możemy przejść do węzła 6, węzła 7 i węzła 8 . Oznaczmy je jako odwiedzone. Poziom tych węzłów będzie wynosił poziom (1 + 1) = poziom 2 . 
Jeśli nie zauważyłeś, poziom węzłów oznacza po prostu najkrótszą odległość ścieżki od źródła . Na przykład: znaleźliśmy węzeł 8 na poziomie 2 . Zatem odległość od źródła do węzła 8 wynosi 2 .
Nie dotarliśmy jeszcze do naszego węzła docelowego, czyli węzła 10 . Odwiedźmy kolejne węzły. możemy bezpośrednio przejść do węzła 6 , węzła 7 i węzła 8 . 
Widzimy to, znaleźliśmy węzeł 10 na poziomie 3 . Zatem najkrótsza ścieżka od źródła do węzła 10 to 3. Przeszukaliśmy wykres poziom po poziomie i znaleźliśmy najkrótszą ścieżkę. Teraz usuńmy krawędzie, których nie używaliśmy: 
Po usunięciu krawędzi, których nie użyliśmy, otrzymujemy drzewo o nazwie drzewo BFS. To drzewo pokazuje najkrótszą ścieżkę od źródła do wszystkich innych węzłów.
Naszym zadaniem będzie przejście od węzła źródłowego do poziomu 1 . Następnie od poziomu 1 do węzłów poziomu 2 i tak dalej, aż dotrzemy do celu. Możemy użyć kolejki do przechowywania węzłów, które będziemy przetwarzać. Oznacza to, że dla każdego węzła, z którym będziemy pracować, przepchniemy wszystkie pozostałe węzły, które można bezpośrednio przechodzić i jeszcze nie w kolejce.
Symulacja naszego przykładu:
Najpierw pchamy źródło w kolejce. Nasza kolejka będzie wyglądać następująco:
front
+-----+
| 1 |
+-----+
Poziom węzła 1 będzie wynosił 0. poziom [1] = 0 . Teraz zaczynamy nasz BFS. Najpierw otwieramy węzeł z naszej kolejki. Otrzymujemy węzeł 1 . Z tego jednego możemy przejść do węzła 4 , węzła 3 i węzła 2 . Dotarliśmy do tych węzłów z węzła 1 . Więc poziom [4] = poziom [3] = poziom [2] = poziom [1] + 1 = 1 . Teraz oznaczamy je jako odwiedzone i pchamy w kolejce.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Teraz otwieramy węzeł 4 i pracujemy z nim. Możemy przejść do węzła 7 z węzła 4 . poziom [7] = poziom [4] + 1 = 2 . Zaznaczamy węzeł 7 jako odwiedzony i pchamy go w kolejce.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Z węzła 3 możemy przejść do węzła 7 i węzła 8 . Ponieważ zaznaczyliśmy już węzeł 7 jako odwiedzony, oznaczamy węzeł 8 jako odwiedzony, zmieniamy poziom [8] = poziom [3] + 1 = 2 . Pchamy węzeł 8 w kolejce.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Proces ten będzie kontynuowany, aż dotrzemy do miejsca docelowego lub kolejka się opróżni. Tablica poziomów zapewni nam odległość najkrótszej ścieżki od źródła . Możemy zainicjować tablicę poziomów wartością nieskończoności , co oznacza, że węzły nie są jeszcze odwiedzane. Nasz pseudo-kod będzie:
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
Poprzez iterację po tablicy poziomów możemy ustalić odległość każdego węzła od źródła. Na przykład: odległość węzła 10 od źródła zostanie zapisana na poziomie [10] .
Czasami możemy potrzebować wydrukować nie tylko najkrótszą odległość, ale także ścieżkę, którą możemy przejść do naszego docelowego węzła ze źródła . W tym celu musimy zachować tablicę nadrzędną . rodzic [źródło] będzie miał wartość NULL. Dla każdej aktualizacji w tablicy poziomów po prostu dodamy parent[v] := u w naszym pseudo-kodzie wewnątrz pętli for. Po zakończeniu BFS, aby znaleźć ścieżkę, przejdziemy wstecz przez tablicę nadrzędną, aż dojdziemy do źródła, które będzie oznaczone wartością NULL. Pseudo-kod będzie:
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
Złożoność:
Odwiedziliśmy każdy węzeł raz i wszystkie krawędzie raz. Tak więc złożoność będzie wynosić O (V + E), gdzie V to liczba węzłów, a E to liczba krawędzi.
Znajdowanie najkrótszej ścieżki ze źródła na wykresie 2D
Przez większość czasu będziemy musieli znaleźć najkrótszą ścieżkę z jednego źródła do wszystkich innych węzłów lub określonego węzła na wykresie 2D. Powiedzmy na przykład: chcemy dowiedzieć się, ile ruchów potrzeba, aby rycerz dotarł do określonego kwadratu na szachownicy, lub mamy tablicę, w której niektóre komórki są zablokowane, musimy znaleźć najkrótszą drogę z jednej komórki do drugiej . Możemy poruszać się tylko poziomo i pionowo. Możliwe są również ruchy po przekątnej. W takich przypadkach możemy przekonwertować kwadraty lub komórki w węzłach i łatwo rozwiązać te problemy za pomocą BFS. Teraz naszym odwiedzanym rodzicem i poziomem będą tablice 2D. Dla każdego węzła rozważymy wszystkie możliwe ruchy. Aby znaleźć odległość do określonego węzła, sprawdzimy również, czy dotarliśmy do celu.
Będzie jeszcze jedna rzecz zwana tablicą kierunku. Spowoduje to po prostu przechowywanie wszystkich możliwych kombinacji kierunków, do których możemy przejść. Powiedzmy, że dla ruchów poziomych i pionowych nasze tablice kierunkowe będą:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Tutaj dx reprezentuje ruch na osi x, a dy reprezentuje ruch na osi y. Znowu ta część jest opcjonalna. Możesz też zapisać wszystkie możliwe kombinacje osobno. Ale łatwiej jest to obsłużyć za pomocą tablicy kierunkowej. Może być więcej, a nawet różne kombinacje ruchów ukośnych lub rycerskich.
Dodatkową częścią, o której musimy pamiętać, jest:
- Jeśli jakakolwiek komórka jest zablokowana, dla każdego możliwego ruchu sprawdzimy, czy komórka jest zablokowana, czy nie.
- Sprawdzimy również, czy przekroczyliśmy granice, czyli przekroczyliśmy granice tablicy.
- Podana zostanie liczba wierszy i kolumn.
Nasz pseudo-kod będzie:
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
Jak omówiliśmy wcześniej, BFS działa tylko w przypadku nieważonych wykresów. Do ważenia wykresów potrzebny jest algorytm Dijkstry . Do ujemnych cykli krawędzi potrzebujemy algorytmu Bellmana-Forda . Ponownie ten algorytm jest algorytmem najkrótszej ścieżki z jednego źródła. Jeśli będziemy musieli ustalić odległość od każdego węzła do wszystkich innych węzłów, potrzebujemy algorytmu Floyda-Warshalla .
Połączone elementy niekierowanego wykresu za pomocą BFS.
BFS można wykorzystać do znalezienia połączonych komponentów niekierowanego wykresu . Możemy również sprawdzić, czy dany wykres jest podłączony, czy nie. Nasza kolejna dyskusja zakłada, że mamy do czynienia z niekierowanymi grafami. Definicja połączonego wykresu to:
Wykres jest połączony, jeśli między każdą parą wierzchołków znajduje się ścieżka.
Poniżej znajduje się połączony wykres .
Poniższy wykres nie jest połączony i ma 2 połączone komponenty:
- Połączony komponent 1: {a, b, c, d, e}
- Połączony komponent 2: {f}
BFS jest algorytmem przechodzenia przez wykres. Więc zaczynając od losowego węzła źródłowego, jeśli po zakończeniu algorytmu odwiedzane są wszystkie węzły, wówczas wykres jest połączony, w przeciwnym razie nie jest połączony.
PseudoCode dla algorytmu.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
Implementacja C służąca do stwierdzenia, czy wykres niekierowany jest podłączony, czy nie:
#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';
}
}
}
Aby znaleźć wszystkie połączone elementy niekierowanego wykresu, musimy tylko dodać 2 linie kodu do funkcji BFS. Chodzi o to, aby wywoływać funkcję BFS, dopóki nie zostaną odwiedzone wszystkie wierzchołki.
Linie do dodania to:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
I
printf("%d ",vertex+1);
add this as first line of while loop in BFS
i definiujemy następującą funkcję:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}
