(Graph Search) C++ میں گراف سرچ الگورتھم- وضاحت، مثال اور کوڈ

گراف سرچ الگورتھم گراف پروسیسنگ اور معلومات کی بازیافت کے میدان میں ایک بنیادی تکنیک ہے۔ یہ الگورتھم ہمیں مخصوص قواعد یا تلاش کے الگورتھم کی بنیاد پر گراف میں راستے یا اجزاء تلاش کرنے کے قابل بناتا ہے۔

یہ کیسے کام کرتا ہے

1. گراف میں ایک مخصوص ورٹیکس(نوڈ) سے شروع کریں۔
2. تلاش کے عمل کو مخصوص اصولوں کی بنیاد پر انجام دیں، جیسے Depth-First Search(DFS) یا Breadth-First Search(BFS)۔
3. ہدف یا اشیاء کو تلاش کرنے کے لیے گراف کے عمودی اور کناروں کو عبور کریں۔
4. راستے یا تلاش کے نتائج کو ریکارڈ کریں۔

مثال

مندرجہ ذیل گراف پر غور کریں:

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

ہم Depth-First Search(DFS) الگورتھم کا استعمال کرتے ہوئے اس گراف میں vertex A سے vertex E تک کا راستہ تلاش کرنا چاہتے ہیں۔

1. عمودی A سے شروع کریں۔
2. عمودی B پر جائیں۔
3. عمودی C تک جاری رکھیں۔
4. C میں کوئی پڑوسی نہیں ہے، پیچھے کی طرف vertex 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;  
}  

اس مثال میں، ہم گراف میں vertex A سے vertex E تک راستہ تلاش کرنے کے لیے DFS الگورتھم کا استعمال کرتے ہیں۔ نتیجہ A سے E تک کا راستہ بنانے والی چوٹیوں کا ایک سلسلہ ہوگا۔