C++로 구현하는 그래프 구조 스택(Graph Structured Stack)

이 글에서는 C++를 이용해 그래프 구조 스택(Graph Structured Stack)을 구현하는 방법을 소개합니다. 그래프 구조 스택은 여러 개의 분기 경로가 존재하거나 서로 다른 경로가 한 노드로 합쳐질 수 있도록 일반 스택을 확장한 자료구조로, GLR 파싱 등 컴파일러 이론과 자연어 처리 분야에서 널리 활용됩니다.

그래프 구조 스택의 동작 원리

주어진 그래프를 인접 행렬로 표현한 뒤, 시작 노드(source)에서 깊이 우선 탐색과 유사한 방식으로 탐색을 진행합니다. 각 노드를 방문할 때마다 스택에 push하고, 부모 노드 정보를 별도의 배열(par)에 기록합니다. 목표로 하는 바닥 노드(bottom node)에 도달하면 부모 배열을 거슬러 올라가 시작 노드까지의 경로를 하나의 스택으로 저장합니다. 이 과정을 더 이상 탐색할 경로가 없을 때까지 반복하면, 여러 개의 스택이 리스트 형태로 관리되는 그래프 구조 스택이 완성됩니다.

알고리즘

시작
    함수 graphStructuredStack(int **adjMat, int s, int bNode):
        매개변수: 인접 행렬 adjMat, 시작 노드 s, 바닥 노드 bNode
        stackFound = false 로 초기화
        sVertex = 1 부터 noOfNodes 까지 반복
            dVertex = 1 부터 noOfNodes 까지 반복
                this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex]
            내부 반복 종료
        외부 반복 종료
        시작 노드 s 를 mystack 에 push
        while (!mystack.empty())
            element = mystack.top()
            도착 노드 변수 d = 1 로 초기화
            while (d <= noOfNodes)
                만약 (this->adjMat[element][d] == 1) 이라면
                    도착 노드 d 를 mystack 에 push
                    par[d] = element
                    this->adjMat[element][d] = 0
                    만약 (d == bNode) 라면
                        stackFound = true 로 설정하고 반복 탈출
                    조건문 종료
                element = d
                d = 1
                continue
                조건문 종료
                d 를 1 증가
            내부 반복 종료
            만약 (stackFound) 라면
                node = bNode 부터 node != s 인 동안 부모 포인터를 따라가며
                    node 를 istack 에 push
                s 를 istack 에 push
                stackList.push_back(istack)
                stackFound = false 로 갱신
            조건문 종료
            mystack 에서 element 를 pop
        반복 종료
        iterator = stackList.begin()
        while (iterator != stackList.end())
            iterator 증가
            while (!stack.empty())
                스택의 최상단(top) 요소를 출력
                스택에서 요소를 pop
        반복 종료
종료.

예제 코드

아래는 위 알고리즘을 그대로 구현한 전체 C++ 코드입니다. 인접 행렬과 스택(stack), 리스트(list)를 조합하여 그래프 위의 모든 유효 경로를 스택 형태로 수집합니다.

#include <iostream>
#include <cstdlib>
#include <stack>
#include <list>
using namespace std;
class GraphStructuredStack {
    private:
    list< stack<int> > stackList;
    stack<int> mystack;
    int noOfNodes;
    int **adjMat;
    int *par;
    public:
    GraphStructuredStack(int noOfNodes) {
        this->noOfNodes =noOfNodes;
        adjMat = new int* [noOfNodes + 1];
        this->par = new int [noOfNodes + 1];
        for (int i = 0; i < noOfNodes + 1; i++)
            adjMat[i] = new int [noOfNodes + 1];
    }
    void graphStructuredStack(int **adjMat, int s,int bNode) {
        bool stackFound = false;
        for (int sVertex = 1; sVertex <= noOfNodes; sVertex++) {
            for (int dVertex = 1; dVertex <= noOfNodes; dVertex++) {
                this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex];
            }
        }
        mystack.push(s);
        int element, d;
        while (!mystack.empty()) {
            element = mystack.top();
            d = 1;
            while (d <= noOfNodes) {
                if (this->adjMat[element][d] == 1) {
                    mystack.push(d);
                    par[d] = element;
                    this->adjMat[element][d] = 0;
                    if (d == bNode) {
                        stackFound = true;
                        break;
                    }
                    element = d;
                    d = 1;
                    continue;
                }
                d++;
            }
            if (stackFound) {
                stack<int> istack;
                for (int node = bNode; node != s; node = par[node]) {
                    istack.push(node);
                }
                istack.push(s);
                stackList.push_back(istack);
                stackFound = false;
            }
            mystack.pop();
        }
        list<stack<int> >::iterator iterator;
        iterator = stackList.begin();
        while (iterator != stackList.end()) {
            stack <int> stack = *iterator;
            iterator++;
            while (!stack.empty()) {
                cout<<stack.top()<<"\t";
                stack.pop();
            }
            cout<<endl;
        }
    }
};
int main() {
    int noofnodes;
    cout<<"Enter number of nodes: ";
    cin>>noofnodes;
    GraphStructuredStack gss(noofnodes);
    int source, bottom;
    int **adjMatrix;
    adjMatrix = new int* [noofnodes + 1];
    for (int i = 0; i < noofnodes + 1; i++)
        adjMatrix[i] = new int [noofnodes + 1];
    cout<<"Enter the graph matrix: "<<endl;
    for (int sVertex = 1; sVertex <= noofnodes; sVertex++) {
        for (int dVertex = 1; dVertex <= noofnodes; dVertex++) {
            cin>>adjMatrix[sVertex][dVertex];
        }
    }
    cout<<"Enter the source node: ";
    cin>>source;
    cout<<"Enter the bottom node: ";
    cin>>bottom;
    cout<<"The stacks are: "<<endl;
    gss.graphStructuredStack(adjMatrix, source, bottom);
    return 0;
}

실행 결과

노드 4개로 구성된 그래프에서 시작 노드를 3, 바닥 노드를 1로 지정한 실행 예입니다. 출력된 31은 시작 노드 3에서 바닥 노드 1로 이어지는 경로가 하나의 스택으로 성공적으로 저장되었음을 의미합니다.

Enter number of nodes: 4
Enter the graph matrix:
1 1 1 0
0 1 1 0
1 0 0 0
1 1 1 1
Enter the source node: 3
Enter the bottom node: 1
The stacks are:
31

마무리

이 프로그램은 인접 행렬과 스택, 리스트를 조합하여 그래프 위의 모든 유효 경로를 스택 형태로 수집하는 과정을 보여줍니다. 코드를 직접 실행해 노드 수, 그래프 행렬, 시작 노드와 바닥 노드를 다양하게 바꿔가며 테스트해 보면 그래프 구조 스택의 동작 원리를 더욱 깊이 이해할 수 있습니다.