Bài toán đồ thị Peterson trong C

Giả sử có đồ thị như hình dưới. Đó là đồ thị Peterson. Các đỉnh được đánh số từ 0 đến 9. Mỗi đỉnh gán một chữ cái. Xét một đường đi W trên đồ thị, dùng L đỉnh. Chuỗi S độ dài L được thực hiện bởi W khi trình tự chữ cái trong W và S giống nhau. Có thể thăm đỉnh nhiều lần.

Ví dụ, chuỗi S = "ABBECCD" được thực hiện bởi đường đi (0, 1, 6, 9, 7, 2, 3). Nhiệm vụ: tìm đường đi như vậy, nếu có thì tìm đường đi nhỏ nhất về thứ tự từ điển. Nếu không có, trả về -1.

Thuật toán

petersonGraphWalk(S, v) -

bắt đầu
    res := đỉnh bắt đầu
    với mỗi ký tự c trong S trừ ký tự đầu, làm
        nếu có cạnh giữa v và c ở đồ thị ngoài, thì
            v := c
        khác nếu có cạnh giữa v và c+5 ở đồ thị trong, thì
            v := c + 5
        khác
            trả về false
        kết thúc nếu
        đưa v vào res
    xong
    trả về true
kết thúc

Ví dụ

#include <iostream>
using namespace std;

bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
    {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 1, 0, 0, 1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 1, 0, 0} };

char S[100005];
char res[100005];

bool petersonGraphWalk(char* S, int v){
    res[0] = v + '0';
    for(int i = 1; S[i]; i++){
        // duyệt đồ thị ngoài
        if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
            v = S[i] - 'A';
        }
        // kiểm tra đồ thị trong
        else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){
            v = S[i] - 'A' + 5;
        }else{
            return false;
        }
        res[i] = v + '0';
    }
    return true;
}

main() {
    char* str = "ABBECCD";
    if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){
        cout << res;
    }else{
        cout << -1;
    }
}

Kết quả

0169723