Algoritm de căutare grafică (Graph Search) în C++- Explicație, Exemplu și Cod

Algoritmul Graph Search este o tehnică fundamentală în domeniul prelucrării graficelor și regăsării informațiilor. Acest algoritm ne permite să găsim căi sau componente într-un grafic pe baza unor reguli specifice sau algoritmi de căutare.

Cum functioneaza

1. Începeți de la un anumit nod(nod) din grafic.
2. Efectuați procesul de căutare pe baza unor reguli specifice, cum ar fi Depth-First Search(DFS) sau Breadth-First Search(BFS).
3. Traversați vârfurile și marginile graficului pentru a căuta ținta sau obiectele de găsit.
4. Înregistrați calea sau rezultatele căutării.

Exemplu

Luați în considerare următorul grafic:

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

Vrem să găsim o cale de la vârful A la vârful E în acest grafic folosind algoritmul Depth-First Search(DFS).

1. Începeți de la vârful A.
2. Deplasați-vă la vârful B.
3. Continuați până la vârful C.
4. Nu există vecini în C, înapoi la vârful B.
5. Mutați la vârful D.
6. Continuați până la vârful A(deoarece D este conectat la A).
7. Deplasați-vă la vârful B.
8. Mutați la vârful C.
9. Deplasați-vă la vârful E.

Calea de la A la E este A -> B -> C -> E.

Exemplu de cod în 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;  
}  

În acest exemplu, folosim algoritmul DFS pentru a găsi o cale de la vârful A la vârful E în grafic. Rezultatul va fi o succesiune de vârfuri care formează calea de la A la E.