Algorithme de recherche de graphes (Graph Search) en C++- Explication, exemple et code

L'algorithme Graph Search est une technique fondamentale dans le domaine du traitement de graphes et de la recherche d'informations. Cet algorithme nous permet de trouver des chemins ou des composants dans un graphe en fonction de règles ou d'algorithmes de recherche spécifiques.

Comment ça fonctionne

1. Commencez à partir d'un sommet(nœud) spécifique dans le graphe.
2. Effectuez le processus de recherche en fonction de règles spécifiques, telles que la recherche en profondeur d'abord(DFS) ou la recherche en largeur d'abord(BFS).
3. Parcourez les sommets et les arêtes du graphique pour rechercher la cible ou les objets à trouver.
4. Enregistrez le chemin ou les résultats de la recherche.

Exemple

Considérez le graphique suivant:

A -- B -- C -- E  
|      |  
D --------  

Nous voulons trouver un chemin du sommet A au sommet E dans ce graphe en utilisant l'algorithme Depth-First Search(DFS).

1. Commencez au sommet A.
2. Déplacez-vous au sommet B.
3. Continuez jusqu'au sommet C.
4. Il n'y a pas de voisins en C, revenez au sommet B.
5. Déplacez-vous au sommet D.
6. Continuez jusqu'au sommet A(puisque D est connecté à A).
7. Déplacez-vous au sommet B.
8. Déplacez-vous au sommet C.
9. Déplacez-vous au sommet E.

Le chemin de A à E est A -> B -> C -> E.

Exemple de code en C++

#include <iostream>  
#include <vector>  
#include <stack>  
#include <unordered_map>  
  
class Graph {  
public:  
    void addEdge(char from, char to);  
    std::vector<char> depthFirstSearch(char start, char end);  
  
private:  
    std::unordered_map<char, std::vector<char>> adjList;  
};  
  
void Graph::addEdge(char from, char to) {  
    adjList[from].push_back(to);  
    adjList[to].push_back(from);  
}  
  
std::vector<char> Graph::depthFirstSearch(char start, char end) {  
    std::vector<char> path;  
    std::unordered_map<char, char> parent;  
    std::stack<char> stack;  
  
    stack.push(start);  
    parent[start] = '\0';  
  
    while(!stack.empty()) {  
        char current = stack.top();  
        stack.pop();  
  
        if(current == end) {  
            // Build the path from end to start using the parent map  
            char node = end;  
            while(node != '\0') {  
                path.insert(path.begin(), node);  
                node = parent[node];  
            }  
            break;  
        }  
  
        for(char neighbor: adjList[current]) {  
            if(parent.find(neighbor) == parent.end()) {  
                parent[neighbor] = current;  
                stack.push(neighbor);  
            }  
        }  
    }  
  
    return path;  
}  
  
int main() {  
    Graph graph;  
    graph.addEdge('A', 'B');  
    graph.addEdge('A', 'D');  
    graph.addEdge('B', 'C');  
    graph.addEdge('C', 'E');  
    graph.addEdge('D', 'B');  
  
    char start = 'A';  
    char end = 'E';  
  
    std::vector<char> path = graph.depthFirstSearch(start, end);  
  
    std::cout << "Path from " << start << " to " << end << ": ";  
    for(char node: path) {  
        std::cout << node << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Dans cet exemple, nous utilisons l'algorithme DFS pour trouver un chemin du sommet A au sommet E dans le graphe. Le résultat sera une séquence de sommets formant le chemin de A à E.