너비우선탐색
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
#define MAX_VERTEX 10
#define FALSE 0
#define TRUE 1
typedef struct GraphNode{
int vertex;
struct GraphNode * link;
}GraphNode;
typedef struct GraphType{
int n;
GraphNode* adjList_H[MAX_VERTEX];
int visited[MAX_VERTEX];
}GraphType;
typedef struct QNode{
int data;
struct QNode *link;
}QNode;
typedef struct
{
QNode *front, *rear;
}LQueueType;
LQueueType *createLinkedQueue() //전역변수선언하면되나
{
LQueueType *LQ;
LQ=(LQueueType*)malloc(sizeof(LQueueType));
LQ->front=NULL;
LQ->rear=NULL;
return LQ;
}
int enQueue(LQueueType* LQ, int item)
{
QNode *newNode=(QNode*)malloc(sizeof(QNode));
newNode->data =item;
newNode->link =NULL;
if(LQ->front =NULL){
LQ->front= newNode;
LQ->rear = newNode;
}
else{
LQ->rear->link=newNode;
LQ->rear =newNode;
}
}
int deQueue(LQueueType *LQ)
{
QNode *old = LQ->front;
int item;
if(LQ->front ==NULL) return 0;
else{
item = old->data;
LQ->front = LQ->front->link;
if(LQ->front ==NULL)
LQ->rear =NULL;
free(old);
return item;
}
}
void createGraph(GraphType* g)
{
int v;
g->n= 0;
for(v=0; v<MAX_VERTEX; v++){
g->visited[v] =FALSE;
g->adjList_H[v]=NULL;
}
}
void insertVertex(GraphType* g, int v)
{
if(((g->n)+1)>MAX_VERTEX){
printf("\n 그래프의 정점의 개수를 초과하였습니다!");
return;
}
g->n++;
}
void insertEdge(GraphType* g, int u, int v)
{
GraphNode* node;
if(u>=g->n || v>=g->n){
printf("\n 그래프에 없는 정점입니다!");
return;
}
node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = v;
node->link=g->adjList_H[u];
g->adjList_H[u] =node;
}
void ini(GraphType *g)
{
int i;
for(i=0; i<MAX_VERTEX; i++)
g->visited[i]=0;
}
void bsfAdjList(GraphType* g, int v)
{
GraphNode* w;
LQueueType* Q;
Q = createLinkedQueue();
g->visited[v] =TRUE;
printf("%-2d", v);
enQueue(Q, v);
while(Q->front !=NULL){
v=deQueue(Q);
for(w=g->adjList_H[v]; w; w =w->link)
if(!g->visited[w->vertex]){
g->visited[w->vertex] =TRUE;
printf("%-2d", w->vertex);
enQueue(Q, w->vertex);
}
}
}
int main(){
int i;
GraphType *G;
G = (GraphType*)malloc(sizeof(GraphType));
createGraph(G);
for(i=0; i<8; i++)
insertVertex(G,i);
insertEdge(G, 0, 1);
insertEdge(G, 0, 2);
insertEdge(G, 1, 3);
insertEdge(G, 1, 4);
insertEdge(G, 1, 0);
insertEdge(G, 2, 5);
insertEdge(G, 2, 6);
insertEdge(G, 2, 0);
insertEdge(G, 3, 7);
insertEdge(G, 3, 1);
insertEdge(G, 4, 7);
insertEdge(G, 4, 1);
insertEdge(G, 5, 7);
insertEdge(G, 5, 2);
insertEdge(G, 6, 7);
insertEdge(G, 7, 2);
insertEdge(G, 7, 3);
insertEdge(G, 7, 4);
insertEdge(G, 7, 5);
insertEdge(G, 7, 6);
ini(G);
printf("\n\n너비우선 탐색>> ");
bsfAdjList(G,0);
printf("\n");
}