close

Algoritmu tat- Tiftix tal-Grafika (Graph Search) f'C++- Spjegazzjoni, Eżempju u Kodiċi

L-algoritmu tat-Tiftix tal-Graff huwa teknika fundamentali fil-qasam tal-ipproċessar tal-graff u l-irkupru tal-informazzjoni. Dan l-algoritmu jippermettilna nsibu mogħdijiet jew komponenti f'graff ibbażat fuq regoli speċifiċi jew algoritmi ta' tfittxija.

Kif taħdem

  1. Ibda minn vertiċi(node) speċifiku fil-graff.
  2. Wettaq il-proċess ta 'tfittxija abbażi ta' regoli speċifiċi, bħal Depth-First Search(DFS) jew Breadth-First Search(BFS).
  3. Aqsa 'l-vertiċi u t-truf tal-graff biex tfittex il-mira jew l-oġġetti li ssib.
  4. Irreġistra t-triq jew ir-riżultati tat-tfittxija.

Eżempju

Ikkunsidra l-graff li ġej:

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

Irridu nsibu mogħdija minn vertiċi A għal vertiċi E f'dan il-graff billi tuża l-algoritmu Depth-First Search(DFS).

  1. Ibda fil-vertiċi A.
  2. Imxi lejn il-vertiċi B.
  3. Kompli sal-vertiċi C.
  4. M'hemm l-ebda ġirien f'Ċ, lura għall-vertiċi B.
  5. Imxi lejn il-vertiċi D.
  6. Kompli sal-vertiċi A(kif D huwa konness ma' A).
  7. Imxi lejn il-vertiċi B.
  8. Imxi lejn il-vertiċi C.
  9. Imxi lejn il-vertiċi E.

Il-mogħdija minn A sa E hija A -> B -> C -> E.

Eżempju Kodiċi f'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;  
}

F'dan l-eżempju, nużaw l-algoritmu DFS biex insibu mogħdija minn vertiċi A għal vertiċi E fil-graff. Ir-riżultat se jkun sekwenza ta’ vertiċi li jiffurmaw il-mogħdija minn A sa E.