C++ இல் வரைபடத் தேடல் (Graph Search) அல்காரிதம்- விளக்கம், எடுத்துக்காட்டு மற்றும் குறியீடு

வரைபட தேடல் அல்காரிதம் என்பது வரைபட செயலாக்கம் மற்றும் தகவல் மீட்டெடுப்பு துறையில் ஒரு அடிப்படை நுட்பமாகும். குறிப்பிட்ட விதிகள் அல்லது தேடல் அல்காரிதம்களின் அடிப்படையில் வரைபடத்தில் பாதைகள் அல்லது கூறுகளைக் கண்டறிய இந்த அல்காரிதம் நமக்கு உதவுகிறது.

எப்படி இது செயல்படுகிறது

1. வரைபடத்தில் ஒரு குறிப்பிட்ட முனையிலிருந்து(முனை) தொடங்கவும்.
2. ஆழம்-முதல் தேடல்(DFS) அல்லது அகலம்-முதல் தேடல்(BFS) போன்ற குறிப்பிட்ட விதிகளின் அடிப்படையில் தேடல் செயல்முறையைச் செய்யவும்.
3. இலக்கு அல்லது பொருள்களைத் தேட வரைபடத்தின் முனைகளையும் விளிம்புகளையும் கடந்து செல்லவும்.
4. பாதை அல்லது தேடல் முடிவுகளை பதிவு செய்யவும்.

உதாரணமாக

பின்வரும் வரைபடத்தைக் கவனியுங்கள்:

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

ஆழம்-முதல் தேடல்(DFS) வழிமுறையைப் பயன்படுத்தி இந்த வரைபடத்தில் உச்சி A இலிருந்து முனை E வரையிலான பாதையைக் கண்டறிய விரும்புகிறோம்.

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;  
}  

இந்த எடுத்துக்காட்டில், வரைபடத்தில் உச்சி A இலிருந்து உச்சி E வரையிலான பாதையைக் கண்டறிய DFS அல்காரிதத்தைப் பயன்படுத்துகிறோம். இதன் விளைவாக A இலிருந்து E வரையிலான பாதையை உருவாக்கும் செங்குத்துகளின் வரிசை இருக்கும்.