Algoritma Panelusuran Grafik (Graph Search) ing C++- Panjelasan, Tuladha lan Kode

Algoritma Panelusuran Grafik minangka teknik dhasar ing bidang pangolahan grafik lan pengambilan informasi. Algoritma iki ngidini kita nemokake dalan utawa komponen ing grafik adhedhasar aturan tartamtu utawa algoritma telusuran.

Cara Kerjane

1. Miwiti saka titik tartamtu(simpul) ing grafik.
2. Nindakake proses panelusuran adhedhasar aturan tartamtu, kayata Depth-First Search(DFS) utawa Breadth-First Search(BFS).
3. Telusuri verteks lan pinggiran grafik kanggo nggoleki target utawa obyek sing bakal ditemokake.
4. Rekam path utawa asil panelusuran.

Tuladha

Coba grafik ing ngisor iki:

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

Kita pengin nemokake path saka vertex A menyang vertex E ing grafik iki nggunakake algoritma Depth-First Search(DFS).

1. Mulai ing vertex A.
2. Pindhah menyang puncak B.
3. Terus menyang puncak C.
4. Ora ana tanggi ing C, mundur menyang vertex B.
5. Pindhah menyang puncak D.
6. Terus menyang vertex A(minangka D disambungake menyang A).
7. Pindhah menyang puncak B.
8. Pindhah menyang puncak C.
9. Pindhah menyang puncak E.

Path saka A menyang E yaiku A -> B -> C -> E.

Tuladha Kode ing 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;  
}  

Ing conto iki, kita nggunakake algoritma DFS kanggo nemokake path saka vertex A kanggo vertex E ing grafik. Asilé bakal dadi urutan vertex sing mbentuk path saka A nganti E.