Algoritma Carian Graf (Graph Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma Carian Graf ialah teknik asas dalam bidang pemprosesan graf dan mendapatkan maklumat. Algoritma ini membolehkan kami mencari laluan atau komponen dalam graf berdasarkan peraturan tertentu atau algoritma carian.

Bagaimana ia berfungsi

1. Mulakan dari puncak tertentu(nod) dalam graf.
2. Laksanakan proses carian berdasarkan peraturan tertentu, seperti Depth-First Search(DFS) atau Breadth-First Search(BFS).
3. Lintas bucu dan tepi graf untuk mencari sasaran atau objek untuk dicari.
4. Rakam laluan atau hasil carian.

Contoh

Pertimbangkan graf berikut:

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

Kami ingin mencari laluan dari bucu A ke bucu E dalam graf ini menggunakan algoritma Depth-First Search(DFS).

1. Mulakan di puncak A.
2. Bergerak ke puncak B.
3. Teruskan ke puncak C.
4. Tiada jiran di C, undur ke puncak B.
5. Bergerak ke puncak D.
6. Teruskan ke bucu A(kerana D disambungkan ke A).
7. Bergerak ke puncak B.
8. Bergerak ke puncak C.
9. Beralih ke puncak E.

Laluan dari A ke E ialah A -> B -> C -> E.

Contoh Kod dalam 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 mencari laluan dari bucu A ke bucu E dalam graf. Hasilnya ialah urutan bucu yang membentuk laluan dari A ke E.