Algartam Cuardach Grafa (Graph Search) i C++- Míniú, Sampla agus Cód

Is teicníocht bhunúsach é an t-algartam Cuardaigh Grafa i réimse na próiseála graif agus aisghabhála faisnéise. Cuireann an algartam seo ar ár gcumas cosáin nó comhpháirteanna a aimsiú i ngraf bunaithe ar rialacha sonracha nó halgartaim chuardaigh.

Conas a oibríonn sé

1. Tosaigh ó rinn(nód) ar leith sa ghraf.
2. Déan an próiseas cuardaigh bunaithe ar rialacha sonracha, ar nós Cuardach Doimhneachta an Chéad Uair(DFS) nó Cuardach Leathan Chéad(BFS).
3. Trasnaigh rinn agus imill an ghraif chun an sprioc nó na réada a lorg.
4. Taifead an cosán nó torthaí cuardaigh.

Sampla

Smaoinigh ar an ngraf seo a leanas:

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

Teastaíonn uainn conair a aimsiú ó rinn A go rinn E sa ghraf seo agus úsáid á baint as an algartam Doimhneacht-First Search(DFS).

1. Tosaigh ag rinn A.
2. Bog go rinn B.
3. Lean ar aghaidh go rinn C.
4. Níl aon chomharsana i C, cúlrian go rinn B.
5. Bog go rinn D.
6. Lean ar aghaidh go rinn A(mar tá D ceangailte le A).
7. Bog go rinn B.
8. Bog go rinn C.
9. Bog go rinn E.

Is é an cosán ó A go E ná A -> B -> C -> E.

Cód Samplach i 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;  
}  

Sa sampla seo, bainimid úsáid as an algartam DFS chun conair a aimsiú ó rinn A go rinn E sa ghraf. Is é an toradh a bheidh air ná seicheamh rinn a fhoirmíonn an cosán ó A go E.