Algoritmo di ricerca su grafi (Graph Search) in C++- Spiegazione, esempio e codice

L'algoritmo di Graph Search è una tecnica fondamentale nel campo dell'elaborazione dei grafici e del recupero delle informazioni. Questo algoritmo ci consente di trovare percorsi o componenti in un grafico in base a regole o algoritmi di ricerca specifici.

Come funziona

1. Inizia da un vertice specifico(nodo) nel grafico.
2. Eseguire il processo di ricerca in base a regole specifiche, come Depth-First Search(DFS) o Breadth-First Search(BFS).
3. Attraversa i vertici e i bordi del grafico per cercare il bersaglio o gli oggetti da trovare.
4. Registra il percorso o i risultati della ricerca.

Esempio

Considera il seguente grafico:

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

Vogliamo trovare un percorso dal vertice A al vertice E in questo grafico utilizzando l'algoritmo Depth-First Search(DFS).

1. Inizia dal vertice A.
2. Passa al vertice B.
3. Continua fino al vertice C.
4. Non ci sono vicini in C, torna al vertice B.
5. Passa al vertice D.
6. Continua fino al vertice A(poiché D è connesso ad A).
7. Passa al vertice B.
8. Passa al vertice C.
9. Passa al vertice E.

Il percorso da A a E è A -> B -> C -> E.

Esempio di codice in 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;  
}  

In questo esempio, utilizziamo l'algoritmo DFS per trovare un percorso dal vertice A al vertice E nel grafico. Il risultato sarà una sequenza di vertici che formano il percorso da A a E.