algorithm
Recherche en largeur
Recherche…
Recherche du chemin le plus court de la source aux autres nœuds
Breadth-first-search (BFS) est un algorithme permettant de parcourir ou de rechercher des structures de données arborescentes ou graphiques. Il commence à la racine de l'arbre (ou un nœud arbitraire d'un graphique, parfois appelé «clé de recherche») et explore les nœuds voisins en premier, avant de passer aux voisins de niveau supérieur. BFS a été inventé à la fin des années 1950 par Edward Forrest Moore , qui l'a utilisé pour trouver le chemin le plus court d'un labyrinthe et a été découvert indépendamment par CY Lee en tant qu'algorithme de routage en 1961.
Les processus de l'algorithme BFS fonctionnent sous ces hypothèses:
- Nous ne traverserons aucun noeud plus d'une fois.
- Le noeud source ou le noeud à partir duquel nous nous trouvons est situé dans le niveau 0.
- Les nœuds que nous pouvons atteindre directement depuis le nœud source sont des nœuds de niveau 1, les nœuds que nous pouvons atteindre directement à partir des nœuds de niveau 1 sont des nœuds de niveau 2 et ainsi de suite.
- Le niveau indique la distance du plus court chemin de la source.
Regardons un exemple: 
Supposons que ce graphique représente la connexion entre plusieurs villes, où chaque nœud indique une ville et une arête entre deux nœuds indique qu’il ya une route les reliant. Nous voulons passer du noeud 1 au noeud 10 . Donc, le noeud 1 est notre source , qui est le niveau 0 . Nous marquons le noeud 1 comme visité. Nous pouvons aller au noeud 2 , au noeud 3 et au noeud 4 d'ici. Ils seront donc au niveau (0 + 1) = nœuds de niveau 1 . Nous allons maintenant les marquer comme visités et travailler avec eux.
Les nœuds colorés sont visités. Les nœuds avec lesquels nous travaillons actuellement seront marqués en rose. Nous ne visiterons pas le même nœud deux fois. A partir du nœud 2 , du nœud 3 et du nœud 4 , nous pouvons aller au nœud 6, au nœud 7 et au nœud 8 . Marquons-les comme visités. Le niveau de ces nœuds sera le niveau (1 + 1) = niveau 2 . 
Si vous ne l'avez pas remarqué, le niveau des nœuds indique simplement la distance de chemin la plus courte par rapport à la source . Par exemple: nous avons trouvé le noeud 8 au niveau 2 . La distance entre la source et le noeud 8 est donc de 2 .
Nous n'avons pas encore atteint notre nœud cible, à savoir le nœud 10 . Alors, visitons les prochains nœuds. on peut aller directement du nœud 6 , du nœud 7 et du nœud 8 . 
Nous pouvons voir cela, nous avons trouvé le nœud 10 au niveau 3 . Donc, le plus court chemin de la source au noeud 10 est 3. Nous avons recherché le graphique par niveau et trouvé le plus court chemin. Maintenant, effaçons les bords que nous n'avons pas utilisés: 
Après avoir supprimé les arêtes que nous n'utilisions pas, nous obtenons un arbre appelé arborescence BFS. Cet arbre montre le chemin le plus court entre la source et tous les autres nœuds.
Notre tâche consistera donc à passer de la source aux nœuds de niveau 1 . Ensuite, du niveau 1 au niveau 2, nous atteignons notre destination. Nous pouvons utiliser la file d' attente pour stocker les noeuds que nous allons traiter. Autrement dit, pour chaque nœud avec lequel nous allons travailler, nous allons pousser tous les autres nœuds pouvant être directement traversés et non encore traversés dans la file d'attente.
La simulation de notre exemple:
Nous commençons par pousser la source dans la file d'attente. Notre file d'attente ressemblera à:
front
+-----+
| 1 |
+-----+
Le niveau du noeud 1 sera 0. niveau [1] = 0 . Maintenant, nous commençons notre BFS. Au début, nous ouvrons un nœud de notre file d'attente. Nous obtenons le noeud 1 . Nous pouvons aller au nœud 4 , au nœud 3 et au nœud 2 de celui-ci. Nous avons atteint ces nœuds à partir du nœud 1 . Donc, niveau [4] = niveau [3] = niveau [2] = niveau [1] + 1 = 1 . Maintenant, nous les marquons comme visités et les mettons dans la file d'attente.
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
Maintenant, nous ouvrons le noeud 4 et travaillons avec. On peut aller au noeud 7 du noeud 4 . niveau [7] = niveau [4] + 1 = 2 . Nous marquons le noeud 7 comme visité et le plaçons dans la file d'attente.
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
A partir du nœud 3 , on peut aller au nœud 7 et au nœud 8 . Comme nous avons déjà marqué le nœud 7 comme visité, nous marquons le nœud 8 comme visité, nous modifions le niveau [8] = niveau [3] + 1 = 2 . Nous poussons le nœud 8 dans la file d'attente.
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
Ce processus continuera jusqu'à ce que nous atteignions notre destination ou que la file d'attente devienne vide. Le tableau de niveaux nous fournira la distance du plus court chemin depuis la source . Nous pouvons initialiser le tableau de niveau avec une valeur infinie , ce qui marquera que les nœuds ne sont pas encore visités. Notre pseudo-code sera:
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
En parcourant le tableau de niveaux , nous pouvons déterminer la distance de chaque nœud à partir de la source. Par exemple: la distance entre le nœud 10 et la source sera stockée dans le niveau [10] .
Parfois, nous pourrions avoir besoin d'imprimer non seulement la distance la plus courte, mais aussi le chemin par lequel nous pouvons aller à notre nœud à partir de la source . Pour cela, nous devons conserver un tableau parent . parent [source] sera NULL. Pour chaque mise à jour dans le tableau de niveaux , nous ajouterons simplement le parent[v] := u dans notre pseudo-code dans la boucle for. Après avoir terminé BFS, pour trouver le chemin, nous allons parcourir le tableau parent jusqu’à ce que nous ayons atteint la source qui sera désignée par la valeur NULL. Le pseudo-code sera:
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
Complexité:
Nous avons visité chaque noeud une fois et chaque fois. La complexité sera donc O (V + E) où V est le nombre de nœuds et E le nombre d’arêtes.
Trouver le plus court chemin de la source dans un graphique 2D
La plupart du temps, nous devrons trouver le chemin le plus court entre une source unique et tous les autres nœuds ou un nœud spécifique dans un graphique 2D. Dites par exemple: nous voulons savoir combien de mouvements sont nécessaires pour qu'un chevalier atteigne un certain carré dans un échiquier, ou nous avons un tableau où certaines cellules sont bloquées, nous devons trouver le plus court chemin d'une cellule à une autre . Nous ne pouvons bouger que horizontalement et verticalement. Même les mouvements diagonaux peuvent être possibles. Dans ces cas, nous pouvons convertir les carrés ou les cellules dans les nœuds et résoudre facilement ces problèmes en utilisant BFS. Maintenant, notre site parent et niveau visité sera des tableaux 2D. Pour chaque nœud, nous considérerons tous les mouvements possibles. Pour trouver la distance à un nœud spécifique, nous vérifierons également si nous avons atteint notre destination.
Il y aura une chose supplémentaire appelée tableau de direction. Cela stockera simplement toutes les combinaisons possibles de directions vers lesquelles nous pouvons aller. Disons que, pour les déplacements horizontaux et verticaux, nos tableaux de direction seront:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
Ici, dx représente le déplacement en abscisse et dy représente le déplacement en ordonnée. Encore une fois, cette partie est facultative. Vous pouvez également écrire toutes les combinaisons possibles séparément. Mais il est plus facile de le gérer en utilisant un tableau de direction. Il peut y avoir des combinaisons plus nombreuses, voire différentes, pour les mouvements en diagonale ou les mouvements de chevalier.
La partie supplémentaire que nous devons garder à l’esprit est la suivante:
- Si l'une des cellules est bloquée, pour chaque mouvement possible, nous vérifierons si la cellule est bloquée ou non.
- Nous allons également vérifier si nous sommes sortis des limites, c'est-à-dire que nous avons dépassé les limites du tableau.
- Le nombre de lignes et de colonnes sera donné.
Notre pseudo-code sera:
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
Comme nous l'avons vu précédemment, BFS ne fonctionne que pour les graphiques non pondérés. Pour les graphiques pondérés, nous aurons besoin de l'algorithme de Dijkstra . Pour les cycles de fronts négatifs, nous avons besoin de l'algorithme de Bellman-Ford . Encore une fois, cet algorithme est l'algorithme à source unique le plus court. Si nous devons trouver la distance entre chaque nœud et tous les autres nœuds, nous aurons besoin de l'algorithme de Floyd-Warshall .
Composants connectés de graphique non dirigé à l'aide de BFS.
BFS peut être utilisé pour trouver les composants connectés d'un graphique non dirigé . Nous pouvons également trouver si le graphique donné est connecté ou non. Notre discussion ultérieure suppose que nous avons affaire à des graphes non orientés. La définition d'un graphe connecté est la suivante:
Un graphique est connecté s'il existe un chemin entre chaque paire de sommets.
Voici un graphique connecté .
Le graphique suivant n'est pas connecté et comporte 2 composants connectés:
- Composant connecté 1: {a, b, c, d, e}
- Composant connecté 2: {f}
BFS est un algorithme de parcours graphique. Donc, à partir d'un nœud source aléatoire, si à la fin de l'algorithme, tous les nœuds sont visités, alors le graphique est connecté, sinon il n'est pas connecté.
PseudoCode pour l'algorithme.
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
Implémentation C pour savoir si un graphe non orienté est connecté ou non:
#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';
}
}
}
Pour rechercher tous les composants connectés d'un graphique non dirigé, il suffit d'ajouter 2 lignes de code à la fonction BFS. L'idée est d'appeler la fonction BFS jusqu'à ce que tous les sommets soient visités.
Les lignes à ajouter sont:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
ET
printf("%d ",vertex+1);
add this as first line of while loop in BFS
et nous définissons la fonction suivante:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}
