[자료구조] 그래프

소개글

[자료구조] 그래프에 대한 보고서 자료입니다.

본문내용

i].weight←0;
A[i].connect←0;
}
for(i←0; i for(j←i+1; j if(g.edgeWeight[i][j]>0) do {
A[k].weight=g->edgeWeight[i][j];
A[k].startv=i;
A[k].endv=j;
A[k].connect=0;
A[k].group=0;
k++;
}
}
}
bubble_sort(A,k); // A구조체 가중치 크기가 작은 순서로 정렬
for(i←0; A[i].weight≠0;i=i+1) do A[i].group←i+1;
n←0;
for(i←0; A[i].weight≠0; i=i+1) do {
if(NOT (A[i].connect) AND n < g.nVertices-1 ) do {
if(groupcheck(A,i)){ // 간선이 싸이클을 만들지 않도록 한다.
groupchange(A,i);
A[i].connect=true;
A[i].startv 값과 A[i].endv 값을 캐릭터형태로 출력(0부터 ABC 알파벳순서이다);
n=n+1;
}
}
}
}
○ 실습 결과
○ 작성자의 코멘트 기재
이번 실습으로 그래프를 텍스트 파일에서 숫자로 표현해 그 값을 통해 그래프를 생성하는 방법과 그래프 탐색 방법, Kruskal 알고리즘 까지 많은 것을 공부 할 수 있었다.
깊이 우선 탐색 방법은 이론 수업 때 배웠던 스택을 이용하는 방법이 아니라 재귀함수만을 사용하여 짜여 진 코드를 받아 재귀함수로도 구현하는 방법에 대해 알아볼 수 있었다. 이번 과제인 너비우선 탐색을 재귀 함수만을 이용하기엔 부족하여 임시공간을 사용하여 큐를 이용한 효과와 같은 방식으로 구현해 보았고, Kruskal은 초기에 자료형태를 복잡하게 잡았던 탓인지 함수의 내용이 많이 복잡 했던 것 같다. Kruskal 알고리즘의 구현 중에서 사이클인지 확인하는 방법에 대해 많은 생각을 해보았는데 그중 가장 쉽다고 생각된 방법인 그룹형태로 묶어서 사이클을 생성하지 않도록 하는 방법으로 구현해 보았다.
이번 실습이 시험기간 며칠을 앞두고 나왔던 과제임과 동시에 여태 했던 실습 과제 중에 난이도가 높은 과제였기에 적잖은 어려움이 있었다. 하지만 한 학기 동안 배웠던 자료구조 수업의 마지막 실습 과제였던 만큼 과제를 하면서 의미 있고 뿌듯하게 할 수 있었다.
교수님 한 학기 동안 수고하셨습니다.

키워드

자료구조,   그래프,   DFS