Tổng quan

Bài viết này trình bày về cách triển khai thuật toán Duyệt Đồ Thị theo Chiều Rộng (Breadth-First Search - BFS) trên cấu trúc dữ liệu đồ thị, sử dụng danh sách kề để lưu trữ đồ thị. Trọng tâm là việc áp dụng hàng đợi (queue) một cách chính xác trong quá trình duyệt.

Mô tả bài toán

Dựa trên cấu trúc lưu trữ danh sách kề, hãy hiện thực thuật toán duyệt đồ thị theo chiều rộng (BFS) và kiểm tra hoạt động của nó. Chú ý sử dụng cấu trúc dữ liệu hàng đợi (queue) một cách hiệu quả.

Định dạng đầu vào

• Dòng 1: Một số nguyên từ 0 đến 3 biểu thị loại đồ thị (0: đồ thị có hướng, 1: đồ thị có hướng có trọng số, 2: đồ thị vô hướng, 3: đồ thị vô hướng có trọng số).
• Dòng 2: Hai số nguyên lần lượt là số đỉnh (n) và số cạnh (m) của đồ thị.
• Dòng 3: Các giá trị của n đỉnh (kiểu ký tự, độ dài tối đa 3 ký tự), cách nhau bởi dấu cách. Quá trình duyệt sẽ bắt đầu từ đỉnh đầu tiên được nhập.
• Dòng 4 trở đi: Mỗi dòng mô tả một cung (cạnh). Với đồ thị không trọng số, nhập đỉnh gốc và đỉnh đích (cách nhau bằng dấu cách). Với đồ thị có trọng số, nhập trọng số, sau đó là đỉnh gốc và đỉnh đích (cách nhau bằng dấu cách).

Định dạng đầu ra

• In ra kết quả duyệt đồ thị theo chiều rộng, các đỉnh cách nhau bởi dấu cách.

Ví dụ

Đầu vào mẫu:

0
3 3
a b c
a b
b c
c b

Đầu ra mẫu:

a b c

Triển khai thuật toán BFS

Để triển khai BFS, chúng ta cần:

1. Một cách để ánh xạ tên đỉnh (chuỗi ký tự) sang chỉ số số nguyên để dễ dàng làm việc với các mảng (ví dụ: mảng visited, danh sách kề).
2. Một danh sách kề để lưu trữ các cạnh của đồ thị.
3. Một mảng hoặc vector để đánh dấu các đỉnh đã được thăm.
4. Một hàng đợi (queue) để quản lý các đỉnh cần thăm theo thứ tự chiều rộng.

Trong ví dụ dưới đây, chúng tôi sử dụng std::map<std::string, int> để ánh xạ tên đỉnh sang chỉ số, và std::vector<std::string> để ánh xạ ngược từ chỉ số sang tên đỉnh. Danh sách kề được biểu diễn bằng std::vector<std::vector<int>>, và trạng thái thăm được quản lý bởi std::vector<bool>.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set> // Để đảm bảo các đỉnh được duyệt theo thứ tự ổn định trong danh sách kề

// Hàm BFS để duyệt đồ thị
void bfsGraph(int startIndex, 
              const std::vector<std::vector<int>>& adjacencyList, 
              const std::vector<std::string>& idToVertexName) {
    
    int numVertices = adjacencyList.size();
    std::vector<bool> visited(numVertices, false);
    std::queue<int> bfsQueue;

    // Bắt đầu duyệt từ đỉnh startIndex
    bfsQueue.push(startIndex);
    visited[startIndex] = true;

    while (!bfsQueue.empty()) {
        int currentVertexId = bfsQueue.front();
        bfsQueue.pop();

        // In tên đỉnh đã duyệt
        std::cout << idToVertexName[currentVertexId] << " ";

        // Duyệt qua tất cả các đỉnh kề của đỉnh hiện tại
        // Sắp xếp các đỉnh kề để đảm bảo thứ tự đầu ra giống ví dụ nếu có nhiều lựa chọn
        std::set<int> sortedNeighbors;
        for (int neighborId : adjacencyList[currentVertexId]) {
            sortedNeighbors.insert(neighborId);
        }

        for (int neighborId : sortedNeighbors) {
            if (!visited[neighborId]) {
                visited[neighborId] = true;
                bfsQueue.push(neighborId);
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int graphType;
    std::cin >> graphType;

    int numVertices, numEdges;
    std::cin >> numVertices >> numEdges;

    std::map<std::string, int> vertexNameToId;
    std::vector<std::string> idToVertexName(numVertices);
    int vertexCounter = 0;
    int firstVertexId = -1; // Id của đỉnh bắt đầu duyệt

    // Đọc tên các đỉnh và ánh xạ chúng sang ID
    for (int i = 0; i < numVertices; ++i) {
        std::string vertexName;
        std::cin >> vertexName;
        if (i == 0) { // Đỉnh đầu tiên là đỉnh bắt đầu
            firstVertexId = vertexCounter;
        }
        vertexNameToId[vertexName] = vertexCounter;
        idToVertexName[vertexCounter] = vertexName;
        vertexCounter++;
    }

    std::vector<std::vector<int>> adjacencyList(numVertices);

    // Đọc các cạnh và xây dựng danh sách kề
    for (int i = 0; i < numEdges; ++i) {
        std::string sourceName, destName;
        int weight = 0; // Trọng số không ảnh hưởng đến BFS cơ bản

        if (graphType == 1 || graphType == 3) { // Đồ thị có trọng số
            std::cin >> weight >> sourceName >> destName;
        } else { // Đồ thị không trọng số
            std::cin >> sourceName >> destName;
        }

        int sourceId = vertexNameToId[sourceName];
        int destId = vertexNameToId[destName];

        adjacencyList[sourceId].push_back(destId);

        if (graphType == 2 || graphType == 3) { // Đồ thị vô hướng, thêm cạnh ngược lại
            adjacencyList[destId].push_back(sourceId);
        }
    }

    // Gọi hàm BFS
    if (firstVertexId != -1) {
        bfsGraph(firstVertexId, adjacencyList, idToVertexName);
    }

    return 0;
}