algorithm
Utöka första sökningen
Sök…
Hitta den kortaste vägen från källa till andra noder
Breadth-first-search (BFS) är en algoritm för att korsa eller söka i träd- eller diagramdatastrukturer. Det börjar vid trädroten (eller någon godtycklig nod i en graf, ibland kallad en "söknyckel") och utforskar grannnoderna innan den går till nästa nivågrannar. BFS uppfanns i slutet av 1950-talet av Edward Forrest Moore , som använde den för att hitta den kortaste vägen ur en labyrint och upptäcktes oberoende av CY Lee som en trådrutningsalgoritm 1961.
Processerna för BFS-algoritm fungerar enligt dessa antaganden:
- Vi kommer inte över någon nod mer än en gång.
- Källnoden eller noden som vi börjar ligger i nivå 0.
- Noderna som vi direkt kan nå från källnoden är nivå 1-noder, de noder vi direkt kan nå från nivå 1-noder är nivå 2-noder och så vidare.
- Nivån anger avståndet för den kortaste vägen från källan.
Låt oss se ett exempel: 
Låt oss anta att denna graf representerar anslutning mellan flera städer, där varje nod anger en stad och en kant mellan två noder anger att det finns en väg som länkar dem. Vi vill gå från nod 1 till nod 10 . Så nod 1 är vår källa , som är nivå 0 . Vi markerar nod 1 som besökt. Vi kan gå till nod 2 , nod 3 och nod 4 härifrån. Så de kommer att vara nivå (0 + 1) = nivå 1- noder. Nu markerar vi dem som besökta och arbetar med dem.
De färgade noderna besöks. Noderna som vi för närvarande arbetar med kommer att markeras med rosa. Vi besöker inte samma nod två gånger. Från nod 2 , nod 3 och nod 4 kan vi gå till nod 6, nod 7 och nod 8 . Låt oss markera dem som besökta. Noden för dessa noder kommer att vara nivå (1 + 1) = nivå 2 . 
Om du inte har lagt märke till anger nivån på noder helt enkelt det kortaste vägavståndet från källan . Till exempel: vi har hittat nod 8 på nivå 2 . Så avståndet från källa till nod 8 är 2 .
Vi nådde ännu inte vår målnod, det vill säga nod 10 . Så låt oss besöka nästa noder. vi kan direkt gå till från nod 6 , nod 7 och nod 8 . 
Vi kan se att vi hittade nod 10 på nivå 3 . Så den kortaste vägen från källa till nod 10 är 3. Vi sökte grafnivån för nivå och hittade den kortaste vägen. Låt oss nu radera kanterna som vi inte använde: 
Efter att vi tagit bort kanterna som vi inte använde får vi ett träd som heter BFS-träd. Detta träd visar den kortaste vägen från källa till alla andra noder.
Så vår uppgift blir att gå från källa till nivå 1- noder. Sedan från nivå 1 till nivå 2- noder och så vidare tills vi når vår destination. Vi kan använda kö för att lagra noderna som vi ska bearbeta. Det vill säga, för varje nod vi ska arbeta med, trycker vi på alla andra noder som kan korsas direkt och ännu inte korsas i kön.
Simuleringen av vårt exempel:
Först trycker vi på källan i kön. Vår kö kommer att se ut:
front
+-----+
| 1 |
+-----+
Noden 1 kommer att vara 0. nivå [1] = 0 . Nu börjar vi vår BFS. Till att börja med poppar vi en nod från vår kö. Vi får nod 1 . Vi kan gå till nod 4 , nod 3 och nod 2 från denna. Vi har nått dessa noder från nod 1 . Så nivå [4] = nivå [3] = nivå [2] = nivå [1] + 1 = 1 . Nu markerar vi dem som besökta och skjuter dem i kön.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Nu pop vi node 4 och arbetar med den. Vi kan gå till nod 7 från nod 4 . nivå [7] = nivå [4] + 1 = 2 . Vi markerar nod 7 som besökt och skjuter den i kön.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Från nod 3 kan vi gå till nod 7 och nod 8 . Eftersom vi redan har markerat nod 7 som besökt, markerar vi nod 8 som besökt, vi ändrar nivå [8] = nivå [3] + 1 = 2 . Vi skjuter node 8 i kön.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Den här processen kommer att fortsätta tills vi når vår destination eller kön blir tom. Nivån array ger oss avståndet för kortaste vägen från källan. Vi kan initiera nivå array med infinity värde, vilket kommer att markera att noderna ännu inte besökt. Vår pseudokod kommer att vara:
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
Genom att iterera genom nivån array, kan vi ta reda på avståndet för varje nod från källan. Till exempel: avståndet från nod 10 från källan lagras i nivå [10] .
Ibland kan vi behöva skriva ut inte bara det kortaste avståndet, utan också den väg som vi kan gå till vår avsedda nod från källan . För detta måste vi hålla en föräldrarray . överordnad [källa] kommer att vara NULL. För varje uppdatering i nivån array, lägger vi bara till parent[v] := u i vår pseudokod inuti för slingan. Efter att ha avslutat BFS, för att hitta sökvägen, kommer vi att gå tillbaka till överordnad array tills vi når källan som kommer att betecknas med NULL-värde. Pseudokoden kommer att vara:
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
Komplexitet:
Vi har besökt varje nod en gång och varje kanter en gång. Så komplexiteten blir O (V + E) där V är antalet noder och E är antalet kanter.
Hitta kortaste sökvägen från källan i en 2D-graf
Oftast måste vi ta reda på den kortaste vägen från enskild källa till alla andra noder eller en specifik nod i en 2D-graf. Säg till exempel: vi vill ta reda på hur många drag som krävs för att en riddare ska nå ett visst torg i ett schackbräde, eller om vi har en grupp där vissa celler är blockerade, vi måste ta reda på den kortaste vägen från en cell till en annan . Vi kan röra oss bara horisontellt och vertikalt. Även diagonala drag kan vara möjligt. För dessa fall kan vi konvertera rutorna eller cellerna i noder och lösa dessa problem enkelt med BFS. Nu är vår besökta , förälder och nivå 2D-arrayer. För varje nod överväger vi alla möjliga drag. För att hitta avståndet till en specifik nod kontrollerar vi också om vi har nått vår destination.
Det kommer att finnas ytterligare en sak som kallas riktningsfält. Detta lagrar helt enkelt alla möjliga kombinationer av vägbeskrivningar vi kan gå till. Låt oss säga, för horisontella och vertikala rörelser kommer våra riktningsarrayer att vara:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Här representerar dx rörelse i x-axel och dy representerar rörelse i y-axel. Återigen är denna del valfri. Du kan också skriva alla möjliga kombinationer separat. Men det är lättare att hantera det med riktningsfält. Det kan finnas fler och till och med olika kombinationer för diagonala drag eller riddare.
Den ytterligare delen vi behöver komma ihåg är:
- Om någon av cellen är blockerad, för alla möjliga drag, kontrollerar vi om cellen är blockerad eller inte.
- Vi kommer också att kontrollera om vi har gått utanför gränserna, det vill säga att vi har korsat matrisgränserna.
- Antalet rader och kolumner anges.
Vår pseudokod kommer att vara:
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
Som vi har diskuterat tidigare fungerar BFS bara för ovägda grafer. För viktade grafer behöver vi Dijkstras algoritm. För negativa kantcykler behöver vi Bellman-Fords algoritm. Återigen är den här algoritmen kortaste sökvägsalgoritm. Om vi behöver ta reda på avståndet från varje noder till alla andra noder, behöver vi Floyd-Warshalls algoritm.
Anslutna komponenter i odirigerad graf med BFS.
BFS kan användas för att hitta de anslutna komponenterna i en riktad graf . Vi kan också hitta om den givna grafen är ansluten eller inte. Vår efterföljande diskussion antar att vi har att göra med inställda diagram. Definitionen av en ansluten graf är:
En graf är ansluten om det finns en sökväg mellan varje par vertikaler.
Följande är en ansluten graf .
Följande graf är inte ansluten och har två anslutna komponenter:
- Ansluten komponent 1: {a, b, c, d, e}
- Ansluten komponent 2: {f}
BFS är en grafversionalgoritm. Så från en slumpmässig källnod, om algoritmen avslutas, besöks alla noder, är grafen ansluten, annars är den inte ansluten.
PseudoCode för algoritmen.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
C-implementering för att hitta om en riktad graf är ansluten eller inte:
#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';
}
}
}
För att hitta alla anslutna komponenter i en riktad graf behöver vi bara lägga till två kodrader till BFS-funktionen. Tanken är att ringa BFS-funktion tills alla vertikaler har besökts.
Raderna som ska läggas till är:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
OCH
printf("%d ",vertex+1);
add this as first line of while loop in BFS
och vi definierar följande funktion:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}