close

Αλγόριθμος αναζήτησης γραφήματος (Graph Search) σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο αλγόριθμος αναζήτησης γραφήματος είναι μια θεμελιώδης τεχνική στον τομέα της επεξεργασίας γραφημάτων και της ανάκτησης πληροφοριών. Αυτός ο αλγόριθμος μας δίνει τη δυνατότητα να βρούμε μονοπάτια ή στοιχεία σε ένα γράφημα με βάση συγκεκριμένους κανόνες ή αλγόριθμους αναζήτησης.

Πως δουλεύει

  1. Ξεκινήστε από μια συγκεκριμένη κορυφή(κόμβο) στο γράφημα.
  2. Εκτελέστε τη διαδικασία αναζήτησης με βάση συγκεκριμένους κανόνες, όπως η αναζήτηση σε πρώτο πλάτος(DFS) ή αναζήτηση σε πρώτο πλάτος(BFS).
  3. Διασχίστε τις κορυφές και τις άκρες του γραφήματος για να αναζητήσετε τον στόχο ή τα αντικείμενα προς εύρεση.
  4. Καταγράψτε τη διαδρομή ή τα αποτελέσματα αναζήτησης.

Παράδειγμα

Σκεφτείτε το παρακάτω γράφημα:

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

Θέλουμε να βρούμε μια διαδρομή από την κορυφή Α στην κορυφή Ε σε αυτό το γράφημα χρησιμοποιώντας τον αλγόριθμο αναζήτησης βάθους-πρώτης(DFS).

  1. Ξεκινήστε από την κορυφή Α.
  2. Μετακίνηση στην κορυφή Β.
  3. Συνεχίστε στην κορυφή C.
  4. Δεν υπάρχουν γείτονες στο C, πίσω στην κορυφή Β.
  5. Μετακίνηση στην κορυφή Δ.
  6. Συνεχίστε στην κορυφή Α(καθώς το D συνδέεται με το Α).
  7. Μετακίνηση στην κορυφή Β.
  8. Μετακίνηση στην κορυφή Γ.
  9. Μετακίνηση στην κορυφή Ε.

Η διαδρομή από το Α στο Ε είναι Α -> Β -> Γ -> Ε.

Παράδειγμα κώδικα σε 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;  
}

Σε αυτό το παράδειγμα, χρησιμοποιούμε τον αλγόριθμο DFS για να βρούμε μια διαδρομή από την κορυφή Α στην κορυφή Ε στο γράφημα. Το αποτέλεσμα θα είναι μια ακολουθία κορυφών που σχηματίζουν τη διαδρομή από το Α στο Ε.