Data Structures HW6

소개글

연세대학교 데이타구조 숙제입니다. 만점받았습니다

목차

(1) Brief explanation of the problem
(2) Your view as to how it ties in with what we covered in class
(3) Discussion of your result
(4) Short explanation of your code
(5) Your code

본문내용

(1) Brief explanation of the problem
The goal of this problem is that we should make a code by using Kruskal`s algorithm and find out the minimum number/cost of roads which I built to connect the cities by using Kruskal`s algorithm.
(2) Your view as to how it ties in with what we covered in class
This topic is related with Graph and Kruskal`s algorithm. And to implement the Kruskal`s algorithm, I used heapsorting function which I made it in homework 5. The graph consists of a set of vertices and a set of edges. And each edge is a pair. So if the pair is ordered, then the graph is directed. In an undirected graph with edge(v,w) and w is adjacent to v and v is adjacent to w.(Our homework is related with undirected. ) A path in a graph is a sequence of vertices and the length of such a path is the number of edges on the path.

<중 략>

heap* h;
disjset s;
initialize(s);
h = graphintoheap(g);
heapsort(h, edgenumber);
//여기까지 disjointset초기화->graph를 heap으로변환->변환한heap을cost낮은순으로 sorting
printf("Start Arrive Cost Number of road\n");
while(edgeaccepted < vertexnumber-1){
u = h[i].x % 65;
v = h[i].y % 65;
//char로 저장되어있는 도시들을 아까 저장 되어있던 integer로 변환
uset = find(u, s);
vset = find(v, s);
//출발도시와 도착도시의 disjoint 위치 찾기
if(uset != vset){//위치가 다른 경우,즉 연결 안되어있을때

참고 자료

없음