algorithm
Breedte-eerste zoekopdracht
Zoeken…
Het kortste pad van bron naar andere knooppunten vinden
Breadth-first-search (BFS) is een algoritme voor het doorlopen of zoeken van boom- of grafiekdatastructuren. Het begint bij de boomwortel (of een willekeurig knooppunt van een grafiek, soms een 'zoeksleutel' genoemd) en verkent eerst de buurknooppunten, voordat het naar de buren van het volgende niveau gaat. BFS werd uitgevonden in de late jaren 1950 door Edward Forrest Moore , die het gebruikte om het kortste pad uit een doolhof te vinden en onafhankelijk ontdekt door CY Lee als een draad routing algoritme in 1961.
De processen van het BFS-algoritme werken onder deze veronderstellingen:
- We zullen geen enkel knooppunt meer dan eens doorkruisen.
- Bronknooppunt of het knooppunt waarmee we beginnen bevindt zich op niveau 0.
- De knooppunten die we rechtstreeks kunnen bereiken vanaf het bronknooppunt zijn knooppunten van niveau 1, de knooppunten die we direct kunnen bereiken vanaf knooppunten van niveau 1 zijn knooppunten van niveau 2 enzovoort.
- Het niveau geeft de afstand aan van het kortste pad vanaf de bron.
Laten we een voorbeeld bekijken: 
Laten we aannemen dat deze grafiek de verbinding tussen meerdere steden vertegenwoordigt, waarbij elke knoop een stad aangeeft en een rand tussen twee knooppunten aangeeft dat er een weg is die ze verbindt. We willen van knooppunt 1 naar knooppunt 10 gaan . Dus knooppunt 1 is onze bron , wat niveau 0 is . We markeren knooppunt 1 als bezocht. We kunnen vanaf hier naar knooppunt 2 , knooppunt 3 en knooppunt 4 gaan . Dus ze zijn level (0 + 1) = level 1 nodes. Nu zullen we ze markeren als bezocht en met hen samenwerken.
De gekleurde knooppunten worden bezocht. De knooppunten waarmee we momenteel werken, worden gemarkeerd met roze. We zullen niet twee keer hetzelfde knooppunt bezoeken. Van knooppunt 2 , knooppunt 3 en knooppunt 4 kunnen we naar knooppunt 6, knooppunt 7 en knooppunt 8 gaan . Laten we ze als bezocht markeren. Het niveau van deze knooppunten is niveau (1 + 1) = niveau 2 . 
Als u het niet hebt gemerkt, geeft het knooppuntniveau eenvoudigweg de kortste padafstand vanaf de bron aan . Bijvoorbeeld: we hebben knooppunt 8 gevonden op niveau 2 . Dus de afstand van bron tot knooppunt 8 is 2 .
We hebben ons doelknooppunt nog niet bereikt, dat is knooppunt 10 . Laten we dus de volgende knooppunten bezoeken. we kunnen rechtstreeks naar van knooppunt 6 , knooppunt 7 en knooppunt 8 gaan . 
We kunnen zien dat we knooppunt 10 op niveau 3 hebben gevonden. Dus het kortste pad van bron naar knooppunt 10 is 3. We hebben de grafiek niveau voor niveau doorzocht en het kortste pad gevonden. Laten we nu de randen wissen die we niet hebben gebruikt: 
Na het verwijderen van de randen die we niet hebben gebruikt, krijgen we een boom genaamd BFS-boom. Deze boom toont het kortste pad van bron naar alle andere knooppunten.
Het is dus onze taak om van bron- naar niveau 1- knooppunten te gaan. Daarna van knooppunten van niveau 1 tot niveau 2 enzovoort totdat we onze bestemming bereiken. We kunnen de wachtrij gebruiken om de knooppunten op te slaan die we gaan verwerken. Dat wil zeggen, voor elk knooppunt waarmee we gaan werken, zullen we alle andere knooppunten pushen die direct kunnen worden doorlopen en nog niet in de wachtrij worden doorlopen.
De simulatie van ons voorbeeld:
Eerst duwen we de bron in de wachtrij. Onze wachtrij ziet eruit als:
front
+-----+
| 1 |
+-----+
Het niveau van knooppunt 1 is 0. niveau [1] = 0 . Nu beginnen we onze BFS. In eerste instantie zetten we een knooppunt uit onze wachtrij. We krijgen knooppunt 1 . We kunnen vanaf deze naar knooppunt 4 , knooppunt 3 en knooppunt 2 gaan . We hebben deze knooppunten bereikt vanaf knooppunt 1 . Dus niveau [4] = niveau [3] = niveau [2] = niveau [1] + 1 = 1 . Nu markeren we ze als bezocht en duwen we ze in de wachtrij.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Nu poppen we knooppunt 4 en werken ermee. We kunnen naar knooppunt 7 gaan van knooppunt 4 . niveau [7] = niveau [4] + 1 = 2 . We markeren knooppunt 7 als bezocht en duwen het in de wachtrij.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Vanaf knooppunt 3 kunnen we naar knooppunt 7 en knooppunt 8 gaan . Omdat we knooppunt 7 al als bezocht hebben gemarkeerd, markeren we knooppunt 8 als bezocht, we veranderen niveau [8] = niveau [3] + 1 = 2 . We duwen knooppunt 8 in de wachtrij.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Dit proces gaat door totdat we onze bestemming bereiken of de wachtrij leeg raakt. De niveau- array geeft ons de afstand van het kortste pad vanaf de bron . We kunnen een niveau- array met oneindige waarde initialiseren, wat aangeeft dat de knooppunten nog niet zijn bezocht. Onze pseudo-code zal zijn:
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
Door de niveau- array te doorlopen, kunnen we de afstand van elk knooppunt tot de bron achterhalen. Bijvoorbeeld: de afstand van knooppunt 10 tot bron wordt opgeslagen in niveau [10] .
Soms moeten we niet alleen de kortste afstand afdrukken, maar ook het pad via welke we vanaf de bron naar onze bestemming kunnen gaan. Hiervoor moeten we een bovenliggende array houden. ouder [bron] zal NULL zijn. Voor elke update in level array voegen we gewoon parent[v] := u aan onze pseudocode in de for-lus. Na het voltooien van BFS, om het pad te vinden, zullen we de bovenliggende array doorlopen totdat we de bron bereiken die wordt aangeduid met de waarde NULL. De pseudo-code zal zijn:
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
complexiteit:
We hebben elk knooppunt één keer bezocht en elke rand één keer. De complexiteit is dus O (V + E) waarbij V het aantal knopen is en E het aantal randen is.
Het kortste pad van de bron zoeken in een 2D-grafiek
Meestal moeten we het kortste pad vinden van één bron naar alle andere knooppunten of een specifiek knooppunt in een 2D-grafiek. Zeg bijvoorbeeld: we willen weten hoeveel bewegingen een ridder nodig heeft om een bepaald vierkant in een schaakbord te bereiken, of we hebben een reeks waarin sommige cellen worden geblokkeerd, we moeten het kortste pad van de ene naar de andere cel vinden . We kunnen alleen horizontaal en verticaal bewegen. Zelfs diagonale bewegingen kunnen ook mogelijk zijn. Voor deze gevallen kunnen we de vierkanten of cellen in knooppunten omzetten en deze problemen eenvoudig oplossen met behulp van BFS. Nu worden ons bezochte , bovenliggende en niveau 2D-arrays. Voor elk knooppunt zullen we alle mogelijke bewegingen overwegen. Om de afstand tot een specifiek knooppunt te vinden, zullen we ook controleren of we onze bestemming hebben bereikt.
Er is nog een ding dat direction array wordt genoemd. Hiermee worden gewoon alle mogelijke combinaties van richtingen opgeslagen waar we naartoe kunnen gaan. Laten we zeggen dat voor horizontale en verticale bewegingen onze richtingsarrays zijn:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Hier stelt dx beweging in x-as voor en dy vertegenwoordigt beweging in y-as. Ook dit onderdeel is optioneel. U kunt ook alle mogelijke combinaties afzonderlijk schrijven. Maar het is gemakkelijker om het te gebruiken met behulp van richtingsmatrix. Er kunnen meer en zelfs verschillende combinaties zijn voor diagonale bewegingen of ridderbewegingen.
Het extra deel dat we in gedachten moeten houden is:
- Als een van de cellen wordt geblokkeerd, controleren we voor elke mogelijke zet of de cel is geblokkeerd of niet.
- We zullen ook controleren of we de grenzen hebben overschreden, dat wil zeggen dat we de grenzen van de array hebben overschreden.
- Het aantal rijen en kolommen wordt gegeven.
Onze pseudo-code zal zijn:
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
Zoals we eerder hebben besproken, werkt BFS alleen voor ongewogen grafieken. Voor gewogen grafieken hebben we het algoritme van Dijkstra nodig. Voor negatieve edge-cycli hebben we het algoritme van Bellman-Ford nodig. Wederom is dit algoritme een algoritme voor het kortste pad met één bron. Als we de afstand van elke knooppunt tot alle andere knooppunten moeten bepalen, hebben we het algoritme van Floyd-Warshall nodig.
Aangesloten componenten van niet-gerichte grafiek met behulp van BFS.
BFS kan worden gebruikt om de verbonden componenten van een niet-gerichte grafiek te vinden . We kunnen ook vinden of de gegeven grafiek is verbonden of niet. In onze daaropvolgende discussie wordt ervan uitgegaan dat we te maken hebben met ongerichte grafieken. De definitie van een verbonden grafiek is:
Een grafiek is verbonden als er een pad is tussen elk paar hoekpunten.
Hierna volgt een verbonden grafiek .
De volgende grafiek is niet verbonden en heeft 2 verbonden componenten:
- Verbonden component 1: {a, b, c, d, e}
- Verbonden component 2: {f}
BFS is een grafisch traversaal algoritme. Dus vanaf een willekeurig bronknooppunt, als bij beëindiging van het algoritme alle knooppunten worden bezocht, is de grafiek verbonden, anders is deze niet verbonden.
PseudoCode voor het algoritme.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
C-implementatie om te bepalen of een niet-gerichte grafiek is verbonden of niet:
#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';
}
}
}
Voor het vinden van alle verbonden componenten van een ongerichte grafiek, hoeven we slechts 2 coderegels toe te voegen aan de BFS-functie. Het idee is om de BFS-functie aan te roepen totdat alle hoekpunten zijn bezocht.
De toe te voegen regels zijn:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
EN
printf("%d ",vertex+1);
add this as first line of while loop in BFS
en we definiëren de volgende functie:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}