Algoritmo de búsqueda de gráficos (Graph Search) en C++- Explicación, ejemplo y código

El algoritmo Graph Search es una técnica fundamental en el campo del procesamiento de gráficos y la recuperación de información. Este algoritmo nos permite encontrar rutas o componentes en un gráfico en función de reglas específicas o algoritmos de búsqueda.

Cómo funciona

1. Comience desde un vértice específico(nodo) en el gráfico.
2. Realice el proceso de búsqueda según reglas específicas, como la búsqueda primero en profundidad(DFS) o la búsqueda primero en amplitud(BFS).
3. Atraviese los vértices y los bordes del gráfico para buscar el objetivo o los objetos que desea encontrar.
4. Registre la ruta o los resultados de la búsqueda.

Ejemplo

Considere el siguiente gráfico:

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

Queremos encontrar una ruta desde el vértice A al vértice E en este gráfico utilizando el algoritmo de búsqueda primero en profundidad(DFS).

1. Comienza en el vértice A.
2. Mover al vértice B.
3. Continúe hasta el vértice C.
4. No hay vecinos en C, retrocede hasta el vértice B.
5. Mover al vértice D.
6. Continúe hasta el vértice A(ya que D está conectado a A).
7. Mover al vértice B.
8. Mover al vértice C.
9. Mover al vértice E.

El camino de A a E es A -> B -> C -> E.

Código de ejemplo 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;  
}  

En este ejemplo, usamos el algoritmo DFS para encontrar una ruta desde el vértice A hasta el vértice E en el gráfico. El resultado será una secuencia de vértices que forman el camino de A a E.