#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 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;
}
}
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 dfs(GraphType* g, int v)
{
GraphNode* w;
g->visited[v] =TRUE;
printf("%-2d" , v);
for(w=g->adjList_H[v]; w; w =w->link)
if(!g->visited[w->vertex])
dfs(g,w->vertex);
}
void dfsAdjList(GraphType* g, int v)
{
GraphNode* w;
top = NULL;
push(v);
g->visited[v] =TRUE;
printf("%-2d" , v);
while(top!=NULL){
w=g->adjList_H[v];
while(w){
if(!g->visited[w->vertex]){
push(w->vertex);
g->visited[w->vertex] =TRUE;
printf("%-2d", w->vertex);
v=w->vertex;
w=g->adjList_H[v];
}
else w=w->link;
}
v=pop();
}
}
void ini(GraphType *g)
{
int i;
for(i=0; i<MAX_VERTEX; i++)
g->visited[i]=0;
}
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);
dfs(G,0);
ini(G);
printf("\n\n깊이우선 탐색>> ");
dfsAdjList(G,0);
printf("\n");
}