C sourcde code from Wikipedia

[thanhthanh]

I got these source code from Wikipedia
http://en.wikipedia.org/wiki/Breadth-first_search
They are about Bread first search of graph.Any one know about that?
I quote it here
Algorithm (informal)

1. Put the ending node (the root node) in the queue.
2. Pull a node from the beginning of the queue and examine it.
* If the searched element is found in this node, quit the search and return a result.
* Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
4. Repeat from Step 2.

Note: Using a stack instead of a queue to store the nodes yet to be visited would turn this algorithm into a Depth-first search.

[edit] C implementation

Algorithm of Breadth-first search：

void BFS(VLink G[], int v) {
int w;
VISIT(v); /*visit vertex v*/
visited[v] = 1; /*mark v as visited : 1 */
ADDQ(Q,v);
while(!QMPTYQ(Q)) {
v = DELQ(Q); /*Dequeue v*/
w = FIRSTADJ(G,v); /*Find first neighbor, return -1 if no neighbor*/
while(w != -1) {
if(visited[w] == 0) {
VISIT(w); /*visit vertex v*/
ADDQ(Q,w); /*Enqueue current visited vertext w*/
visited[w] = 1; /*mark w as visited*/
}
W = NEXTADJ(G,v); /*Find next neighbor, return -1 if no neighbor*/
}
}
}

Main Algorithm of apply Breadth-first search to graph G=(V,E)：

void TRAVEL_BFS(VLink G[], int visited[], int n) {
int i;
for(i = 0; i < n; i ++) {
visited[i] = 0; /* Mark initial value as 0 */
}
for(i = 0; i < n; i ++)
if(visited[i] == 0)
BFS(G,i);
}


I think that inforder to find out the neighbour of a vertex of a graph, the second parameter must be VLink like G,but ,here,it just an int.i don't know how to find the neighbour of a node if we just give the value.( int v)
void BFS(VLink G[], int v)
w = FIRSTADJ(G,v);
W = NEXTADJ(G,v);

[oracleguy]

It would depend on the exact implementation of your graph class.

But don't follow the code on wikipedia when writing your algorithm as much as the comments and steps outlined above the code. Follow those and you can write your own code that will work.

[thanhthanh]

It would depend on the exact implementation of your graph class.

But don't follow the code on wikipedia when writing your algorithm as much as the comments and steps outlined above the code. Follow those and you can write your own code that will work.
I think wikipedia is quite good for realiable information. Graph can be implemented by array or linked list,right?but here,they use linked list,graph is linked list too.

[ghell]

In most cases wikipedia is fine for reliable information. However, as oracleguy was saying, the comments there show you the process of what happens in general, so are more useful to you than the code which is very specific and dependant on how the graph is structured in your implementation, down to how many bytes you give for an edge weight, for example.

For example if you have no VISIT function, that code won't work at all.

Anyway, BFS isn't that complicated. The difference between DFS and BFS is that BFS uses a queue and DFS uses a stack to list which vertices to visit next.

iterative BFS (in some kind of pseudo code):
queue = {start vertex}
while(queue is not empty)
current node C = first value of the queue (remove from the queue as you take)
mark C visited
add all unvisited neighbours of C to a queue
do any processing to C you might need

EDIT: By the way, in C a linked list is pretty good for a queue (fast to append and delete from, slower to look up but you only ever need the first value in the queue anyway so this doesn't matter). In C++ there is a queue class in the STL. This is just for the algorithm's queue. To store the actual graph data you can use any data type you want. If it remains a fixed size or the size rarely changes, use an array.