Example 1: python breadth first search
# tree level-by-level traversal. O(n) time/space
def breadthFirstSearch(root):
q = [root]
while q:
current = q.pop(0)
print(current)
if current.left is not None: q.append(current.left)
if current.right is not None: q.append(current.right)
Example 2: breadth first traversal python program
class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}
def add_vertex(self, key):
"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex
def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]
def __contains__(self, key):
return key in self.vertices
def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with given weight."""
self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}
def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key
def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight
def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()
def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]
def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, data):
self.items.append(data)
def dequeue(self):
return self.items.pop(0)
def display_bfs(vertex):
"""Display BFS Traversal starting at vertex."""
visited = set()
q = Queue()
q.enqueue(vertex)
visited.add(vertex)
while not q.is_empty():
current = q.dequeue()
print(current.get_key(), end=' ')
for dest in current.get_neighbours():
if dest not in visited:
visited.add(dest)
q.enqueue(dest)
g = Graph()
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest>')
print('bfs <vertex key>')
print('display')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0]
if operation == 'add':
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
g.add_vertex(key)
else:
print('Vertex already exists.')
elif suboperation == 'edge':
src = int(do[2])
dest = int(do[3])
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
g.add_edge(src, dest)
else:
print('Edge already exists.')
elif operation == 'bfs':
key = int(do[1])
print('Breadth-first Traversal: ', end='')
vertex = g.get_vertex(key)
display_bfs(vertex)
print()
elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()
print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()
elif operation == 'quit':
break
Example 3: bfs traversal of graph in c
#include <stdio.h>
#include <stdlib.h>
#define SIZE 40
struct queue {
int items[SIZE];
int front;
int rear;
};
struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
int* visited;
};
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
void printQueue(struct queue* q) {
int i = q->front;
if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}
int main() {
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
bfs(graph, 0);
return 0;
}
Example 4: BFS in c++
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::BFS(int s)
{
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
list<int> queue;
visited[s] = true;
queue.push_back(s);
list<int>::iterator i;
while(!queue.empty())
{
s = queue.front();
cout << s << " ";
queue.pop_front();
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) \n";
g.BFS(2);
return 0;
}
Example 5: breadth first search
procedure BFS(G, start_v) is
2 let Q be a queue
3 label start_v as discovered
4 Q.enqueue(start_v)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 w.parent := v
13 Q.enqueue(w)
Example 6: bfs
function breadthFirstSearch (Start, Goal)
{
enqueue(Queue,Start)
setVisited(start)
while notEmpty(Queue)
{
Node := dequeue(Queue)
if Node = Goal
{
return Node
}
for each Child in Expand(Node)
{
if notVisited(Child)
{
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}