python breadth first search

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}