'자료구조'에 해당되는 글 18건

  1. 2008.11.09 자료구조 마지막 과제 -그래프 깊이 우선 탐색
2008.11.09 23:57

자료구조 마지막 과제 -그래프 깊이 우선 탐색




#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
#define MAX_VERTEX 10
#define FALSE 0
#define TRUE 1

typedef struct graphNode{
int n;
graphNode* adjList_H[MAX_VERTEX];
int visited[MAX_VERTEX];
}graphType;

//////// <<스택 연산
typedef struct stackNode{
int data;
struct stackNode *link;
}stackNode;

stackNode* top;

void push(int item)
{
stackNode* temp=(stackNode *)malloc(sizeof(stackNode));
temp->data=item;
temp->link=top;
top=temp;
}

int pop()
{
int item;
stackNode* temp=top;
if(top == NULL){
printf("\n\n Stack is empty !\n");
return 0;
}
else{
item = temp->data;
top=temp->link;
free(temp);
return item;
}
}
//////// 스택 연산 >>

//////// << 큐 연산
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 isEmpty(LQueueType *LQ)
{
if (LQ->front == NULL) {
printf("\n Linked Queue is empty! \n");
return 1;
}
else return 0;
}

void enQueue(LQueueType *LQ, int item)
{
QNode *newNode=(QNode *)malloc(sizeof(QNod));
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(isEmpty(LQ)) 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 print_adjList(graphType* g)
{
int i;
graphNode* p;
for(i=0; i<g->n; i++){
printf("\n\t\t 정점%c의 인접리스트", i +65);
p= g->adjList_H[i];
while(p){
printf(" -> %c", p->vertex +65);
p = p->link;
}
}
}

void DFS_adjList(graphType* g, int v)
{
graphNode* w;
top = NULL; //스택 top
push(v);
g->visited[v] = TRUE;
printf("%c", v +65);
while(top != NULL){
w=g->adjList_H[v];
while(w){ // 인접정점이 있는 동안 수행
if( !g->visited[w->vertex]){//방문하지 않은 인접정점에 대해서 수행

push(w->vertex);
g->visited[w->vertex] = TRUE;
printf(" %c", w->vertex +65); //정점 0~6을 A~G로 바꾸어서 출력
v = w->vertex;
w=g->adjList_H[v];
}
else= w->link;
}
v = pop(); //방문하지 않은 인접정점이 없으면 스택 pop!
}
}

void BFS_adjList(graphType* g, int v)
{
graphNode* w;
LQueueType* Q;  // 큐
Q = createLinkedQueue();
g->visited[v] = TRUE;
printf("%c", v +65);
enQueue(Q, v);
while(! isEmpty(Q)){
v=deQueue(Q);
for(w=g->adjList_H[v]; w; w=w->link) //인접 정점이 있는 동안 수행
if(!g->visited[w->vertex]){ //방문하지 않은 인접 정점에 대해 수행
g->visited[w->vertex] = TRUE;
printf("%c", w->vertex +65); //정점 0~6을 a~g로 바꾸어서 출력
enQueue(Q, w->vertex);
}
}
}

void main()
{
int i;
graphType *G9;
G9 = (graphType *)malloc(sizeof(graphType));

createGraph(G9);
for(i=0; i<7; i++)
     insertVertex(G9, i);
insertEdge(G9, 0, 2);
insertEdge(G9, 0, 1);
insertEdge(G9, 1, 4);
insertEdge(G9, 1, 3);
insertEdge(G9, 1, 0);
insertEdge(G9, 2, 4);
insertEdge(G9, 2, 0);
insertEdge(G9, 3, 6);
insertEdge(G9, 3, 1);
insertEdge(G9, 4, 6);
insertEdge(G9, 4, 2);
insertEdge(G9, 4, 1);
insertEdge(G9, 5, 6);
insertEdge(G9, 6, 5);
insertEdge(G9, 6, 4);
insertEdge(G9, 6, 3);
printf("\n G9의 인접 리스트");
print_adjList(G9);


printf("\n\n////////////\n\n 깊이우선탐색>>");
DFS_adjList(G9, 0);

printf("\n\n///////////\n\n 너비우선탐색>>");
BFS_adjList(G9, 0);

getchar();

}
신고
Trackback : 0 Comment : 0