Graphsuchalgorithmus (Graph Search) in C++ – Erklärung, Beispiel und Code

Der Graph Search-Algorithmus ist eine grundlegende Technik im Bereich der Graphverarbeitung und des Informationsabrufs. Dieser Algorithmus ermöglicht es uns, Pfade oder Komponenten in einem Diagramm basierend auf bestimmten Regeln oder Suchalgorithmen zu finden.

Wie es funktioniert

1. Beginnen Sie an einem bestimmten Scheitelpunkt(Knoten) im Diagramm.
2. Führen Sie den Suchvorgang basierend auf bestimmten Regeln durch, z. B. der Tiefensuche(DFS) oder der Breitensuche(BFS).
3. Durchqueren Sie die Eckpunkte und Kanten des Diagramms, um nach dem Ziel oder den zu findenden Objekten zu suchen.
4. Notieren Sie den Pfad oder die Suchergebnisse.

Beispiel

Betrachten Sie die folgende Grafik:

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

Wir möchten in diesem Diagramm mithilfe des DFS-Algorithmus(Depth-First Search) einen Pfad vom Scheitelpunkt A zum Scheitelpunkt E finden.

1. Beginnen Sie am Scheitelpunkt A.
2. Gehen Sie zum Scheitelpunkt B.
3. Weiter zum Scheitelpunkt C.
4. Es gibt keine Nachbarn in C, zurück zum Scheitelpunkt B.
5. Gehen Sie zum Scheitelpunkt D.
6. Fahren Sie mit Scheitelpunkt A fort(da D mit A verbunden ist).
7. Gehen Sie zum Scheitelpunkt B.
8. Gehen Sie zum Scheitelpunkt C.
9. Gehen Sie zum Scheitelpunkt E.

Der Weg von A nach E ist A -> B -> C -> E.

Beispielcode 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 diesem Beispiel verwenden wir den DFS-Algorithmus, um einen Pfad vom Scheitelpunkt A zum Scheitelpunkt E im Diagramm zu finden. Das Ergebnis ist eine Folge von Eckpunkten, die den Pfad von A nach E bilden.