자연과학 문제해결기법 위상정렬

자연과학 문제해결기법 위상정렬

[자연과학] 문제해결기법 위상정렬.hwp

본문 이번 과제는 위상정렬을 이용하여 다음 방향성비순환그래프(DAG)의 연결성분(Connected Component)을 찾는 프로그램을 완성하는 것이었다. <전역 변수 부분> int sorted 10 11 = 0, ; 정렬 결과를 저장하는 2차원 배열이다. 문제에서는 연결 성분이 3개이지만 문제를 푸는 컴퓨터의 입장에서는 연결 성분이 몇 개인지 알 수 없다. 그래서 넉넉하게 10개까지 저장할 수 있도록 하였다. 한 성분 당 정점은 10개까지 저장 가능한데 11개의 공간을 준 이유는, 인덱스를 0부터 쓰는 것이 아니라 1부터 쓰기 때문이다. int cnt_separation; 연결 성분의 개수를 세는 카운터이다. 위에서 설명했듯이, 문제를 푸는 컴퓨터의 입장에서는 연결 성분이 총 몇 개인지 알 수 없으므로 이 카운터를 전역변수로 만들어서 연결 성분이 증가할 때마다 카운터를 증가시켜서 총 개수를 얻는다. 하고 싶은 말 열심히 작성하고 좋은 평을 받은 자료 입니다. 감사합니다. 키워드 연결, 성분, 개수, 출력, 카운터, 변수