위상정렬

1. 문제 다음의 입력 형식을 갖는 화일(유향 그래프)을 읽어서 위상 정렬(topological sorting)을 한 결과를 출력하는 프로그램을 작성하라. (1) 데이터 화일들(10개)은 자료실에서 제공될 예정임 각 화일에서 입력의 첫줄은 정점의 개수, 유향 에지의 개수가 순서적으로 나타나고, 그 다음 줄부터 에지 개수만큼 유향 에지를 순서 쌍으로 한줄씩 나열 함. (2) 프로그램에서 위상정렬이 안되는 경우(즉, 사이클이 있는 경우)를 반드시 체크해서 그렇다는 메세지를 출력해야 함. 위의 데이터 중에는 그런 경우의 예가 포함되어 있음 2.입출력의 예 정점이 4개, 에지가 (v1, v2), (v1, v3), (v2, v4)의 3개라면, 입력: 4 3 // 정점의 개수, 에지의 개수 1 2 // 유향 에지 (v1, v2) 1 3 // ... 2 4 출력: v1 v2 v4 v3 3.문제풀이 방법(알고리즘) 노드와 에지의 개수를 입력받아서 node포인터 node1에 저장하고 헤드노드 graph에 링크시키고 그에 알맞게 graph[].count의 값을 증가시켜서 topSort에서 돌렸다. 4.소스프로그램 #include #define MAX_NO_VERTICES 50 typedef struct node *nodePointer; struct node{ int vertex; nodePointer link; }; typedef struct{ int count; nodePointer link; } headNode; headNode graph[MAX_NO_VERTICES]; void topSort(int n);