Algorithm ya Utafutaji wa Grafu (Graph Search) katika C++- Maelezo, Mfano na Msimbo

Kanuni ya Utafutaji wa Grafu ni mbinu ya kimsingi katika uga wa kuchakata grafu na urejeshaji wa taarifa. Kanuni hii hutuwezesha kupata njia au vijenzi kwenye grafu kulingana na sheria mahususi au kanuni za utafutaji.

Inavyofanya kazi

1. Anza kutoka kwa kipeo maalum(nodi) kwenye grafu.
2. Tekeleza mchakato wa utafutaji kwa kuzingatia sheria mahususi, kama vile Utafutaji wa Kina-Kwanza(DFS) au Utafutaji wa Upana-Kwanza(BFS).
3. Pitia wima na kingo za grafu ili kutafuta lengwa au vitu vya kupata.
4. Rekodi njia au matokeo ya utafutaji.

Mfano

Fikiria grafu ifuatayo:

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

Tunataka kutafuta njia kutoka kwa kipeo A hadi kipeo E katika grafu hii kwa kutumia algoriti ya Utafutaji wa Kina-Kwanza(DFS).

1. Anzia kwenye kipeo A.
2. Hamisha hadi kwenye kipeo B.
3. Endelea kwenye kipeo C.
4. Hakuna majirani katika C, nyuma ya vertex B.
5. Hamisha hadi kwenye kipeo D.
6. Endelea hadi kipeo A(kama D imeunganishwa na A).
7. Hamisha hadi kwenye kipeo B.
8. Hamisha hadi kwenye kipeo C.
9. Hamisha hadi kwenye kipeo E.

Njia kutoka A hadi E ni A -> B -> C -> E.

Msimbo wa Mfano katika 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;  
}  

Katika mfano huu, tunatumia algoriti ya DFS kutafuta njia kutoka kipeo A hadi kipeo E kwenye grafu. Matokeo yake yatakuwa mlolongo wa wima kutengeneza njia kutoka A hadi E.