გრაფიკის ძიების (Graph Search) ალგორითმი C++ -ში- ახსნა, მაგალითი და კოდი

Graph Search ალგორითმი არის ფუნდამენტური ტექნიკა გრაფიკის დამუშავებისა და ინფორმაციის მოძიების სფეროში. ეს ალგორითმი საშუალებას გვაძლევს ვიპოვოთ ბილიკები ან კომპონენტები გრაფიკში კონკრეტული წესების ან საძიებო ალგორითმების საფუძველზე.

Როგორ მუშაობს

1. დაიწყეთ გრაფიკის კონკრეტული წვეროდან(კვანძიდან).
2. შეასრულეთ ძიების პროცესი კონკრეტული წესების საფუძველზე, როგორიცაა Depth-First Search(DFS) ან Breadth-First Search(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-მდე.