How to study graph data structures and BFS & DFS

Question

I am studying data structures recently, and I have trouble here in graph. I read this book: Data Structures and Algorithm Analysis in C (2nd Edition).

In fact I also read some other algorithm books and I found that almost no book gives me a full implementation of graph. Though I can read pseudocode and understand how BFS and DFS run, and some other algorithms used in graph to solve problems, I still want a full implementation helping me better understand how it works. However, is it unimportant to write code here in studying graph? I'm not sure.

Also, I found some ACM questions about BFS and DFS. I don't know how to express, but it seems BFS and DFS are only ideas to solve them, they do not write a standard BFS code. So this make me trouble studying data structures.

I'm sorry for my poor expression, I'm a international student in the US now.

At last, I copied this code from Mastering Algorithms with C and analyzed it. But I still cannot understand a part of it. And here is part of code:

typedef struct BfsVertex_ {
    void *data;
    VertexColor color;
    int hops;
} BfsVertex;

typedef struct AdjList_ {
    void *vertex;
    Set adjacent;
} AdjList;

typedef struct Graph_ {
    int  vcount;
    int  ecount;
    List adjlists;
    int  (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
} Graph;

int BFS(Graph *graph, BfsVertex *start, List *hops) {

    Queue     queue;
    AdjList   *adjlist, *clr_adjlist;
    BfsVertex *clr_vertex, *adj_vertex;
    ListElem  *element, *member;

    /* init all of the vertices in the graph */
    for (element = list_head(&graph_adjlists(graph));
         element != NULL;
         element = list_next(element)) {

        clr_vertex = ((AdjList *)list_data(element))->vertex;

        if (graph->match(clr_vertex, start)) {
            clr_vertex->color = gray;
            clr_vertex->hops = 0;
        } else {
            clr_vertex = white;
            clr_vertex->hops = -1;
        }
    }

    /* init the queue with the adjacency list of the start vertex */
    queue_init(&queue, NULL);
    if (graph_adjlist(graph, start, &clr_adjlist) != 0) {
        queue_destroy(&queue);
        return -1;
    }

    if (queue_enqueue(&queue, clr_adjlist) != 0) {
        queue_destroy(&queue);
        return -1;
    }

    /* perform Breadth-First Search */
    while (queue_size(&queue) > 0) {

        adjlist = queue_peek(&queue);

        /* traverse each vertex in the current adjacency list */
        for (member = list_head(&adjlist->adjacent);
             member != NULL;
             member = list_next(member)) {

            adj_vertex = list_data(member);

            /* determine the color of the next adjacent vertex */
            if (graph_adjlist(graph, adj_vertex, &clr_adjlist) != 0) {
                queue_destroy(&queue);
                return -1;
            }
            clr_vertex = clr_adjlist->vertex;

            /* color each white vertex gray and enqueue its adjacency list */
            if (clr_vertex->color == white) {
                clr_vertex->color = gray;
                clr_vertex->hops = ((BfsVertex *)adjlist->vertex)->hops + 1;

                if (queue_enqueue(&queue, clr_adjlist) != 0) {
                    queue_destroy(&queue);
                    return -1;
                }
            }
        }

        /* dequeue the current adjacency list and color its vertex black */
        if (queue_dequeue(&queue, (void **)&adjlist) == 0) {
            ((BfsVertex *)adjlist->vertex)->color = black;
        } else {
            queue_destroy(&queue);
            return -1;
        }
    }

    queue_destroy(&queue);

    /* pass back the hop count for each vertex in a list */
    list_init(hops, NULL);

    for (element = list_head(&graph_adjlists(graph));
         element != NULL;
         element = list_next(element)) {

        /* skip vertices that were not visited (those with hop counts of -1) */
        clr_vertex = ((AdjList *)list_data(element))->vertex;
        if (clr_vertex->hops != -1) {
            if (list_ins_next(hops, list_tail(hops), clr_vertex) != 0) {
                list_destroy(hops);
                return -1;
            }
        }
    }

    return 0;
}

I had trouble here: how this initialization works? It traverses the adjacency list of the graph, and assigns the colored vertex each vertex in the graph. But after coloring, the clr_vertex changed its object, how that color and distance information are saved?

 /* init all of the vertices in the graph */
        for (element = list_head(&graph_adjlists(graph));
             element != NULL;
             element = list_next(element)) {

            clr_vertex = ((AdjList *)list_data(element))->vertex;

            if (graph->match(clr_vertex, start)) {
                clr_vertex->color = gray;
                clr_vertex->hops = 0;
            } else {
                clr_vertex = white;
                clr_vertex->hops = -1;
            }
        }

Thank you for reading such a long question.

Answer 1

How to study graph data structures and BFS & DFS

one word: Abstractly.

You need to understand them regardless of the programming language. All you need is a pen and a paper. This would make it crystal clear when it comes to implementation. Graphs are meant to be abstract objects where the choice of prog. language is irrelevant to the concepts.

I still want a full implementation helping me better understand how it works.

DFS and BFS are just two different ways to traverse (i.e., walk over) the graph. No more No less. The result of this walking is what's called search tree in the literature. The full implementation is as follows:

1. Run DFS and BFS on small graphs by hand. (This would return a search tree)

2. Check it against your implementation.

Certainly, these are too general techniques. When it comes to practice, you can modify them combine other techniques or do whatever you want with them. For now, you can see them as DFS=Stack, BFS=Queue