세상과 소통하는 채널
나를 표현하는 웹에서의 나의 공간

EE209 (전기 공학을 위한 프로그래밍) Homework#2

Graph를 인접 리스트로 구현한 MCST(minimum cost spanning tree)


-

인접 행렬인줄 알고 짰다가 낭패.

종료 조건을 찾지 못해서 낭패 -> min 값을 못찾으면 종료


다음은 소스

--

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX 9999
int n=0;
float p=0.0;
typedef struct Node
{
   int node;
   int cost;
   struct Node *next;
} Node;
Node *graph;
Node *mcst;

void print_graph(char *filename,Node *graph);
void input()
{
  printf("EE209 Homwork #2\n");
  printf("노드의 수(N)을 입력하세요 : ");
   scanf("%d",&n);
   printf("연결선 존재 확률(P)를 입력하세요 : ");
   scanf("%f",&p);
}

Node *createNode(int node,int cost)
{
   Node*tmp;
   tmp=(Node*)malloc(sizeof(Node));
   tmp->node=node;
   tmp->cost=cost;
   tmp->next=NULL;
   return tmp;
}
int isExist()
{
   int cost;
   float r;
   r=(float)rand()/(float)(RAND_MAX+1.0);
   if(r<p)
   {
   cost=(int)(rand()%(2*n))+1;
   return cost;
   }
   return -1;
}
void insert_node(Node*list,int from,int dest,int cost)
{
   Node *tmp,*prev,*tmp2;
   tmp=list[from].next;
   prev=&list[from];
   while(tmp!=NULL)
   {
   if(dest<tmp->node)
   {
       tmp2=prev->next;
       prev->next=createNode(dest,cost);
       prev->next->next=tmp2;
       return;
   }
   prev=tmp;
   tmp=tmp->next;
   }
   prev->next=createNode(dest,cost);
}

void delete_node(Node *list,int from,int dest)
{
   Node *tmp,*prev;
   tmp=list[from].next;
   prev=&list[from];
   while(tmp!=NULL)
   {
   if(tmp->node==dest)
   {
       prev->next=tmp->next;
       return;
   }
   prev=tmp;
   tmp=tmp->next;
   }
}
void make_graph()
{
   int i,j=0;
   int cost;
   int **check;
   Node *tmpNode;
   graph=(Node*)malloc((n+1)*sizeof(Node));
   mcst=(Node*)malloc((n+1)*sizeof(Node));
   check=(int **)malloc((n+1)*sizeof(int*));
   for(i=0;i<=n;i++)
   check[i]=(int*)malloc((n+1)*sizeof(int));
   for(i=0;i<=n;i++)
   for(j=0;j<=n;j++)
       check[i][j]=0;
   for (i=1;i<=n;i++)
   {
   for(j=1;j<=n;j++)
   {
       if(i!=j&&check[i][j]==0)
       if((cost=isExist())>0)
       {
       check[i][j]=1;
       check[j][i]=1;
       insert_node(graph,i,j,cost);
       insert_node(graph,j,i,cost);
       }
   }
   }
   for(i=0;i<=n;i++)
   free(check[i]);
   free(check);
}
int isCycle(int * sn, int val, int cnt)
{
   int i;
   for (i =0; i<cnt; i++)
   if (sn[i] == val) return 1;
   return 0;
}
void find_mcst()
{
   int i,j,min,from;
   int k=0;
   int count = 0;
   int *sn;
   Node *tmpNode;
   sn=(int*)malloc(n*sizeof(int));
   sn[count++] = 1;
   while(count < n)
   {
   min = MAX;
   from =1;
   for (i=0; i<count; i++)  //sn
   {
       tmpNode=graph[sn[i]].next;
       while(tmpNode!=NULL)
       {
       if (tmpNode->cost < min)
       {
           from =sn[i];
           sn[count] = tmpNode->node;
           min = tmpNode->cost;
       }
       tmpNode=tmpNode->next;
       }
   }//for i
  
   if(min==MAX) break;

   if (!isCycle(sn,sn[count],count))
   {
       printf("%d --> %d\n",from,sn[count]);
       insert_node(mcst,from,sn[count],min);
       insert_node(mcst,sn[count],from,min);
       delete_node(graph,from,sn[count]);
       delete_node(graph,sn[count],from);
       //printf("delete node %d---> %d\n",from,sn[count]);
   }
   else
   {
       delete_node(graph,from,sn[count]);
       delete_node(graph,sn[count],from);
       //printf("delete node %d---> %d\n",from,sn[count]);
       sn[count--] = 0;
   }

   // delete node


   count++;

   }//while
}
void print_graph(char *filename,Node *graph)
{
   int i;
   FILE *fp;
   fp=fopen(filename,"w");
   Node *tmp;
   for(i=1;i<=n;i++)
   {
   tmp=graph[i].next;
   if(tmp!=NULL)
   {
       printf("%d : ",i);
       fprintf(fp,"%d : ",i);
       while(tmp!=NULL)
       {
       if(tmp->next!=NULL)
       {
           fprintf(fp,"%d (%d), ",tmp->node,tmp->cost);
           printf("%d (%d), ",tmp->node,tmp->cost);
       }
       else
       {
           fprintf(fp,"%d (%d)",tmp->node,tmp->cost);
           printf("%d (%d)",tmp->node,tmp->cost);
       }
       tmp=tmp->next;
       }
       printf("\n");
       fprintf(fp,"\n");
   }//if
   }
}
int main()
{
   srand((unsigned)time(NULL));
   input();
   make_graph();
   printf("\n<graph.txt>\n");
   print_graph("graph.txt",graph);
   printf("\n");
   find_mcst();
   printf("\n<MCST.txt>\n");
   print_graph("MCST.txt",mcst);
   return 0;
}