Breadth- and Depth-first search code

Question

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;
}

Answer 1

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.