[자연과학] 문제해결기법 위상정렬
페이지 정보
작성일 22-12-25 15:00
본문
Download : [자연과학] 문제해결기법 위상정렬.hwp
for(i〓0 ; i[cnt_separation ; i++)
각각의 연결 component에 대해 위상정렬을 수행한다.
[전역 변수 부분]
int sorted[10][11] 〓 {0,};
정렬 결과를 저장하는 2차원 배열이다.
`void topsort(graph...
[스타트하는 말]
이번 assignment는 위상정렬을 이용하여 다음 방향성비순환그래프(DAG)의 연결component(Connected Component)을 찾는 프로그램(program]) 을 완성하는 것이었다. 한 component 당 정점은 10개까지 저장 가능한데 11개의 공간을 준 이유는, 인덱스를 0부터 쓰는 것이 아니라 1부터 쓰기 때문일것이다
int cnt_separation;
연결 component의 개수를 세는 카운터이다.
[자연과학] 문제해결기법 위상정렬
설명
`스타트하는 말`
이번 assignment는 위상정렬을 이용하여 다음 방향성비순환그래프(DAG)의 연결component(Connected Component)을 찾는 프로그램(program]) 을 완성하는 것이었다.
int cnt_v〓0;
주어진 그래프가 DAG인지 체크해서 오류 메시지를 출력하는데 필요한 카운터. 원래 책의 코드에서는 변수 j가 하던 일이었는데, 연결 component이 달라질 때마다 j의 값도 달라지기 때문에 변수 j가 카운터로서의 역할을 할 수 없게 되었다. 그래서 넉넉하게 10개까지 저장할 수 있도록 하였다. 위에서 설명(說明)했듯이, 문제를 푸는 컴퓨터의 입장에서는 연결 component이 총 몇 개인지 알 수 없으므로 이 카운터를 전역변수로 만들어서 연결 component이 증가할 때마다 카운터를 증가시켜서 총 개수를 얻는다. 그래서 cnt_v 라는 변수를 새롭게 만들었다. 문제에서는 연결 component이 3개이지만 문제를 푸는 컴퓨터의 입장에서는 연결 component이 몇 개인지 알 수 없다. 연결 component이 총 몇 개가 될지 알 수 없기 때문에 넉넉하게 10개를 잡았다.
[void print_graph(graph *g) 함수에서 참고할 사항]
1. 그래프의 각 정점에서 연결된 다른 정점들을 출력. 연결…(To be continued )
레포트/자연과학
![[자연과학]%20문제해결기법%20위상정렬_hwp_01.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_01.gif)
![[자연과학]%20문제해결기법%20위상정렬_hwp_02.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_02.gif)
![[자연과학]%20문제해결기법%20위상정렬_hwp_03.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_03.gif)
![[자연과학]%20문제해결기법%20위상정렬_hwp_04.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_04.gif)
![[자연과학]%20문제해결기법%20위상정렬_hwp_05.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_05.gif)
![[자연과학]%20문제해결기법%20위상정렬_hwp_06.gif](http://www.allreport.co.kr/View/%5B%EC%9E%90%EC%97%B0%EA%B3%BC%ED%95%99%5D%20%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%EA%B8%B0%EB%B2%95%20%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC_hwp_06.gif)
순서
Download : [자연과학] 문제해결기법 위상정렬.hwp( 79 )
[자연과학],문제해결기법,위상정렬,자연과학,레포트
[자연과학] 문제해결기법 위상정렬 , [자연과학] 문제해결기법 위상정렬자연과학레포트 , [자연과학] 문제해결기법 위상정렬
[자연과학] 문제해결기법 위상정렬
다.
`전역 변수 부분`
int sorted[10][11] 〓 {0,};
정렬 결과를 저장하는 2차원 배열이다. 그래서 넉넉하게 10개까지 저장할 수 있도록 하였다. 위에서 설명(說明)했듯이, 문제를 푸는 컴퓨터의 입장에서는 연결 component이 총 몇 개인지 알 수 없으므로 이 카운터를 전역변수로 만들어서 연결 component이 증가할 때마다 카운터를 증가시켜서 총 개수를 얻는다. 각 연결 component마다 indegree가 0인 스타트 정점이 있고, 각 정점들을 기준으로 인접한 정점들을 정렬해간다. 문제에서는 연결 component이 3개이지만 문제를 푸는 컴퓨터의 입장에서는 연결 component이 몇 개인지 알 수 없다. 한 component 당 정점은 10개까지 저장 가능한데 11개의 공간을 준 이유는, 인덱스를 0부터 쓰는 것이 아니라 1부터 쓰기 때문일것이다
int cnt_separation;
연결 component의 개수를 세는 카운터이다.
[void topsort(graph* g) 함수에서 중요한 것들]
queue zeroin[10];
입력 차수가 0인 정점을 저장하는 배열이다.
