algorithm
Breitensuche
Suche…
Den kürzesten Pfad von der Quelle zu anderen Knoten finden
Breadth-First-Search (BFS) ist ein Algorithmus zum Durchsuchen oder Durchsuchen von Baum- oder Diagrammdatenstrukturen. Es beginnt an der Baumwurzel (oder einem beliebigen Knoten eines Graphen, manchmal als "Suchschlüssel" bezeichnet) und erkundet zuerst die Nachbarknoten, bevor es zu den nächsten Nachbarn übergeht. BFS wurde in den späten 50er Jahren von Edward Forrest Moore erfunden, der den kürzesten Weg aus einem Labyrinth fand und 1961 von CY Lee unabhängig als ein Routing-Algorithmus entdeckt wurde.
Die Prozesse des BFS-Algorithmus arbeiten unter folgenden Annahmen:
- Wir werden keinen Knoten mehr als einmal durchqueren.
- Der Quellknoten oder der Knoten, von dem aus wir beginnen, befindet sich in der Ebene 0.
- Die Knoten, die wir direkt vom Quellknoten erreichen können, sind Knoten der Ebene 1, die Knoten, die wir direkt von Knoten der Ebene 1 erreichen können, sind Knoten der Ebene 2 und so weiter.
- Der Pegel gibt die Entfernung des kürzesten Pfads von der Quelle an.
Sehen wir uns ein Beispiel an: 
Angenommen, dieser Graph stellt eine Verbindung zwischen mehreren Städten dar, wobei jeder Knoten eine Stadt bezeichnet und eine Kante zwischen zwei Knoten zeigt, dass eine Straße sie verbindet. Wir möchten vom Knoten 1 zum Knoten 10 gehen . Knoten 1 ist also unsere Quelle , die Ebene 0 ist . Wir markieren Knoten 1 als besucht. Von hier aus können wir zum Knoten 2 , zum Knoten 3 und zum Knoten 4 gehen . Sie sind also Level (0 + 1) = Level 1- Knoten. Jetzt markieren wir sie als besucht und arbeiten mit ihnen.
Die farbigen Knoten werden besucht. Die Knoten, mit denen wir gerade arbeiten, werden mit rosa markiert. Wir werden denselben Knoten nicht zweimal besuchen. Von Knoten 2 , Knoten 3 und Knoten 4 können wir zu Knoten 6, Knoten 7 und Knoten 8 gelangen . Lassen Sie uns sie als besucht markieren. Die Ebene dieser Knoten ist Ebene (1 + 1) = Ebene 2 . 
Wenn Sie es nicht bemerkt haben, geben die Knotenpunkte einfach die kürzeste Wegentfernung von der Quelle an . Zum Beispiel: Wir haben Knoten 8 auf Ebene 2 gefunden . Der Abstand von Quelle zu Knoten 8 beträgt also 2 .
Wir haben unseren Zielknoten, den Knoten 10, noch nicht erreicht. Lass uns also die nächsten Knoten besuchen. Wir können direkt von Knoten 6 , Knoten 7 und Knoten 8 gehen . 
Wir können das sehen, wir haben Knoten 10 auf Stufe 3 gefunden . Der kürzeste Pfad von der Quelle zum Knoten 10 ist also 3. Wir haben die Grafikebene für Ebene gesucht und den kürzesten Pfad gefunden. Nun löschen wir die Kanten, die wir nicht verwendet haben: 
Nachdem wir die Kanten entfernt haben, die wir nicht verwendet haben, erhalten wir einen Baum namens BFS-Baum. Dieser Baum zeigt den kürzesten Pfad von der Quelle zu allen anderen Knoten.
Unsere Aufgabe wird also sein, von der Quelle zu den Knoten der Ebene 1 zu gelangen . Dann von Ebene 1 zu Ebene 2 und so weiter, bis wir unser Ziel erreichen. Wir können die Warteschlange verwenden , um die Knoten zu speichern, die wir verarbeiten werden. Das heißt, für jeden Knoten, mit dem wir arbeiten werden, werden wir alle anderen Knoten pushen, die direkt und nicht noch in der Warteschlange durchlaufen werden können.
Die Simulation unseres Beispiels:
Zuerst drücken wir die Quelle in die Warteschlange. Unsere Warteschlange wird wie folgt aussehen:
front
+-----+
| 1 |
+-----+
Der Pegel des Knotens 1 wird 0 sein. Level [1] = 0 . Jetzt starten wir unser BFS. Zuerst ziehen wir einen Knoten aus unserer Warteschlange. Wir bekommen Knoten 1 . Von diesem Knoten können wir zu Knoten 4 , Knoten 3 und Knoten 2 gelangen . Wir haben diese Knoten von Knoten 1 erreicht . Ebene [4] = Ebene [3] = Ebene [2] = Ebene [1] + 1 = 1 . Jetzt markieren wir sie als besucht und schieben sie in die Warteschlange.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Jetzt knacken wir Knoten 4 und arbeiten damit. Wir können von Knoten 4 zu Knoten 7 gehen. Stufe [7] = Stufe [4] + 1 = 2 . Wir markieren Knoten 7 als besucht und verschieben ihn in die Warteschlange.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
Von Knoten 3 können wir zu Knoten 7 und 8 gehen . Da wir Knoten 7 bereits als besucht markiert haben, markieren wir Knoten 8 als besucht. Wir ändern Ebene [8] = Ebene [3] + 1 = 2 . Wir schieben Knoten 8 in die Warteschlange.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Dieser Vorgang wird fortgesetzt, bis wir unser Ziel erreichen oder die Warteschlange leer ist. Das Level- Array gibt uns die Entfernung des kürzesten Pfads von der Quelle an . Wir können ein Level- Array mit einem unendlich großen Wert initialisieren, der anzeigt, dass die Knoten noch nicht besucht sind. Unser Pseudo-Code lautet:
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
Durch Iteration durch das Level- Array können wir die Entfernung jedes Knotens von der Quelle ermitteln. Zum Beispiel: Die Entfernung des Knotens 10 von der Quelle wird in Stufe [10] gespeichert.
Manchmal müssen wir möglicherweise nicht nur die kürzeste Entfernung drucken, sondern auch den Pfad, über den wir von der Quelle zu unserem Zielknoten gehen können. Dafür müssen wir ein übergeordnetes Array behalten. parent [source] wird NULL sein. Für jedes Update im Level- Array fügen wir in unserem Pseudocode in der for-Schleife einfach parent[v] := u . Nach dem Beenden von BFS werden wir das übergeordnete Array zurückverfolgen, um den Pfad zu finden, bis wir die Quelle erreichen, die mit dem NULL-Wert bezeichnet wird. Der Pseudo-Code lautet:
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
Komplexität:
Wir haben jeden Knoten einmal und alle Kanten einmal besucht. Die Komplexität ist also O (V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
Suchen des kürzesten Pfads aus der Quelle in einem 2D-Diagramm
In den meisten Fällen müssen wir den kürzesten Weg von einer einzelnen Quelle zu allen anderen Knoten oder zu einem bestimmten Knoten in einem 2D-Diagramm ermitteln. Beispiel: Wir möchten herausfinden, wie viele Züge ein Ritter benötigt, um ein bestimmtes Quadrat in einem Schachbrett zu erreichen, oder wir haben ein Array, in dem einige Zellen blockiert sind. Wir müssen den kürzesten Weg von einer Zelle zur anderen ermitteln . Wir können uns nur horizontal und vertikal bewegen. Auch diagonale Bewegungen können möglich sein. Für diese Fälle können wir die Quadrate oder Zellen in Knoten konvertieren und diese Probleme einfach mit BFS lösen. Unsere besuchten , übergeordneten und Level werden jetzt 2D-Arrays sein. Für jeden Knoten werden alle möglichen Bewegungen berücksichtigt. Um die Entfernung zu einem bestimmten Knoten zu ermitteln, prüfen wir auch, ob wir unser Ziel erreicht haben.
Es wird eine zusätzliche Funktion namens Richtungsarray geben. Dadurch werden einfach alle möglichen Kombinationen von Richtungen gespeichert, zu denen wir gehen können. Sagen wir, für horizontale und vertikale Bewegungen sind unsere Richtungsarrays:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Dabei repräsentiert dx die Bewegung in der x-Achse und dy die Bewegung in der y-Achse. Auch dieser Teil ist optional. Sie können auch alle möglichen Kombinationen separat schreiben. Es ist jedoch einfacher, mit Richtungsarray zu arbeiten. Es können mehr und sogar verschiedene Kombinationen für diagonale Bewegungen oder Ritterbewegungen vorhanden sein.
Der zusätzliche Teil, den wir berücksichtigen müssen, ist:
- Wenn eine Zelle blockiert ist, prüfen wir bei jeder möglichen Bewegung, ob die Zelle blockiert ist oder nicht.
- Wir werden auch prüfen, ob wir die Grenzen überschritten haben, das heißt, wir haben die Arraygrenzen überschritten.
- Die Anzahl der Zeilen und Spalten wird angegeben.
Unser Pseudo-Code lautet:
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
Wie bereits erwähnt, funktioniert BFS nur für nicht gewichtete Diagramme. Für gewichtete Diagramme benötigen wir den Dijkstra -Algorithmus. Für negative Flankenzyklen benötigen wir den Bellman-Ford -Algorithmus. Auch dieser Algorithmus ist ein Algorithmus für den kürzesten Weg aus einem Quellcode. Wenn wir die Entfernung von jedem Knoten zu allen anderen Knoten herausfinden müssen, benötigen wir den Algorithmus von Floyd-Warshall .
Verbundene Komponenten eines ungerichteten Diagramms mit BFS.
BFS kann verwendet werden, um die verbundenen Komponenten eines ungerichteten Graphen zu finden . Wir können auch feststellen, ob der angegebene Graph verbunden ist oder nicht. Bei der anschließenden Diskussion wird davon ausgegangen, dass es sich um ungerichtete Graphen handelt. Die Definition eines verbundenen Graphen lautet:
Ein Diagramm wird verbunden, wenn sich zwischen jedem Scheitelpaar ein Pfad befindet.
Es folgt ein zusammenhängender Graph .
Der folgende Graph ist nicht verbunden und hat 2 verbundene Komponenten:
- Angeschlossene Komponente 1: {a, b, c, d, e}
- Angeschlossene Komponente 2: {f}
BFS ist ein Graph-Traversal-Algorithmus. Wenn also von einem zufälligen Quellknoten aus alle Knoten besucht werden, wird der Graph verbunden, andernfalls nicht verbunden.
PseudoCode für den Algorithmus.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
C-Implementierung zum Ermitteln, ob ein ungerichteter Graph verbunden ist oder nicht:
#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';
}
}
}
Um alle verbundenen Komponenten eines ungerichteten Graphen zu finden, müssen Sie der BFS-Funktion nur zwei Codezeilen hinzufügen. Die Idee ist, die BFS-Funktion aufzurufen, bis alle Scheitelpunkte besucht sind.
Die Zeilen, die hinzugefügt werden sollen, sind:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
UND
printf("%d ",vertex+1);
add this as first line of while loop in BFS
und wir definieren die folgende Funktion:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}