Grafiko paieškos (Graph Search) algoritmas C++ kalboje – paaiškinimas, pavyzdys ir kodas

Grafų paieškos algoritmas yra pagrindinė technika grafikų apdorojimo ir informacijos gavimo srityje. Šis algoritmas leidžia grafike rasti kelius arba komponentus pagal konkrečias taisykles arba paieškos algoritmus.

Kaip tai veikia

1. Pradėkite nuo konkrečios viršūnės(mazgo) grafike.
2. Atlikite paieškos procesą remdamiesi konkrečiomis taisyklėmis, pvz., „Depth-First Search“(DFS) arba „Breadth-First Search“(BFS).
3. Pereikite per grafiko viršūnes ir briaunas, kad ieškotumėte taikinio ar objektų, kuriuos reikia rasti.
4. Įrašykite kelią arba paieškos rezultatus.

Pavyzdys

Apsvarstykite šią diagramą:

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

Šiame grafike norime rasti kelią nuo viršūnės A iki viršūnės E, naudodami algoritmą „Depth-First Search“(DFS).

1. Pradėkite nuo viršūnės A.
2. Perkelti į viršūnę B.
3. Toliau eikite į viršūnę C.
4. C kaimynų nėra, grįžkite į viršūnę B.
5. Perkelti į viršūnę D.
6. Toliau eikite į viršūnę A(kadangi D yra sujungta su A).
7. Perkelti į viršūnę B.
8. Perkelti į viršūnę C.
9. Perkelti į viršūnę E.

Kelias nuo A iki E yra A -> B -> C -> E.

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

Šiame pavyzdyje mes naudojame DFS algoritmą, kad surastume kelią nuo viršūnės A iki viršūnės E grafike. Rezultatas bus viršūnių seka, sudaranti kelią nuo A iki E.