Chương trình C++ triển khai Graph Structured Stack

Graph Structured Stack (GSS) là cấu trúc dữ liệu dùng trong phân tích cú pháp (parsing) như thuật toán Tomita cho ngữ pháp không xác định. GSS gom nhiều stack chia sẻ các đoạn chung (shared prefixes) thành một đồ thị có hướng.

Chương trình dưới minh họa GSS đơn giản: tìm tất cả đường đi từ đỉnh nguồn s đến đỉnh đích bNode trong đồ thị có hướng, mỗi đường đi lưu dưới dạng một stack.

Thuật toán chính

1. DFS từ đỉnh nguồn, dùng stack mystack theo dõi đường đi hiện tại.
2. Khi gặp đỉnh đích, copy đường đi hiện tại vào một stack mới istack và lưu vào stackList.
3. Backtrack bằng cách pop mystack, tiếp tục tìm đường đi khác.
4. Cuối cùng in tất cả stack trong stackList.

Ví dụ mã (đơn giản hóa, có chú thích)

#include <iostream>
#include <cstdlib>
#include <stack>
#include <list>
#include <vector>
using namespace std;

class GraphStructuredStack {
    int n;
    vector<vector<int>> adj;
    vector<int> parent;
    list<stack<int>> stackList;
    stack<int> mystack;

public:
    GraphStructuredStack(int nodes) : n(nodes), adj(nodes + 1), parent(nodes + 1) {}

    void addEdge(int u, int v) { adj[u].push_back(v); }

    void findPaths(int s, int target) {
        vector<bool> visited(n + 1, false);
        mystack.push(s);
        parent[s] = -1;

        while (!mystack.empty()) {
            int u = mystack.top();
            bool foundNext = false;

            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    mystack.push(v);
                    foundNext = true;
                    break;
                }
            }

            if (!foundNext) {
                if (u == target) {
                    // Tìm thấy đường đi, lưu vào stackList
                    stack<int> path;
                    for (int x = u; x != -1; x = parent[x])
                        path.push(x);
                    stackList.push_back(path);
                }
                mystack.pop();
            }
        }

        // In tất cả đường đi
        for (auto &st : stackList) {
            while (!st.empty()) {
                cout << st.top() << '\t';
                st.pop();
            }
            cout << endl;
        }
    }
};

int main() {
    int nodes;
    cout << "Số đỉnh: "; cin >> nodes;
    GraphStructuredStack gss(nodes);

    cout << "Ma trận kề (" << nodes << "x" << nodes << "):\n";
    for (int i = 1; i <= nodes; ++i)
        for (int j = 1; j <= nodes; ++j) {
            int x; cin >> x;
            if (x) gss.addEdge(i, j);
        }

    int src, dst;
    cout << "Đỉnh nguồn: "; cin >> src;
    cout << "Đỉnh đích: "; cin >> dst;

    cout << "Các đường đi (stack):\n";
    gss.findPaths(src, dst);
    return 0;
}

Kết quả mẫu

Số đỉnh: 4
Ma trận kề:
1 1 1 0
0 1 1 0
1 0 0 0
1 1 1 1
Đỉnh nguồn: 3
Đỉnh đích: 1
Các đường đi (stack):
3	1