dfs

#include<stdio.h>

#include<stdlib.h>

#define FALSE 0

#define TRUE 1

#define MAX_VERTICES 100

short visited[MAX_VERTICES];

typedef struct nod{

int vertex;

struct nod* link;

} node;

void dfs1(int v);

void dfs(int v);

node* graph[8];

node* head[8];

int main(void)

{

node* list;

int i;

for(i=0;i<8;i++)

{

graph[i] = (node*) malloc(sizeof(node));

head[i] = graph[i];

}

for(i=0;i<8;i++)

{

graph[i]->link = (node*) malloc(sizeof(node));

graph[i] = graph[i]->link;

}

graph[0]->vertex=1; graph[1]->vertex=0; graph[2]->vertex=0; graph[3]->vertex=1;

graph[4]->vertex=1; graph[5]->vertex=2; graph[6]->vertex=2; graph[7]->vertex=3;

for(i=0;i<8;i++)

{

graph[i]->link = (node*) malloc(sizeof(node));

graph[i] = graph[i]->link;

}

graph[0]->vertex=2; graph[1]->vertex=3; graph[2]->vertex=5; graph[3]->vertex=7;

graph[4]->vertex=7; graph[5]->vertex=7; graph[6]->vertex=7; graph[7]->vertex=4;

graph[0]->link = NULL;

for(i=3;i<=6;i++)

graph[i]->link = NULL;

graph[1]->link = (node*) malloc(sizeof(node));

graph[1] = graph[1]->link;

graph[1]->vertex = 4;

graph[1]->link = NULL;

graph[2]->link = (node*) malloc(sizeof(node));

graph[2] = graph[2]->link;

graph[2]->vertex = 6;

graph[2]->link = NULL;

graph[7]->link = (node*) malloc(sizeof(node));

graph[7] = graph[7]->link;

graph[7]->vertex = 5;

graph[7]->link = (node*) malloc(sizeof(node));

graph[7] = graph[7]->link;

graph[7]->vertex = 6;

graph[7]->link = NULL;

printf("recursive version : ");

dfs1(0);

printf("\n");

printf("interative version : ");

dfs(0);

printf("\n");

return 0;

}

void dfs1(int v)

{

node* w;

visited[v] = TRUE;

printf("%5d",v);

for(w = head[v]->link ; w ; w=w->link)

if(!visited[w->vertex])

dfs1(w->vertex);

}

void dfs(int v)

{

node* w;

int i,top=0,decide=1,a=0;

int stack[10];

visited[v] = TRUE;

printf("%5d",v);

stack[top++]=0;

for(w = head[v]->link ; ;)

{

for(i=0;i<top;i++)

if(stack[i]==w->vertex)

decide=0;

if(decide)

{

printf("%5d",w->vertex);

stack[top++] = w->vertex;

w = head[w->vertex];

}

if(w->link ==NULL)

w = head[stack[top-(++a)]];

if(top==8)

break;

w = w->link;

decide=1;

}

}