1# tree level-by-level traversal. O(n) time/space
2def breadthFirstSearch(root):
3 q = [root]
4
5 while q:
6 current = q.pop(0)
7 print(current)
8 if current.left is not None: q.append(current.left)
9 if current.right is not None: q.append(current.right)
1class Graph:
2 def __init__(self):
3 # dictionary containing keys that map to the corresponding vertex object
4 self.vertices = {}
5
6 def add_vertex(self, key):
7 """Add a vertex with the given key to the graph."""
8 vertex = Vertex(key)
9 self.vertices[key] = vertex
10
11 def get_vertex(self, key):
12 """Return vertex object with the corresponding key."""
13 return self.vertices[key]
14
15 def __contains__(self, key):
16 return key in self.vertices
17
18 def add_edge(self, src_key, dest_key, weight=1):
19 """Add edge from src_key to dest_key with given weight."""
20 self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
21
22 def does_edge_exist(self, src_key, dest_key):
23 """Return True if there is an edge from src_key to dest_key."""
24 return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
25
26 def __iter__(self):
27 return iter(self.vertices.values())
28
29
30class Vertex:
31 def __init__(self, key):
32 self.key = key
33 self.points_to = {}
34
35 def get_key(self):
36 """Return key corresponding to this vertex object."""
37 return self.key
38
39 def add_neighbour(self, dest, weight):
40 """Make this vertex point to dest with given edge weight."""
41 self.points_to[dest] = weight
42
43 def get_neighbours(self):
44 """Return all vertices pointed to by this vertex."""
45 return self.points_to.keys()
46
47 def get_weight(self, dest):
48 """Get weight of edge from this vertex to dest."""
49 return self.points_to[dest]
50
51 def does_it_point_to(self, dest):
52 """Return True if this vertex points to dest."""
53 return dest in self.points_to
54
55
56class Queue:
57 def __init__(self):
58 self.items = []
59
60 def is_empty(self):
61 return self.items == []
62
63 def enqueue(self, data):
64 self.items.append(data)
65
66 def dequeue(self):
67 return self.items.pop(0)
68
69
70def display_bfs(vertex):
71 """Display BFS Traversal starting at vertex."""
72 visited = set()
73 q = Queue()
74 q.enqueue(vertex)
75 visited.add(vertex)
76 while not q.is_empty():
77 current = q.dequeue()
78 print(current.get_key(), end=' ')
79 for dest in current.get_neighbours():
80 if dest not in visited:
81 visited.add(dest)
82 q.enqueue(dest)
83
84
85g = Graph()
86print('Menu')
87print('add vertex <key>')
88print('add edge <src> <dest>')
89print('bfs <vertex key>')
90print('display')
91print('quit')
92
93while True:
94 do = input('What would you like to do? ').split()
95
96 operation = do[0]
97 if operation == 'add':
98 suboperation = do[1]
99 if suboperation == 'vertex':
100 key = int(do[2])
101 if key not in g:
102 g.add_vertex(key)
103 else:
104 print('Vertex already exists.')
105 elif suboperation == 'edge':
106 src = int(do[2])
107 dest = int(do[3])
108 if src not in g:
109 print('Vertex {} does not exist.'.format(src))
110 elif dest not in g:
111 print('Vertex {} does not exist.'.format(dest))
112 else:
113 if not g.does_edge_exist(src, dest):
114 g.add_edge(src, dest)
115 else:
116 print('Edge already exists.')
117
118 elif operation == 'bfs':
119 key = int(do[1])
120 print('Breadth-first Traversal: ', end='')
121 vertex = g.get_vertex(key)
122 display_bfs(vertex)
123 print()
124
125 elif operation == 'display':
126 print('Vertices: ', end='')
127 for v in g:
128 print(v.get_key(), end=' ')
129 print()
130
131 print('Edges: ')
132 for v in g:
133 for dest in v.get_neighbours():
134 w = v.get_weight(dest)
135 print('(src={}, dest={}, weight={}) '.format(v.get_key(),
136 dest.get_key(), w))
137 print()
138
139 elif operation == 'quit':
140 break
1// BFS algorithm in C
2
3#include <stdio.h>
4#include <stdlib.h>
5#define SIZE 40
6
7struct queue {
8 int items[SIZE];
9 int front;
10 int rear;
11};
12
13struct queue* createQueue();
14void enqueue(struct queue* q, int);
15int dequeue(struct queue* q);
16void display(struct queue* q);
17int isEmpty(struct queue* q);
18void printQueue(struct queue* q);
19
20struct node {
21 int vertex;
22 struct node* next;
23};
24
25struct node* createNode(int);
26
27struct Graph {
28 int numVertices;
29 struct node** adjLists;
30 int* visited;
31};
32
33// BFS algorithm
34void bfs(struct Graph* graph, int startVertex) {
35 struct queue* q = createQueue();
36
37 graph->visited[startVertex] = 1;
38 enqueue(q, startVertex);
39
40 while (!isEmpty(q)) {
41 printQueue(q);
42 int currentVertex = dequeue(q);
43 printf("Visited %d\n", currentVertex);
44
45 struct node* temp = graph->adjLists[currentVertex];
46
47 while (temp) {
48 int adjVertex = temp->vertex;
49
50 if (graph->visited[adjVertex] == 0) {
51 graph->visited[adjVertex] = 1;
52 enqueue(q, adjVertex);
53 }
54 temp = temp->next;
55 }
56 }
57}
58
59// Creating a node
60struct node* createNode(int v) {
61 struct node* newNode = malloc(sizeof(struct node));
62 newNode->vertex = v;
63 newNode->next = NULL;
64 return newNode;
65}
66
67// Creating a graph
68struct Graph* createGraph(int vertices) {
69 struct Graph* graph = malloc(sizeof(struct Graph));
70 graph->numVertices = vertices;
71
72 graph->adjLists = malloc(vertices * sizeof(struct node*));
73 graph->visited = malloc(vertices * sizeof(int));
74
75 int i;
76 for (i = 0; i < vertices; i++) {
77 graph->adjLists[i] = NULL;
78 graph->visited[i] = 0;
79 }
80
81 return graph;
82}
83
84// Add edge
85void addEdge(struct Graph* graph, int src, int dest) {
86 // Add edge from src to dest
87 struct node* newNode = createNode(dest);
88 newNode->next = graph->adjLists[src];
89 graph->adjLists[src] = newNode;
90
91 // Add edge from dest to src
92 newNode = createNode(src);
93 newNode->next = graph->adjLists[dest];
94 graph->adjLists[dest] = newNode;
95}
96
97// Create a queue
98struct queue* createQueue() {
99 struct queue* q = malloc(sizeof(struct queue));
100 q->front = -1;
101 q->rear = -1;
102 return q;
103}
104
105// Check if the queue is empty
106int isEmpty(struct queue* q) {
107 if (q->rear == -1)
108 return 1;
109 else
110 return 0;
111}
112
113// Adding elements into queue
114void enqueue(struct queue* q, int value) {
115 if (q->rear == SIZE - 1)
116 printf("\nQueue is Full!!");
117 else {
118 if (q->front == -1)
119 q->front = 0;
120 q->rear++;
121 q->items[q->rear] = value;
122 }
123}
124
125// Removing elements from queue
126int dequeue(struct queue* q) {
127 int item;
128 if (isEmpty(q)) {
129 printf("Queue is empty");
130 item = -1;
131 } else {
132 item = q->items[q->front];
133 q->front++;
134 if (q->front > q->rear) {
135 printf("Resetting queue ");
136 q->front = q->rear = -1;
137 }
138 }
139 return item;
140}
141
142// Print the queue
143void printQueue(struct queue* q) {
144 int i = q->front;
145
146 if (isEmpty(q)) {
147 printf("Queue is empty");
148 } else {
149 printf("\nQueue contains \n");
150 for (i = q->front; i < q->rear + 1; i++) {
151 printf("%d ", q->items[i]);
152 }
153 }
154}
155
156int main() {
157 struct Graph* graph = createGraph(6);
158 addEdge(graph, 0, 1);
159 addEdge(graph, 0, 2);
160 addEdge(graph, 1, 2);
161 addEdge(graph, 1, 4);
162 addEdge(graph, 1, 3);
163 addEdge(graph, 2, 4);
164 addEdge(graph, 3, 4);
165
166 bfs(graph, 0);
167
168 return 0;
169}
1#include<iostream>
2#include <list>
3
4using namespace std;
5
6
7
8class Graph
9{
10 int V;
11
12
13 list<int> *adj;
14public:
15 Graph(int V);
16
17
18 void addEdge(int v, int w);
19
20
21 void BFS(int s);
22};
23
24Graph::Graph(int V)
25{
26 this->V = V;
27 adj = new list<int>[V];
28}
29
30void Graph::addEdge(int v, int w)
31{
32 adj[v].push_back(w);
33}
34
35void Graph::BFS(int s)
36{
37
38 bool *visited = new bool[V];
39 for(int i = 0; i < V; i++)
40 visited[i] = false;
41
42
43 list<int> queue;
44
45
46 visited[s] = true;
47 queue.push_back(s);
48
49
50 list<int>::iterator i;
51
52 while(!queue.empty())
53 {
54
55 s = queue.front();
56 cout << s << " ";
57 queue.pop_front();
58
59
60 for (i = adj[s].begin(); i != adj[s].end(); ++i)
61 {
62 if (!visited[*i])
63 {
64 visited[*i] = true;
65 queue.push_back(*i);
66 }
67 }
68 }
69}
70
71
72int main()
73{
74
75 Graph g(4);
76 g.addEdge(0, 1);
77 g.addEdge(0, 2);
78 g.addEdge(1, 2);
79 g.addEdge(2, 0);
80 g.addEdge(2, 3);
81 g.addEdge(3, 3);
82
83 cout << "Following is Breadth First Traversal "
84 << "(starting from vertex 2) \n";
85 g.BFS(2);
86
87 return 0;
88}