Grafiekzoekalgoritme (Graph Search) in C ++- uitleg, voorbeeld en code

Het Graph Search-algoritme is een fundamentele techniek op het gebied van grafische verwerking en het ophalen van informatie. Dit algoritme stelt ons in staat om paden of componenten in een grafiek te vinden op basis van specifieke regels of zoekalgoritmen.

Hoe het werkt

1. Begin vanaf een specifiek hoekpunt(knooppunt) in de grafiek.
2. Voer het zoekproces uit op basis van specifieke regels, zoals Depth-First Search(DFS) of Breadth-First Search(BFS).
3. Doorkruis de hoekpunten en randen van de grafiek om te zoeken naar het doel of de te vinden objecten.
4. Noteer het pad of de zoekresultaten.

Voorbeeld

Beschouw de volgende grafiek:

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

We willen een pad vinden van hoekpunt A naar hoekpunt E in deze grafiek met behulp van het algoritme Depth-First Search(DFS).

1. Begin bij hoekpunt A.
2. Ga naar hoekpunt B.
3. Ga verder naar hoekpunt C.
4. Er zijn geen buren in C, terug naar hoekpunt B.
5. Ga naar hoekpunt D.
6. Ga verder naar hoekpunt A(aangezien D is verbonden met A).
7. Ga naar hoekpunt B.
8. Ga naar hoekpunt C.
9. Ga naar hoekpunt E.

Het pad van A naar E is A -> B -> C -> E.

Voorbeeldcode 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 dit voorbeeld gebruiken we het DFS-algoritme om een ​​pad te vinden van hoekpunt A naar hoekpunt E in de grafiek. Het resultaat is een reeks hoekpunten die het pad van A naar E vormen.