반응형
1. Implement the dfs and bfs algorithms using the given graph and adjacency lists (Figure 1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <stdio.h> #include <stdlib.h> #define SIZE 8 #define FALSE 0 //boolean 연산을 위한 상수 설정 #define TRUE 1 //boolean 연산을 위한 상수 설정 typedef struct node *pn; //node형 포인터 자료형 pn typedef struct node{ int vertice; pn link; }node; //node 자료형 안에는 node의 주소를 나타내는 link와 정수형 변수 vertice 포함 void add(pn a); void dfs(int v); void bfs(int v); void addq(int *rear,int value); int deleteq(int *front); pn graph[SIZE]; //pn형 크기 8짜리 배열 graph int visited[SIZE]; //int형 크기 8짜리 배열 visited, 방문한 노드 삽입 int queue[SIZE]; // 사이즈 8짜리 큐 int main(void) { pn cup; //pn형 변수 cup (포인터) 임시 저장소 int i; for(i=0;i<SIZE;i++) //graph 배열의 원소 초기화 { graph[i]=0; } add(&graph[0],1); add(&graph[0],2); add(&graph[1],0); add(&graph[1],3); add(&graph[1],4); add(&graph[2],0); add(&graph[2],5); add(&graph[2],6); add(&graph[3],1); add(&graph[3],7); add(&graph[4],1); add(&graph[4],7); add(&graph[5],2); add(&graph[5],7); add(&graph[6],2); add(&graph[6],7); add(&graph[7],3); add(&graph[7],4); add(&graph[7],5); add(&graph[7],6); //주어진 그림대로 그래프 초기화 하는 과정 for(i=0;i<SIZE;i++){ cup=graph[i]; //graph[i]를 cup에 대입 printf("graph[%d] ",i); while(cup){ //cup이 0이 아니면(각 노드는 링크드 리스트로 구성되어 있어 마지막 노드는 0을 가리킴) printf("%d ",cup->vertice); //cup->vertice 출력 cup=cup->link; //cup에 cup->link 대입 } printf("\n"); //개행문자 출력 } printf("DFS : ");dfs(0); printf("\n"); //dfs 실행 for(i=0;i<SIZE;i++) {visited[i]=FALSE;} //visited된 노드들 초기화 (bfs 를 하려면 초기화 시켜줘야함) printf("BFS : ");bfs(0); printf("\n"); //bfs 실행 return 0; } void add(pn *a,int value){ //그래프의 노드를 연결해주는 함수 /*a에 해당하는 것이 노드를 가리키는 포인터, value는 추가할 값이다. a에 이미 연결되어 있는 메모리가 존재하면 계속 링크를 타고 가다가 링크가 0인 메모리에 동적메모리할당 한것을 링크시켜 그곳에 value를 넣어준다 add(&graph[0],1); add(&graph[0],2); 예를들어 main함수에서 나온 것인데 맨처음 graph[0]이 1을 갖는 메모리를 가리키고 1를 갖는 메모리가 2를 갖는 메모리를 가리키고 2를 갖는 메모리의 링크는 0이다. 이런식으로 진행이 된다. 링크가 0인지 아닌지는 함수가 스스로 판단한다.*/ pn *check=0; //check를 NUL로 초기화,check는 이중포인터 pn tmp = (pn)malloc(sizeof(node)); //tmp가 가리키는 곳에 node size 동적 메모리 할당 check=a; //check가 가리키는 주소 = a가 가리키는 주소 while(1){ if((*check)==0){break;} // check가 가리키는 주소가 0이면 루프 탈출 else if(((*check)->link)!=0){ //(*check)->link)!=0)이면 check=&((*check)->link); //check에 &((*check)->link) 대입 } else{ //이외의경우 check=&((*check)->link); //check에 &((*check)->link) 대입하고 break break;}} *check=tmp; //check가 가리키는 주소에 tmp 대입 (*check)->vertice=value; //value를 마지막 노드의 vertice 에 삽입 (*check)->link=0; //마지막 노드의 링크는 0 } void dfs(int v){ pn w; //pn형 변수 w (포인터) visited[v]=TRUE; //visited[v]에 1 대입 printf("%5d",v); //5자리수로 해서 출력 for(w=graph[v];w;w=w->link) //초기식 : w=graph[v], 조건식 : w가 존재하면(not 0) 증가식 : w에 w->link 대입 { if(!visited[w->vertice]) //w가 가리키는 주소의 vertice가 방문하지 않은 노드라면 dfs(w->vertice); //dfs 순환 호출 } } void bfs(int v){ pn w; //pn형 변수 w(포인터) int front=-1; //front와 rear 를 -1로 설정(원형 큐) int rear=-1; printf("%5d", v); // 5의 전체 크기로 출력 visited[v]=TRUE; //visited[v]에 true 대입(1) addq(&rear,v); //v를 원형 큐에 삽입 while(front!=rear){ //front가 not rear 이면 v=deleteq(&front); // 맨 앞 원소 delete for(w=graph[v];w;w=w->link){ //초기식 : w=graph[v], 조건식 : w가 존재하면(not 0) 증가식 : w에 w->link 대입 if(!visited[w->vertice]) //w가 가리키는 주소의 vertice가 방문하지 않은 노드라면 { printf("%5d", w->vertice); //w->vertice 출력 addq(&rear,w->vertice); //w->vertice 큐에 삽입 visited[w->vertice]=TRUE; //visited[w->vertice]에 true 대입(1) }}}} void addq(int *rear,int value){ //원형 큐에서 삽입 *rear=(*rear)%SIZE; queue[++(*rear)]=value; } int deleteq(int *front){ //원형 큐에서 원소 삭제 return queue[++(*front)%SIZE]; } | cs |
2. Refine Prim’s algorithm, Kruskal’s algorithm into a C function that finds a minimum cost spanning tree.
Prim’s algorithm
Kruskal’s algorithm
graph
<Prim's Algorithm>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <stdio.h> #include <stdlib.h> typedef struct edge{ //edge 형 변수 int left; //int형변수 left,right,weight,u를 포함한다. int right; int weight; int u; // 어떤 집합에 속할지 정해준다. (여기서는 사용하지 않음) }edge; void Prim(edge E[],edge T[]); int Ecount=0; //몇번째 E의 원소를 참조하고 있는가 int TVlength=1; //노드가 들어갈 집합 int Tlength=0; //dege T의 길이 int TV[7]={0,-1,-1,-1,-1,-1,-1}; //노드가 들어갈 집합, 몇번부터 시작하는지는 상관 없으나 0번부터 시작하라고 해서 0번만 넣고 나머지는 나올 수 없는 -1로 초기화 edge T[6]; //우리가 prim algorithm 에 의해 선택한 간선을 넣을 집합 edge E[9]; //기존에 주어진 set int main(void) { int i; for(i=0;i<20;i++){ T[i].left=-1; T[i].right=-1; T[i].u=-1; T[i].weight=-1;} E[0].left=5; E[0].right=0; E[0].weight=10; E[0].u=-1; E[1].left=0; E[1].right=1; E[1].weight=28; E[1].u=-1; E[2].left=1; E[2].right=2; E[2].weight=16; E[2].u=-1; E[3].left=2; E[3].right=3; E[3].weight=12; E[3].u=-1; E[4].left=6; E[4].right=3; E[4].weight=18; E[4].u=-1; E[5].left=4; E[5].right=3; E[5].weight=22; E[5].u=-1; E[6].left=4; E[6].right=6; E[6].weight=24; E[6].u=-1; E[7].left=5; E[7].right=4; E[7].weight=25; E[7].u=-1; E[8].left=6; E[8].right=1; E[8].weight=14; E[8].u=-1; //책에 나와있는대로 초기화 Prim(E,TV); //Prim 알고리즘 실행 for(i=0;i<6;i++) {printf("%d %d %d %d\n",T[i].left,T[i].right,T[i].u,T[i].weight);} //확인을 위해 출력 return 0; } void Prim(edge E[],int TV[]){ int i=0; int j; int k;int count=0; int flag=0; int tmpisl=-1; edge tmpedge; while(Tlength<6){ /*for(u=0;u<TVlength;u++) {printf("%d",TV[u]);} printf("\n");*/ tmpisl=-1; tmpedge.left=-1; tmpedge.right=-1; tmpedge.u=-1; tmpedge.weight=100; //tmp 각 원소 초기화 weight는 무조건 모든 간선 weight보다 크게 for(j=0;j<9;j++){ //j는 0부터 9보다 작을 때까지 count=0; //count=0으로 초기화 for(k=0;k<TVlength;k++) //k=0부터 TVlength 보다 작을 때까지 {if((TV[k]==E[j].left)) //TV[k]가 E[j].left와 같으면 count++;} //count ++; for(k=0;k<TVlength;k++){ //k=0부터 TVlength 보다 작을 때까지 if((TV[k]==E[j].right)) //TV[k]가 E[j].right와 같으면 count++;} //count ++; printf("i=%d j=%d k=%d count=%d TLength=%d TVLength=%d\n",i,j,k,count,Tlength,TVlength); if(count==1){ //즉 E[j](간선)에 노드 TV[k]가 들어있으면 만약 count==2면 cycle 이라서 안됨 if(E[j].weight<tmpedge.weight) //E[j].weight<tmpedge.weight 면(작은걸 택해야 하니까) { tmpedge.left=E[j].left; tmpedge.right=E[j].right; tmpedge.u=E[j].u; tmpedge.weight=E[j].weight; //tmp에 E[j]의 요소 대입 flag=0; //flag에 0 대입 for(k=0;k<TVlength;k++){ //k=0부터 TVlength 아래까지 if(E[j].left==TV[k]) //E[j].left==TV[k]면 루프탈출 break; else flag++; //아니면 flag++ } if(flag==TVlength) //flag가 TVlength면 tmpisl=E[j].left; //tmpisl 에 E[j].left대입 flag=0; //flag 0으로 초기화 for(k=0;k<TVlength;k++){ //k=0부터 k<TVlength 까지 if(E[j].right==TV[k]) //E[j].right==TV[k]면 루프탈출 break; else flag++; //아니면 flag++ } if(flag==TVlength) //flag==TVlength면 tmpisl=E[j].right; // tmpisl에 E[j].right대입; /*TV에 없는걸 tempisl에넣어야함*/} } } TV[TVlength]=tmpisl; //TV에 tmpisl 대입 TVlength++; //TVlength 증가 T[Tlength].left=tmpedge.left; T[Tlength].right=tmpedge.right; T[Tlength].u=tmpedge.u; T[Tlength].weight=tmpedge.weight; //tmp에있는 요소 T[Tlength]에 대입 Tlength++; //Tlength 증가 i++; //i증가 } } | cs |
<Kruskal's Algorithm>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <stdio.h> #include <stdlib.h> typedef struct edge{ //edge 형 변수 int left; //int형변수 left,right,weight,u를 포함한다. int right; int weight; int u; // 어떤 집합에 속할지 정해준다. }edge; void Kruskal(edge E[],edge T[]); void select_sort(edge vector[],int size); int notcycle(edge *e,edge T[]); int makeuni(edge *e,edge T[]); void jointuni(edge T[]); int uni=0; //전역변수, 집합의 이름(번호)를 정함 int Ecount=0; //E의 인덱스 int Tlength=0; //T의 길이(T에 원소 몇개인지) edge T[6]; //edge형 배열 T 크기 6 edge E[9]; //edge형 배열 E 크기 9 int k; int main(void) { int i; for(i=0;i<20;i++){ T[i].left=-1; T[i].right=-1; T[i].u=-1; T[i].weight=-1;} //T 초기화 (안나올 값으로) E[0].left=5; E[0].right=0; E[0].weight=10; E[0].u=-1; E[1].left=0; E[1].right=1; E[1].weight=28; E[1].u=-1; E[2].left=1; E[2].right=2; E[2].weight=16; E[2].u=-1; E[3].left=2; E[3].right=3; E[3].weight=12; E[3].u=-1; E[4].left=6; E[4].right=3; E[4].weight=18; E[4].u=-1; E[5].left=4; E[5].right=3; E[5].weight=22; E[5].u=-1; E[6].left=4; E[6].right=6; E[6].weight=24; E[6].u=-1; E[7].left=5; E[7].right=4; E[7].weight=25; E[7].u=-1; E[8].left=6; E[8].right=1; E[8].weight=14; E[8].u=-1; //교과서에 나온 것처럼 초기화 Kruskal(E,T); //Kruscal 알고리즘 실행 for(i=0;i<6;i++) {printf("%d %d %d %d\n",T[i].left,T[i].right,T[i].u,T[i].weight);} //출력으로 제대로 나왔나 확인 return 0; } void Kruskal(edge E[],edge T[]){ edge temp; select_sort(E,9); //E를 가중치의 크기대로 오름차순 정렬한다. while((Tlength<6)&&(Ecount<9)){ //Tlength가 6보다 작고 Ecount가 9보다 작으면 루프 반복 temp.left=E[Ecount].left;temp.right=E[Ecount].right;temp.weight=E[Ecount].weight; temp.u=E[Ecount].u; //temp의 각 요소에 E[Ecount]의 요소 대입 E[Ecount].left=-1;E[Ecount].right=-1;E[Ecount].weight=-1; //E의 Ecount 원소는 삭제 (-1대입) makeuni(&temp,T); //temp의 집합을 만들어준다. jointuni(T); //같은 집합인데 번호가 다른 집합이 있으면 합해준다. temp를 제외한 T만 해준다. (cycle 검사때문에) for(k=0;k<Tlength;k++){ printf("T[%d].u=%d ",k,T[k].u); } printf("tmp.u : %d\n",temp.u); //T의 원소의 집합 번호와 temp의 집합 번호 확인 if(notcycle(&temp,T)) //싸이클이 생기지 않으면 { T[Tlength].left=temp.left;T[Tlength].right=temp.right;T[Tlength].weight=temp.weight; T[Tlength].u=temp.u; //T[Tlength]의 요소에 temp의 요소 대입 Tlength++;Ecount++; //Tlength와 Ecount 하나씩 증가 } else{Ecount++;} //싸이클이 생겼으면 Ecount만 증가 }} void select_sort(edge vector[],int size){ //선택정렬 알고리즘 int i; int j; int temp; int index; for(i=0;i<size;i++) { index=i; for(j=i+1;j<size;j++) { if((vector[j].weight)<vector[index].weight){ index=j;} } temp=vector[index].weight; vector[index].weight=vector[i].weight; vector[i].weight=temp; temp=vector[index].left; vector[index].left=vector[i].left; vector[i].left=temp; temp=vector[index].right; vector[index].right=vector[i].right; vector[i].right=temp; } } int notcycle(edge *e,edge T[]){ //간선이 cycle 형성 하는지 리턴값이 판별 1이면 notcycle, 0이면 cycle int check=0; int i; if(Tlength==0) //Tlength가 0이면 1반환 return 1; for(i=0;i<Tlength;i++){ //i=0부터 Tlength 이전까지 반복 if(e->u==T[i].u){ //e->u 와 T[i].u 가같으면 (집합이 같으면) if((e->left==T[i].left)||(e->left==T[i].right)||(e->right==T[i].left)||(e->right==T[i].right)){ //e의 left가 t의 left나 right와 같거나, e의 right가 t의 left나 right와 같거나 check++; printf("Tlength=%d i=%d check=%d\n\n",Tlength,i,check);} //check 증가식 if(check==2) //즉 같은 집합 내에서 {return 0;} }} return 1; } int makeuni(edge *e,edge T[]){ //집합을 만드는 함수 int i; int check=0; if(Tlength==0) //Tlength가 0이면 {e->u=uni++; return e->u;} //e->u에 uni 대입하고 증가, e->u 리턴 else{ for(i=0;i<Tlength;i++) { if((e->left==T[i].left)||(e->left==T[i].right)||(e->right==T[i].left)||(e->right==T[i].right)) //e의 left가 t의 left나 right와 같거나, e의 right가 t의 left나 right와 같거나 {check=1; //check에 1 대입 e->u=T[i].u; return e->u; //e->u 에 T[i].u 대입 (즉 둘은 같은 집합이됨) e->u 리턴 break;} } if(check==0){ //check가 0이면 e->u=uni++; return e->u; //e->u에 uni대입하고 uni 증가시킴, e->u 리턴 (새로운집합) }}} void jointuni(edge T[]){ //집합을 합치는 함수 int i; for(i=0;i<Tlength;i++){ //i=0부터 Tlength 보다 작을때까지 반복 if((T[i+1].left==T[i].left)||(T[i+1].left==T[i].right)||(T[i+1].right==T[i].left)||(T[i+1].right==T[i].right)){ //T[i+1]의 left가 T[i]의 left나 right와 같거나, T[i+1]의 right가 T[i]의 left나 right와 같거나, if(T[i+1].u<T[i].u) //T[i+1].u가 T[i].u보다 작으면 T[i].u=T[i+1].u; //T[i+1].u를 T[i].u에 대입 else T[i+1].u=T[i].u; //작은 쪽으로 집합 번호를 매긴다. }}} | cs |
반응형
'컴퓨터 & 프로그래밍 & 전자공학 > Data Sturcture' 카테고리의 다른 글
| 데이터 스트럭처 보고서 (0) | 2017.10.16 |
|---|---|
| preorder, postorder, inorder, heap, tree (0) | 2017.10.01 |
| stack, queue (0) | 2017.10.01 |
| 참고 사항 (0) | 2017.10.01 |
| 하노이의 탑, iterative, recursive fucntcion, 이진 탐색 (0) | 2017.10.01 |
