Algoritmi i Kërkimit të Grafikut (Graph Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi i Kërkimit të Grafikut është një teknikë themelore në fushën e përpunimit të grafikëve dhe marrjes së informacionit. Ky algoritëm na mundëson të gjejmë shtigje ose komponentë në një grafik bazuar në rregulla specifike ose algoritme kërkimi.

Si punon

1. Filloni nga një kulm(nyje) specifike në grafik.
2. Kryeni procesin e kërkimit bazuar në rregulla specifike, të tilla si Kërkimi në Thellësi-First(DFS) ose Breadth-First Search(BFS).
3. Kaloni kulmet dhe skajet e grafikut për të kërkuar objektivin ose objektet për të gjetur.
4. Regjistroni shtegun ose rezultatet e kërkimit.

Shembull

Merrni parasysh grafikun e mëposhtëm:

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

Ne duam të gjejmë një shteg nga kulmi A në kulmin E në këtë grafik duke përdorur algoritmin Depth-First Search(DFS).

1. Filloni në kulmin A.
2. Kaloni në kulmin B.
3. Vazhdoni te kulmi C.
4. Nuk ka fqinjë në C, prapa te kulmi B.
5. Kaloni në kulmin D.
6. Vazhdoni në kulmin A(pasi D është i lidhur me A).
7. Kaloni në kulmin B.
8. Kaloni në kulmin C.
9. Kaloni në kulmin E.

Rruga nga A në E është A -> B -> C -> E.

Shembull Kodi në 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;  
}  

Në këtë shembull, ne përdorim algoritmin DFS për të gjetur një shteg nga kulmi A në kulmin E në grafik. Rezultati do të jetë një sekuencë kulmesh që formojnë shtegun nga A në E.