위상정렬
페이지 정보
작성일 22-11-09 12:10본문
Download : 위상정렬.hwp
,기타,레포트
설명
레포트/기타
위상정렬에 대한 자료입니다.
4.소스program
#include <…(To be continued )
위상정렬
순서
다.
Download : 위상정렬.hwp( 34 )
위상정렬에 대한 자료(data)입니다. 위상정렬 , 위상정렬기타레포트 ,
위상정렬
1. 문제
다음의 입력 형식을 갖는 화일(유향 그래프)을 읽어서 위상 정렬(topological sorting)을 한 결과를 출력하는 program을 작성하라.
(1) 데이터 화일들(10개)은 data(자료)실에서 제공될 예정임
각 화일에서 입력의 첫줄은 정점의 개수, 유향 에지의 개수가 순서적으로 나타나고, 그 다음 줄부터 에지 개수만큼 유향 에지를 순서 쌍으로 한줄씩 나열 함.
(2) program에서 위상정렬이 안되는 경우(즉, 사이클이 있는 경우)를 반드시 체크해서 그렇다는 메세지를 출력해야 함. 위의 데이터 중에는 그런 경우의 예가 포함되어 있음
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에서 돌렸다.