Algoritma Pencarian Grafik (Graph Search) di C++- Penjelasan, Contoh dan Kode

Algoritma Pencarian Grafik adalah teknik mendasar di bidang pemrosesan grafik dan pencarian informasi. Algoritma ini memungkinkan kita untuk menemukan jalur atau komponen dalam grafik berdasarkan aturan tertentu atau algoritma pencarian.

Bagaimana itu bekerja

1. Mulai dari simpul(simpul) tertentu dalam graf.
2. Lakukan proses pencarian berdasarkan aturan tertentu, seperti Depth-First Search(DFS) atau Breadth-First Search(BFS).
3. Lintasi simpul dan tepi grafik untuk mencari target atau objek yang akan ditemukan.
4. Rekam jalur atau hasil pencarian.

Contoh

Perhatikan grafik berikut:

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

Kami ingin menemukan jalur dari simpul A ke simpul E dalam graf ini menggunakan algoritma Depth-First Search(DFS).

1. Mulai dari simpul A.
2. Pindah ke simpul B.
3. Lanjutkan ke simpul C.
4. Tidak ada tetangga di C, mundur ke simpul B.
5. Pindah ke simpul D.
6. Lanjutkan ke simpul A(karena D terhubung ke A).
7. Pindah ke simpul B.
8. Pindah ke simpul C.
9. Pindah ke simpul E.

Lintasan dari A ke E adalah A -> B -> C -> E.

Contoh Kode di 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;  
}  

Dalam contoh ini, kami menggunakan algoritma DFS untuk menemukan jalur dari simpul A ke simpul E di graf. Hasilnya akan menjadi urutan simpul yang membentuk jalur dari A ke E.