문제해결기법 위상정렬

목차

<시작하는 말>

<전역 변수 부분>

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

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

<소스 코드>

본문내용

성분에 대해 정렬을 수행한다
{
j=0;
while(empty(&zeroin[i])==FALSE)//zeroin이라는 큐에 무언가 들어있다면 반복 수행
{
cnt_v++;//주어진 그래프가 DAG인지 체크하기 위한 카운터
j = j+1;
x = dequeue(&zeroin[i]);
sorted[i][j] = x;//정렬된 결과를 저장하는 배열
for(k=0 ; kdegree[x] ; k++)
{
y = g->edges[x][k];
//그 정점에서 나가는 k번째 화살표가 가리키는 값을 y에 저장.
//즉, 그 정점이 가리키는 정점.
indegree[y]--;//y의 차수를 감소
if(indegree[y]==0)//y의 차수가 0이 되었다면, 이제 그것을 큐에 삽입
enqueue(&zeroin[i],y);
}
}
}
if(cnt_v != g->nvertices)
printf("Not a DAG -- only %d vertices found\n",cnt_v);
}
void compute_indegrees(graph* g, int in[])//각 정점으로 들어오는 화살표들의 개수를 계산
{
int i,j;
for(i=1 ; i<=g->nvertices ; i++)
{
in[i] = 0;//초기화
}
for(i=1 ; i<=g->nvertices ; i++)//정점의 개수만큼 반복
for(j=0 ; jdegree[i] ; j++)//그 정점에서 화살표(모서리)가 나간 개수만큼 반복
{
in[ g->edges[i][j] ]++;
//그 정점으로 들어오는 화살표가 몇 개인지 하나씩 증가시키면서 센다
}
}
void enqueue(queue* q, int x)//큐에 원소를 넣는다
{
if(q->cnt >= 100)
printf("오버플로우\n");
else
{
q->tail = (q->tail+1) % 100;
q->que[q->tail] = x;
q->cnt++;
}
}
int dequeue(queue* q)//큐의 원소를 꺼낸다
{
int x;
if(q->cnt <= 0) printf("언더플로우\n");
else
{
x = q->que[q->head];
q->head = (q->head+1)%100;
q->cnt--;
}
return (x);
}
int empty(queue* q)//큐가 비어있는지 체크한다
{
if(q->cnt <= 0) return(TRUE);
else return(FALSE);
}
void print_graph(graph *g)//출력한다
{
int i,j;
printf("그래프의 형태는 아래와 같습니다\n");
for(i=1 ; i<=g->nvertices; i++)
{
printf("%c ->",i+64);//숫자를 문자로 변환 출력(1->A)
for(j=0 ; jdegree[i] ; j++)
{
printf(" %c", g->edges[i][j] + 64);//숫자를 문자로 변환 출력(1->A)
}
printf("\n");
}
printf("\n");
printf("%d개의 연결 성분이 존재합니다\n",cnt_separation);
for(i=0 ; i printf("연결성분 %d: {",i+1);
for(j=1 ; ; j++)
{
if(sorted[i][j+1] == 0)//만일 이 원소가 마지막 원소라면
{
printf("%c}",sorted[i][j]+64);//문제에서 제시한대로 출력 포맷을 맞춤
break;
}
printf("%c, ",sorted[i][j]+64);//숫자를 문자로 변환 출력(1->A)
}
printf("\n");
}
}

키워드

문제해결기법 위상정렬,   위상정렬,   문제해결기법,   소스 코드,   void topsort(graph* g) 함수에서 중요한 것들,   void print_graph(graph *g) 함수에서 참고할 사항