dfs, bfs, prim, kruskal

1. Implement the dfs and bfs algorithms using the given graph and adjacency lists (Figure 1).

#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];
}
 

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>

#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증가
    }
        
}

<Kruskal's Algorithm>

#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; //작은 쪽으로 집합 번호를 매긴다.
        }}}