In C

/* Do the list-based BFS, given the source node and the graph's adjacency list. Go through each vertices in a BFS manner, and then calculate the dsitance from the source vertex. input parameters: The following are 'consumed' by this function adj_node_t** list adjacency list for the graph int rows number of rows/vertices in the graph int source BFS source

The following are 'produced' by this function int* color keeps track of color during BFS int* distance distance from the source int* parent parent of each vertex return parameters: none */ void bfs(adj_node_t** list, int rows, int source, int* color, int* distance, int* parent) { // Make sure the source is a valid vertex if(source >= rows) { fprintf(stderr, "Invalid source vertex "); exit(EXIT_FAILURE); } // Make sure the adjacency list is not NULL // Even if this is a completely unconnected graph, // it should still NOT be NULL (see init_adj_list) if(list == NULL) { fprintf(stderr, "There is nothing in the adjacency list "); exit(EXIT_FAILURE); } // Make sure all these are properly allocated (i.e., not NULL) assert(color); assert(distance); assert(parent);

fprintf(stdout, "Breadth first search on the grahp using linked list ... ");

// INSERT YOUR CODE HERE

// Initialize the vertices // color should be initialized to 0 // distance should be initialized to -1 for infinity // parent should be initialized to -1 for NIL

// Initialize the source vertex // distance for the source vertex is 0, so it should be initialized as such // it has no parent, so initialize it to -1 // color should be initialized to 1

// Initialize the queue with the source vertex // HINT: use create_node(source) and add_node

// bfs iteration // HINT: use remove_node (to fetch & dequeu the vertex) // HINT: you will also need create_node an add_node here

fprintf(stdout, "done ");

#if DEBUG print_bfs_result(rows, color, distance, parent); #endif }