خوارزمية بحث (Graph Search) الرسم البياني في C ++- شرح ومثال ورمز

تعد خوارزمية Graph Search تقنية أساسية في مجال معالجة الرسم البياني واسترجاع المعلومات. تمكننا هذه الخوارزمية من العثور على المسارات أو المكونات في الرسم البياني بناءً على قواعد محددة أو خوارزميات البحث.

كيف تعمل

1. ابدأ من قمة(عقدة) معينة في الرسم البياني.
2. قم بإجراء عملية البحث استنادًا إلى قواعد محددة ، مثل بحث العمق أولاً(DFS) أو بحث النطاق الأول(BFS).
3. اجتياز الرؤوس والحواف في الرسم البياني للبحث عن الهدف أو الكائنات التي تريد البحث عنها.
4. سجل المسار أو نتائج البحث.

مثال

انظر إلى الرسم البياني التالي:

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

نريد إيجاد مسار من الرأس A إلى الرأس E في هذا الرسم البياني باستخدام خوارزمية Depth-First Search(DFS).

1. ابدأ من قمة الرأس A.
2. الانتقال إلى الرأس B.
3. تابع إلى قمة الرأس C.
4. لا يوجد جيران في C ، تراجع إلى قمة الرأس B.
5. الانتقال إلى الرأس D.
6. استمر في الرأس A(حيث أن D متصل بـ A).
7. الانتقال إلى الرأس B.
8. الانتقال إلى الرأس C.
9. الانتقال إلى قمة الرأس E.

المسار من A إلى E هو A -> B -> C -> E.

رمز المثال في 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 لإيجاد مسار من الرأس A إلى الرأس E في الرسم البياني. ستكون النتيجة سلسلة من القمم التي تشكل المسار من A إلى E.