위상정렬
페이지 정보
작성일 22-10-28 14:17본문
Download : 위상정렬.hwp
위상정렬
설명
레포트/기타
위상정렬
다. 위상정렬 , 위상정렬기타레포트 ,
순서
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에서 돌렸다.
4.소스프로그램(program])
#include <…(투비컨티뉴드 )
,기타,레포트
Download : 위상정렬.hwp( 71 )
위상정렬에 대한 자료(data)입니다.위상정렬에 대한 자료입니다.