# Breadth- and Depth-first search code

Here is my breadth-first search (bfs) and depth-first search (dfs) code for graph traversal. Please give me some constructive reviews on it.

#include<stdio.h>
#include<stdlib.h>
#define null 0

typedef struct node//node of a linked list
{
struct vertex* info;//info part of node
struct node* next;// next pointer of a node
}*nodeptr;

typedef struct edge
{
int weight;
struct vertex * point;
struct edge *next;
}*eptr;

typedef struct vertex
{
int degree;
int info;
int status;
struct vertex * next;
struct edge *point;
struct vertex *parent;
}* vptr;

typedef struct graph
{
struct vertex *start;
int *directed;
}Graph;

typedef struct queue
{
nodeptr front;//front pointer of a queue
nodeptr rear;//rear pointer of a queue
} *QUEUE;

QUEUE qwe;

void insert_node(Graph *g,int x)
{
vptr p=(vptr)malloc(sizeof(struct vertex));
p->degree=0;
p->info=x;
p->point=null;
p->status=1;
p->next=g->start;
g->start=p;

return;
}

vptr find(vptr p,int x)
{
while(p!=null)
{
if(p->info==x)
return p;
p=p->next;
}
return null;
}

void insert_edge(Graph *g,int a,int b,int directed)
{
vptr loca;
vptr locb;
eptr p;
eptr q;
loca=find(g->start,a);
locb=find(g->start,b);

if(loca==null||locb==null)
{
printf("void insertion");
return;
}

p=loca->point;
q=null;

while(p!=null)
{
q=p;
p=p->next;
}

p=(eptr)malloc(sizeof(struct edge));
p->point=locb;
p->next=null;
if(q!=null)
q->next=p;
else
loca->point=p;
if(directed)
return;
else
insert_edge(g,b,a,1);
}

void delete_edge(Graph *g,int a,int b,int directed)
{
vptr loca=find(g->start,a);
vptr locb=find(g->start,b);
eptr p=loca->point;
eptr q=null;
while(p->point!=locb)
{
q=p;
p=p->next;
}
if (q==null)
loca->point=null;
else
q->next=p->next;
free(p);
return;
}

void process_vertex_early(vptr x)
{
printf("%d ",x->info);
}

void process_vertex_late(vptr x)
{

}

void process_edge(vptr x,vptr y)
{
//printf("%d %d\n",x->info,y->info);
}

int empty_queue()//if queue is empty then return 1
{
if (qwe->front==null)
return 1;
else
return 0;
}

void insert_queue(vptr x)
{
nodeptr p=(nodeptr)malloc(sizeof(struct node));//allocate new memory space to be added to queue
p->next=null;
p->info=x;
if(empty_queue())//if the queue is empty,front and rear point to the new node
{
qwe->rear=p;
qwe->front=p;
return;
}
qwe->rear->next=p;
qwe->rear=p;
//rear points to the new node
return;
}

vptr delete_queue()
{
vptr x;

if(empty_queue())//if queue is empty then it is the condition for underflow
{
printf("underflow\n");
return;
}

nodeptr p=qwe->front;//p points to node to be deleted
x=p->info;//x is the info to be returned
qwe->front=p->next;

if(qwe->front==null)//if the single element present was deleted
qwe->rear=null;

free(p);
return x;
}


BFS

void bfs(Graph *g)
{
vptr q=g->start;
vptr x;
vptr y;
eptr p;
while(q!=null)
{
q->status=1;
q=q->next;
}
g->start->status=2;
insert_queue(g->start);

while(!(empty_queue()))
{
x=delete_queue();
process_vertex_early(x);
x->status=3;
p=x->point;

while(p!=null)
{
y=p->point;

if(y->status!=3||g->directed)
process_edge(x,y);

if(y->status==1)
{
y->status=2;
y->parent=x;
insert_queue(y);
}

p=p->next;
}
process_vertex_late(x);
}
return;
}


DFS

void dfs(Graph *g,vptr x)
{
//  if(finished)return;
//  x->entry_time=++time;
eptr p=x->point;
vptr y;
process_vertex_early(x);

while(p!=null)
{
y=p->point;

if(y->status==1)
{
process_edge(x,y);
y->status=2;
y->parent=x;
dfs(g,y);
}

else if((y->status==2&&x->parent!=y||g->directed))
{
process_edge(x,y);
}
//  if(finished)return;
p=p->next;
}

process_vertex_late(x);
x->status=3;
//x->exit_time=++time;
return;
}

• I can understand how your graph hangs together. You will need to add comments the describe how node/edge/vertex/graph hang together to build a graph. – Martin York Dec 30 '12 at 20:25
• Have you tested it at all? In delete_edge you have if (q=null) which your compiler should warn you about. – William Morris Dec 30 '12 at 23:26
• yesyes (q=null) should be (q==null) – abhay jain Dec 31 '12 at 6:25
• But did you test it? I would expect that sort of error to turn up quite quickly in tests (quite apart from the compiler telling you of it). – William Morris Dec 31 '12 at 17:12
• It would be easier to review this code if there was an example main() program that created a graph and then ran the traversal functions over it. It is a lot harder to work out what's required and expected when you don't provide an SSCCE (Short, Self-Contained, Correct Example). – Jonathan Leffler Jan 1 '13 at 7:44

Some comments, in no particular order:

You are inconsistent in spacing and in positioning of '*', which makes the code look rather scrappy.

It is generally less confusing not to hide pointers behind type definitions. Admittedly you use 'ptr' in the type names, so this lessens the harm. But when I compare your definition and use of eptr:

typedef struct edge
{
...
}*eptr;

// function:
{
eptr p;


to a more normal:

typedef struct edge
{
...
} Edge;

// function:
{
Edge *e;


I have no hesitation in saying the latter is more easily understood (bearing in mind that the function will probably not be near to (or even in the same file as) the definition.

Also on types, your QUEUE would be better written Queue as upper case names are usually kept for #define constants.

Other issues

• don't cast the return of malloc. This can be harmful and is never necessary in C. Also check the return from malloc is not NULL and handle such failures.

• add spaces around operators ('==', '=', etc)

• indent the code properly

• using braces around single line statements avoids some common errors.

• empty_queue is badly named. Prefer is_empty or something indicating that the return is a truth value. Also empty_queue and delete_queue should have a void parameter list.

• delete_queue seems to delete on entry from the queue, not the whole queue as its name would suggest.

• delete_edge does not use its parameter directed.

• process_vertex_early, process_vertex_late and process_edge appear to be unfinished.

• bfs has three while loops. That is seldom necessary and indicates that you could extract some of the functionality to separate helper functions and hence make the function more understandable.

• both dfs and bfs call incomplete functions process_vertex_early and process_vertex_late, which makes me think this code is generally incomplete.