Graafihakualgoritmi (Graph Search) C++:ssa- Selitys, esimerkki ja koodi

Graafihakualgoritmi on perustekniikka kuvaajien käsittelyssä ja tiedonhaussa. Tämän algoritmin avulla voimme löytää kaaviosta polkuja tai komponentteja tiettyjen sääntöjen tai hakualgoritmien perusteella.

Kuinka se toimii

1. Aloita graafin tietystä kärjestä(solmusta).
2. Suorita hakuprosessi tiettyjen sääntöjen perusteella, kuten Depth-First Search(DFS) tai Breadth-First Search(BFS).
3. Hae kohde tai löydettäviä objekteja kulkemalla kuvaajan kärkien ja reunojen läpi.
4. Tallenna polku tai hakutulokset.

Esimerkki

Harkitse seuraavaa kaaviota:

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

Haluamme löytää polun kärjestä A kärkeen E tästä kaaviosta käyttämällä Depth-First Search(DFS) -algoritmia.

1. Aloita kärjestä A.
2. Siirry kärkipisteeseen B.
3. Jatka kärkeen C.
4. C:ssä ei ole naapureita, palaa kärkeen B.
5. Siirrä kärkeen D.
6. Jatka kärkeen A(koska D on yhdistetty A:han).
7. Siirry kärkipisteeseen B.
8. Siirry kärkipisteeseen C.
9. Siirry kärkipisteeseen E.

Polku A:sta E:hen on A -> B -> C -> E.

Esimerkkikoodi C++:ssa

#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;  
}  

Tässä esimerkissä käytämme DFS-algoritmia löytääksemme polun pisteestä A kärkeen E graafista. Tuloksena on sarja pisteitä, jotka muodostavat polun A:sta E:hen.