목차
<시작하는 말>
<전역 변수 부분>
<void topsort(graph* g) 함수에서 중요한 것들>
<void print_graph(graph *g) 함수에서 참고할 사항>
<소스 코드>
<전역 변수 부분>
<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");
}
}
{
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 ; 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 ; 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 ; j
{
printf(" %c", g->edges[i][j] + 64);//숫자를 문자로 변환 출력(1->A)
}
printf("\n");
}
printf("\n");
printf("%d개의 연결 성분이 존재합니다\n",cnt_separation);
for(i=0 ; i
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");
}
}
키워드
추천자료
- 60회 전기 통신 필기 시험 문제
- 선택정렬과 이진탐색(자료구조)
- 한국 - 극동러시아 경제협력 현황과 문제점
- 영국증권 시장의 구조와 문제점 및 해결방안
- [신행정수도건설]신행정수도건설(행정수도이전)의 타당성과 최적 조건, 신행정수도건설(행정...
- [화일처리론] 대규모 데이터의 외부 정렬 알고리즘 설계 및 비교
- 사회복지협의회 개념과 기능, 문제점, 개선방향 및 미국, 일본, 한국의 사회복지협의회 비교
- 황우석 신드롬 & 줄기 세포 연구의 쟁점 분석
- 사회과 정치교육의 위상에 대해 논하시오
- 중국 개혁개방 30년 성과와 향후 과제
- 가상공간(인터넷) 학습, 가상공간(인터넷) 교육, 가상공간(인터넷) 자아정체성, 가상공간(인...
- 과학기술정책에서 뉴거버넌스의 동향과 실태- 시민참여 프로그램으로서의 과학상점, 한국사회...
- 우리나라 경찰교육훈련 실태와 문제점 및 해결방안