DmDream.com (Draw My Dream)

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 10
#define MAX_QUEUE_SIZE 100
#define IS_EMPTY(ptr) (!(ptr))
#define IS_FULL(ptr) (!(ptr))

void bfs(int);

typedef struct edge *edge_pointer;

typedef struct edge{
  short int marked;
  int vertex1;
  int vertex2;
  edge_pointer path1;
  edge_pointer path2;
};

edge_pointer graph[MAX_VERTICES];

int visited[MAX_VERTICES];

typedef struct queue *queue_pointer;

typedef struct queue
{
  int vertex;
  queue_pointer link;
};

void addq(queue_pointer *,queue_pointer *,int);
int deleteq(queue_pointer *);

void addq(queue_pointer *front,queue_pointer *rear,int vertex)
{
 queue_pointer temp =(queue_pointer)malloc(sizeof(struct queue));
 if(IS_FULL(temp))
 {
  fprintf(stderr,"The memory is full\n");
  exit(1);
 }

 temp->vertex = vertex;
 temp->link = NULL;
 if(*front) (*rear)->link = temp;
 else *front = temp;
 *rear = temp;
}

int deleteq(queue_pointer *front)
{
  queue_pointer temp=(*front);
  int temp2=0;
  
  temp2=(*front)->vertex;
  *front=temp->link;
  free(temp);
  return (temp2);

}

void main()
{
 int i=0;
 struct edge edges[10];
 edges[0].vertex1=0;
 edges[0].vertex2=1;
 edges[0].path1=&edges[1];
 edges[0].path2=&edges[2];

 edges[1].vertex1=0;
 edges[1].vertex2=2;
 edges[1].path1=NULL;
 edges[1].path2=&edges[4];

 edges[2].vertex1=1;
 edges[2].vertex2=3;
 edges[2].path1=&edges[3];
 edges[2].path2=&edges[6];

 edges[3].vertex1=1;
 edges[3].vertex2=4;
 edges[3].path1=NULL;
 edges[3].path2=&edges[7];

 edges[4].vertex1=2;
 edges[4].vertex2=5;
 edges[4].path1=&edges[5];
 edges[4].path2=&edges[8];

 edges[5].vertex1=2;
 edges[5].vertex2=6;
 edges[5].path1=NULL;
 edges[5].path2=&edges[9];

 edges[6].vertex1=3;
 edges[6].vertex2=7;
 edges[6].path1=NULL;
 edges[6].path2=&edges[7];
 
 edges[7].vertex1=4;
 edges[7].vertex2=7;
 edges[7].path1=NULL;
 edges[7].path2=&edges[8];

 edges[8].vertex1=5;
 edges[8].vertex2=7;
 edges[8].path1=NULL;
 edges[8].path2=&edges[9];

 edges[9].vertex1=6;
 edges[9].vertex2=7;
 edges[9].path1=NULL;
 edges[9].path2=NULL;

 graph[0]=&edges[0];
 graph[1]=&edges[0];
 graph[2]=&edges[1];
 graph[3]=&edges[2];
 graph[4]=&edges[3];
 graph[5]=&edges[4];
 graph[6]=&edges[5];
 graph[7]=&edges[6];
 
/*
 struct edge edges[3];
 edges[0].vertex1=0;
 edges[0].vertex2=1;
 edges[0].path1=&edges[1];
 edges[0].path2=NULL;
 
 edges[1].vertex1=0;
 edges[1].vertex2=2;
 edges[1].path1=NULL;
 edges[1].path2=&edges[2];

 edges[2].vertex1=2;
 edges[2].vertex2=3;
 edges[2].path1=NULL;
 edges[2].path2=NULL;

 graph[0]=&edges[0];
 graph[1]=&edges[0];
 graph[2]=&edges[1];
 graph[3]=&edges[2];

 printf("%d ",&edges[0]);
 printf("%d ",&edges[1]);
 printf("%d ",&edges[2]);
 printf("\n%d ",edges[0].path1);
 printf("\n%d ",edges[1].path1);
 printf("\n\n\n");
 bfs(2);
*/

 bfs(0);
}

void bfs(int v)
{ 

 edge_pointer w;
 queue_pointer front,rear;
 front=rear=NULL;  // Quere의 초기화
 visited[v] = 1;  // BFS처음 값을 방문했다고 체크
 addq(&front,&rear,v);  // BFS처음값을 queue에 넣는다.

 while(front)  // queue의 값이 NULL일 때까지 반복한다.
 {
  v = deleteq(&front); //우선 queue 하나를 삭제한후 값을 가지고 온다.
  printf("%d ->",v);
  w=graph[v];
  // multi list는 vertex 1 vertex2 어느 값이 선택될지 몰라, 두 경우를 나누어 설정
  // 하나의 노드가 설정 되면 인접한 노드가 등록 된지 체크후 없으면 체크한한후 큐에 등록
  // 그 노드가 Null이 될때까지 이동하면서 반복 하는게 주 내용.
  while(w)
  {
   if(v==w->vertex1)
   {  
    if(!visited[w->vertex2])
    { 
     visited[w->vertex2] =1;    
     addq(&front,&rear,w->vertex2);
    }
    w=w->path1;
   }

   else if(v==w->vertex2)
   {
    if(!visited[w->vertex1])
    { 
     visited[w->vertex1] =1;
     addq(&front,&rear,w->vertex1);
    }
    w=w->path2;
   }
  } 
 }
}