[자료구조] C언어로 가능한 모든 위상정렬을 구하는 프로그램 구현

1. 코드

C언어로 가능한 모든 위상 정렬을 구하는 프로그램을 구현하기 위해 필요로 하는 것이 그래프의 표현 방식과 백트랙킹을 통한 모든 위상 정렬의 탐색이다. 위상 정렬은 Directed Acyclic Graph(Directed Acyclic Graph)에서 정점들을 선형으로 나열하는 방법이다. 주어진 그래프의 간선 방향에 따라 정점 순서를 정해야 하며, 하나의 정점이 다른 정점보다 먼저 나와야 할 경우 그 관계에 따라 배열해야 한다. 이 프로그램은 다음과 같은 주요 구성 요소로 이루어져 있다. 첫 번째로는 인접 리스트 또는 인접 행렬을 사용하여 그래프를 표현하고, 두 번째로 위상 정렬을 위한 DFS(Depth First Search)나 백트래킹 기법을 활용하여 가능한 모든 정렬을 탐색해야 한다. 또한, 각 정점의 진입 차수(indegree)를 관리하여 어느 정점이 선택 가능한지를 결정하는 것이 중요하다. 먼저, 그래프를 인접 리스트로 표현하기로 한다. 각 정점에 대해 연결된 정점의 목록을 저장할 수 있도록 동적 할당을 활용해 리스트를 생성한다. 그 후, 진입 차수를 관리하기 위한 배열을 준비한다. 이 두 가지 자료구조를 통해 그래프를 초기화하고 입력받은 간선 정보를 통해 그래프를 …