[양때구름]위상정렬을 이용하여 다음 방향성비순환그래프(DAG)의 연결성분(Connected Component)을 찾는 프로그램

소개

위상정렬을 이용하여 다음 방향성비순환그래프(DAG)의 연결성분(Connected Component)을 찾는 프로그램입니다.

목차

없음

본문내용

void topsort(graph* g) 함수에서 중요한 것들>

queue zeroin[10];
입력 차수가 0인 정점을 저장하는 배열이다. 연결 성분이 총 몇 개가 될지 알 수 없기 때문에 넉넉하게 10개를 잡았다.

int cnt_v=0;
주어진 그래프가 DAG인지 체크해서 오류 메시지를 출력하는데 필요한 카운터. 원래 책의 코드에서는 변수 j가 하던 일이었는데, 연결 성분이 달라질 때마다 j의 값도 달라지기 때문에 변수 j가 카운터로서의 역할을 할 수 없게 되었다. 그래서 cnt_v 라는 변수를 새롭게 만들었다.

for(i=0 ; i<cnt_separation ; i++)
각각의 연결 성분에 대해 위상정렬을 수행한다. 각 연결 성분마다 indegree가 0인 시작 정점이 있고, 각 정점들을 기준으로 인접한 정점들을 정렬해간다.


<void print_graph(graph *g) 함수에서 참고할 사항>

1. 그래프의 각 정점에서 연결된 다른 정점들을 출력. 연결된 것이 없으면 공백.
2. 총 몇 개의 연결 성분이 존재하는지 출력.
3. 위상 정렬된 결과들을 출력

sorted[i][j]+64
숫자를 문자로 변환 출력하기 위해 64를 더했다.
아스키코드에서 A는 65이기 때문에, 1을 A에 대응시키기 위해 64를 더했다.

참고자료

· 없음