close

Giải thuật Tìm kiếm Đồ thị (Graph Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Thuật toán Tìm kiếm theo Đồ thị là một phương pháp quan trọng trong lĩnh vực xử lý đồ thị và tìm kiếm thông tin. Thuật toán này cho phép chúng ta tìm kiếm đường đi hoặc các thành phần trong một đồ thị dựa trên các quy tắc hoặc thuật toán tìm kiếm cụ thể.

Cách hoạt động

  1. Bắt đầu từ một đỉnh (node) cụ thể trong đồ thị.
  2. Thực hiện quá trình tìm kiếm dựa trên các quy tắc cụ thể, chẳng hạn như DFS (Dưới trước trọng số) hoặc BFS (Dưới trước trọng số).
  3. Duyệt qua các đỉnh và cạnh của đồ thị để tìm kiếm đích hoặc các đối tượng cần tìm.
  4. Ghi nhận đường đi hoặc kết quả tìm kiếm.

Ví dụ

Xem xét đồ thị sau:

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

Chúng ta muốn tìm kiếm đường đi từ đỉnh A đến đỉnh E trong đồ thị này bằng phương pháp DFS (Dưới trước trọng số).

  1. Bắt đầu tại đỉnh A.
  2. Di chuyển đến đỉnh B.
  3. Tiếp tục di chuyển đến đỉnh C.
  4. Không có đỉnh kề nào trong C cả, quay lại đỉnh B.
  5. Di chuyển đến đỉnh D.
  6. Tiếp tục di chuyển đến đỉnh A (do D kề A).
  7. Di chuyển đến đỉnh B.
  8. Di chuyển đến đỉnh C.
  9. Di chuyển đến đỉnh E.

Đường đi từ A đến E là A -> B -> C -> E.

Ví dụ mã nguồn trong 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;
}

Trong ví dụ này, chúng ta sử dụng thuật toán DFS để tìm đường đi từ đỉnh A đến đỉnh E trong đồ thị. Kết quả sẽ là một dãy các đỉnh tạo thành đường đi từ A đến E.