#include <stdio.h>
#include <stdlib.h>
#define MAX 8 // 정점의 개수입니다.
// BOOL을 나타내기 위한 정의입니다.
#define TRUE 1
#define FALSE 0
typedef struct Node *pointernode; // 노드포인터타입입니다.
typedef struct Node
{
int vertax; // 정점을 나타냅니다.
pointernode link; // 노드를 연결하는 링크입니다.
}Node;
pointernode graph[MAX]; // 인접리스트 구성 초기 포인터배열입니다.
int visit[MAX]; // 방문 기록을 알 수 있습니다.
int Que[MAX]; // bfs 노드탐색방식에 사용될 배열입니다.(큐방식)
int matrix[MAX][MAX]={ // 인접행렬입니다. (8 by 8 size)
{0,1,1,0,0,0,0,0},
{1,0,0,1,1,0,0,0},
{1,0,0,0,0,1,1,0},
{0,1,0,0,0,0,0,1},
{0,1,0,0,0,0,0,1},
{0,0,1,0,0,0,0,1},
{0,0,1,0,0,0,0,1},
{0,0,0,1,1,1,1,0}
};
void init(); // 인접행렬을 이용해서 인접리스트를 초기화합니다.
void Clear_visit(); // 마킹 FALSE로 클리어
//-----------------------탐색방식------------------------------
void dfs(int v); // 깊이탐색
void bfs(int v); // 너비탐색
//-----------------------너비탐색------------------------------
void enq(int *rear,int vertax);
int deq(int *front);
int main()
{
int v;
Clear_visit(); // 방문기록을 초기화합니다.v
printf("인접리스트입니다. \n");
init(); // 인접행렬을 기반으로 인접 리스트 구성
puts("깊이 우선탐색할 초기 정점을 선택하세요");
scanf("%d",&v);
dfs(v);
puts("");
Clear_visit(); // 방문기록을 초기화합니다
puts("너비 우선탐색할 초기 정점을 선택하세요");
scanf("%d",&v);
bfs(v);
puts("");
return 0;
}
// 인접행렬을 인접리스트로 초기화합니다.
void init()
{
int i,j;
pointernode move; // 이동포인터입니다.
pointernode st; // 비교할 포인터입니다.
pointernode temp; // 동적할당할 매개포인터입니다.
for(i=0; i<MAX; i++)
{
st = graph[i]; // 움직이면서 비교할 변수입니다.
printf("V%d -> ", i);
for(j=0; j<MAX; j++)
{
if(matrix[i][j] != FALSE) // matrix[i][j] == TRUE이면,
{
temp = (pointernode)malloc(sizeof(Node)); //동적메모리할당
temp->vertax = j; // vertax값에 노드 번호로 초기화
if(graph[i] == st) // 아무연결도 없을때
{
// move가 temp주소값을 갖게 하고 graph역시 temp의 주소값으로 초가화합니다..
move = temp;
graph[i] = temp;
printf("%5d", temp->vertax);
}
else // 연결되어 있을 때
{
// 노드를 연결합니다.
move->link = temp;
move = temp;
printf("%5d",temp->vertax);
}
}
}
temp->link = NULL; //나머지 link필드는 NULL로 초기화합니다.
puts("\n");
}
}
// 깊이우선탐색입니다.
void dfs(int v)
{
pointernode w;
visit[v] = TRUE;
printf("%3d",v);
for(w=graph[v]; w; w = w->link)
if(!visit[w->vertax])
dfs(w->vertax);
}
//너비우선탐색입니다.
void bfs(int v)
{
pointernode w;
int front,rear;
front = rear = -1;
printf("%3d",v);
visit[v] = TRUE;
enq(&rear, v);
while(front != rear)
{
v = deq(&front);
for(w = graph[v]; w; w = w->link)
{
if(!visit[w->vertax]) // 마킹되지않은 정점이면(FALSE)
{
printf("%3d",w->vertax);
enq(&rear,w->vertax);
visit[w->vertax] = TRUE;
}
}
}
}
void enq(int *rear,int vertax)
{
*rear = (*rear)%MAX;
Que[++(*rear)] = vertax;
}
int deq(int *front)
{
return Que[++(*front)%MAX];
}
void Clear_visit()
{
int i;
for(i=0; i<MAX; i++)
{
visit[i] = FALSE;
}
}