Home > Articles, Data Structures & Algorithms > Implementation of breadth-first search algorithm in graphs.

Implementation of breadth-first search algorithm in graphs.

The following function is applied onto a graph and it specifically implements the method of breadth-first search. To visit all nodes connected to node k of a graph, we put the k in a FIFO queue and then go into a loop, during which we get the next node from the queue and, if we have not already visited it, we visit it and push into the queue all nodes belonging to the adjacency list of this node, continuing this process until we empty the queue.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

void
traverse (int k, void visit (int)) {
  QUEUE<int> q (V*V);

  q.put (k);

  while (!q.empty ()) {
    if (visited[k = q.get ()] == 0) {
      visit (k); visited[k] = 1;
      for (link t = adj[k]; t != 0; t = t->next)
        if (visited[t->v] == 0)
          q.put (t->v);
    }
  }
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: