อัลกอริทึม การค้นหากราฟ (Graph Search) ใน C++- คำอธิบาย ตัวอย่าง และโค้ด

อัลกอริทึมการค้นหากราฟเป็นเทคนิคพื้นฐานในด้านการประมวลผลกราฟและการดึงข้อมูล อัลกอริทึมนี้ช่วยให้เราสามารถค้นหาเส้นทางหรือส่วนประกอบในกราฟตามกฎเฉพาะหรืออัลกอริทึมการค้นหา

มันทำงานอย่างไร

1. เริ่มต้นจากจุดยอดเฉพาะ(โหนด) ในกราฟ
2. ดำเนินการกระบวนการค้นหาตามกฎเฉพาะ เช่น การค้นหาความลึกก่อน(DFS) หรือการค้นหาครั้งแรกตามความกว้าง(BFS)
3. สำรวจจุดยอดและขอบของกราฟเพื่อค้นหาเป้าหมายหรือวัตถุที่ต้องการค้นหา
4. บันทึกเส้นทางหรือผลการค้นหา

ตัวอย่าง

พิจารณากราฟต่อไปนี้:

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

เราต้องการค้นหาเส้นทางจากจุดยอด A ไปยังจุดยอด E ในกราฟนี้โดยใช้อัลกอริทึมการค้นหาระยะแรก(DFS)

1. เริ่มต้นที่จุดยอด A
2. เลื่อนไปที่จุดยอด B
3. ดำเนินการต่อไปยังจุดยอด C
4. ไม่มีเพื่อนบ้านใน C ย้อนกลับไปที่จุดยอด B
5. เลื่อนไปที่จุดยอด D
6. ดำเนินการต่อไปยังจุดยอด A(เนื่องจาก D เชื่อมต่อกับ A)
7. เลื่อนไปที่จุดยอด B
8. เลื่อนไปที่จุดยอด C
9. เลื่อนไปที่จุดยอด E

เส้นทางจาก A ถึง E คือ A -> B -> C -> E

ตัวอย่างโค้ดในภาษา 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;  
}  

ในตัวอย่างนี้ เราใช้อัลกอริทึม DFS เพื่อค้นหาเส้นทางจากจุดยอด A ไปยังจุดยอด E ในกราฟ ผลลัพธ์จะเป็นลำดับของจุดยอดที่สร้างเส้นทางจาก A ถึง E