-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathbreadth-first-search.html
More file actions
301 lines (267 loc) · 70.1 KB
/
breadth-first-search.html
File metadata and controls
301 lines (267 loc) · 70.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Breadth-First Search</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Finding the Shortest Path from Source to other Nodes, Finding Shortest Path from Source in a 2D graph, Connected Components Of Undirected Graph Using BFS.">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Breadth-First Search">
<meta property="og:description" content="Finding the Shortest Path from Source to other Nodes, Finding Shortest Path from Source in a 2D graph, Connected Components Of Undirected Graph Using BFS.">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/breadth-first-search.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Breadth-First Search">
<meta name="twitter:description" content="Finding the Shortest Path from Source to other Nodes, Finding Shortest Path from Source in a 2D graph, Connected Components Of Undirected Graph Using BFS.">
<meta name="twitter:url" content="/algorithm/breadth-first-search.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/21.0a6a3974.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" aria-current="page" class="active sidebar-link">Breadth-First Search</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/breadth-first-search.html#finding-the-shortest-path-from-source-to-other-nodes" class="sidebar-link">Finding the Shortest Path from Source to other Nodes</a></li><li class="sidebar-sub-header"><a href="/algorithm/breadth-first-search.html#finding-shortest-path-from-source-in-a-2d-graph" class="sidebar-link">Finding Shortest Path from Source in a 2D graph</a></li><li class="sidebar-sub-header"><a href="/algorithm/breadth-first-search.html#connected-components-of-undirected-graph-using-bfs" class="sidebar-link">Connected Components Of Undirected Graph Using BFS.</a></li></ul></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="breadth-first-search"><a href="#breadth-first-search" class="header-anchor">#</a> Breadth-First Search</h1> <h2 id="finding-the-shortest-path-from-source-to-other-nodes"><a href="#finding-the-shortest-path-from-source-to-other-nodes" class="header-anchor">#</a> Finding the Shortest Path from Source to other Nodes</h2> <p><a href="https://en.wikipedia.org/wiki/Breadth-first_search" target="_blank" rel="noopener noreferrer">Breadth-first-search<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors. BFS was invented in the late 1950s by <a href="https://en.wikipedia.org/wiki/Edward_F._Moore" target="_blank" rel="noopener noreferrer">Edward Forrest Moore<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>, who used it to find the shortest path out of a maze and discovered independently by C. Y. Lee as a wire routing algorithm in 1961.</p> <p>The processes of BFS algorithm works under these assumptions:</p> <ol><li>We won't traverse any node more than once.</li> <li>Source node or the node that we're starting from is situated in level 0.</li> <li>The nodes we can directly reach from source node are level 1 nodes, the nodes we can directly reach from level 1 nodes are level 2 nodes and so on.</li> <li>The level denotes the distance of the shortest path from the source.</li></ol> <p>Let's see an example:
<a href="http://i.stack.imgur.com/LrC21.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/LrC21.png" alt="Example Graph"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Let's assume this graph represents connection between multiple cities, where each node denotes a city and an edge between two nodes denote there is a road linking them. We want to go from <strong>node 1</strong> to <strong>node 10</strong>. So <strong>node 1</strong> is our <strong>source</strong>, which is <strong>level 0</strong>. We mark <strong>node 1</strong> as visited. We can go to <strong>node 2</strong>, <strong>node 3</strong> and <strong>node 4</strong> from here. So they'll be <strong>level (0+1)</strong> = <strong>level 1</strong> nodes. Now we'll mark them as visited and work with them.</p> <p><a href="http://i.stack.imgur.com/Wwcte.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/Wwcte.png" alt="Visited source and level 1"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The colored nodes are visited. The nodes that we're currently working with will be marked with pink. We won't visit the same node twice. From <strong>node 2</strong>, <strong>node 3</strong> and <strong>node 4</strong>, we can go to <strong>node 6,</strong> <strong>node 7</strong> and <strong>node 8</strong>. Let's mark them as visited. The level of these nodes will be <strong>level (1+1)</strong> = <strong>level 2</strong>. <a href="http://i.stack.imgur.com/Ns886.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/Ns886.png" alt="Visited Source and level 2"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>If you haven't noticed, the level of nodes simply denote the shortest path distance from the <strong>source</strong>. For example: we've found <strong>node 8</strong> on <strong>level 2</strong>. So the distance from <strong>source</strong> to <strong>node 8</strong> is <strong>2</strong>.</p> <p>We didn't yet reach our target node, that is <strong>node 10</strong>. So let's visit the next nodes. we can directly go to from <strong>node 6</strong>, <strong>node 7</strong> and <strong>node 8</strong>.<a href="http://i.stack.imgur.com/XdE7c.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/XdE7c.png" alt="Visited level 3"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>We can see that, we found <strong>node 10</strong> at <strong>level 3</strong>. So the shortest path from <strong>source</strong> to <strong>node 10</strong> is <strong>3.</strong> We searched the graph level by level and found the shortest path. Now let's erase the edges that we didn't use: <a href="http://i.stack.imgur.com/AaVRF.png" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/AaVRF.png" alt="BFS tree"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>After removing the edges that we didn't use, we get a tree called BFS tree. This tree shows the shortest path from <strong>source</strong> to all other nodes.</p> <p>So our task will be, to go from <strong>source</strong> to <strong>level 1</strong> nodes. Then from <strong>level 1</strong> to <strong>level 2</strong> nodes and so on until we reach our destination. We can use <strong>queue</strong> to store the nodes that we are going to process. That is, for each node we're going to work with, we'll push all other nodes that can be directly traversed and not yet traversed in the queue.</p> <p>The simulation of our example:</p> <p>First we push the source in the queue. Our queue will look like:</p> <div class="language- extra-class"><pre class="language-text"><code>
front
+-----+
| 1 |
+-----+
</code></pre></div><p>The level of <strong>node 1</strong> will be 0. <strong>level[1]</strong> = <strong>0</strong>. Now we start our BFS. At first, we pop a node from our queue. We get <strong>node 1</strong>. We can go to <strong>node 4</strong>, <strong>node 3</strong> and <strong>node 2</strong> from this one. We've reached these nodes from <strong>node 1</strong>. So <strong>level[4]</strong> = <strong>level[3]</strong> = <strong>level[2]</strong> = <strong>level[1]</strong> + <strong>1</strong> = <strong>1</strong>. Now we mark them as visited and push them in the queue.</p> <div class="language- extra-class"><pre class="language-text"><code>
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
</code></pre></div><p>Now we pop <strong>node 4</strong> and work with it. We can go to <strong>node 7</strong> from <strong>node 4</strong>. <strong>level[7]</strong> = <strong>level[4]</strong> + <strong>1</strong> = <strong>2</strong>. We mark <strong>node 7</strong> as visited and push it in the queue.</p> <div class="language- extra-class"><pre class="language-text"><code>
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
</code></pre></div><p>From <strong>node 3</strong>, we can go to <strong>node 7</strong> and <strong>node 8</strong>. Since we've already marked <strong>node 7</strong> as visited, we mark <strong>node 8</strong> as visited, we change <strong>level[8]</strong> = <strong>level[3]</strong> + <strong>1</strong> = <strong>2</strong>. We push <strong>node 8</strong> in the queue.</p> <div class="language- extra-class"><pre class="language-text"><code>
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
</code></pre></div><p>This process will continue till we reach our destination or the queue becomes empty. The <strong>level</strong> array will provide us with the distance of the shortest path from <strong>source</strong>. We can initialize <strong>level</strong> array with <strong>infinity</strong> value, which will mark that the nodes are not yet visited. Our pseudo-code will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Procedure <span class="token function">BFS</span><span class="token punctuation">(</span>Graph<span class="token punctuation">,</span> source<span class="token punctuation">)</span><span class="token operator">:</span>
Q <span class="token operator">=</span> <span class="token function">queue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
level<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> infinity
level<span class="token punctuation">[</span>source<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> <span class="token number">0</span>
Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>source<span class="token punctuation">)</span>
<span class="token keyword">while</span> Q is <span class="token operator">not</span> empty
u <span class="token operator">-></span> Q<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token keyword">for</span> all edges from u to v in Adjacency list
<span class="token keyword">if</span> level<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">==</span> infinity
level<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> level<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span>
Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span>
end <span class="token keyword">if</span>
end <span class="token keyword">for</span>
end <span class="token keyword">while</span>
Return level
</code></pre></div><p>By iterating through the <strong>level</strong> array, we can find out the distance of each node from source. For example: the distance of <strong>node 10</strong> from <strong>source</strong> will be stored in <strong>level[10]</strong>.</p> <p>Sometimes we might need to print not only the shortest distance, but also the path via which we can go to our destined node from the <strong>source</strong>. For this we need to keep a <strong>parent</strong> array. <strong>parent[source]</strong> will be NULL. For each update in <strong>level</strong> array, we'll simply add <code>parent[v] := u</code> in our pseudo code inside the for loop. After finishing BFS, to find the path, we'll traverse back the <strong>parent</strong> array until we reach <strong>source</strong> which will be denoted by NULL value. The pseudo-code will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Procedure <span class="token function">PrintPath</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token comment">//recursive | Procedure PrintPath(u): //iterative</span>
<span class="token keyword">if</span> parent<span class="token punctuation">[</span>u<span class="token punctuation">]</span> is <span class="token operator">not</span> equal to null <span class="token operator">|</span> S <span class="token operator">=</span> <span class="token function">Stack</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token function">PrintPath</span><span class="token punctuation">(</span>parent<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">|</span> <span class="token keyword">while</span> parent<span class="token punctuation">[</span>u<span class="token punctuation">]</span> is <span class="token operator">not</span> equal to null
end <span class="token keyword">if</span> <span class="token operator">|</span> S<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span>
print <span class="token operator">-></span> u <span class="token operator">|</span> u <span class="token operator">:</span><span class="token operator">=</span> parent<span class="token punctuation">[</span>u<span class="token punctuation">]</span>
<span class="token operator">|</span> end <span class="token keyword">while</span>
<span class="token operator">|</span> <span class="token keyword">while</span> S is <span class="token operator">not</span> empty
<span class="token operator">|</span> print <span class="token operator">-></span> S<span class="token punctuation">.</span>pop
<span class="token operator">|</span> end <span class="token keyword">while</span>
</code></pre></div><p><strong>Complexity:</strong></p> <p>We've visited every node once and every edges once. So the complexity will be <strong>O(V + E)</strong> where <strong>V</strong> is the number of nodes and <strong>E</strong> is the number of edges.</p> <h2 id="finding-shortest-path-from-source-in-a-2d-graph"><a href="#finding-shortest-path-from-source-in-a-2d-graph" class="header-anchor">#</a> Finding Shortest Path from Source in a 2D graph</h2> <p>Most of the time, we'll need to find out the shortest path from single source to all other nodes or a specific node in a 2D graph. Say for example: we want to find out how many moves are required for a knight to reach a certain square in a chessboard, or we have an array where some cells are blocked, we have to find out the shortest path from one cell to another. We can move only horizontally and vertically. Even diagonal moves can be possible too. For these cases, we can convert the squares or cells in nodes and solve these problems easily using BFS. Now our <strong>visited</strong>, <strong>parent</strong> and <strong>level</strong> will be 2D arrays. For each node, we'll consider all possible moves. To find the distance to a specific node, we'll also check whether we have reached our destination.</p> <p>There will be one additional thing called direction array. This will simply store the all possible combinations of directions we can go to. Let's say, for horizontal and vertical moves, our direction arrays will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> dx <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
<span class="token operator">|</span> dy <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">0</span> <span class="token operator">|</span> <span class="token number">1</span> <span class="token operator">|</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">|</span>
<span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span><span class="token operator">+</span>
</code></pre></div><p>Here <strong>dx</strong> represents move in x-axis and <strong>dy</strong> represents move in y-axis. Again this part is optional. You can also write all the possible combinations separately. But it's easier to handle it using direction array. There can be more and even different combinations for diagonal moves or knight moves.</p> <p>The additional part we need to keep in mind is:</p> <ul><li>If any of the cell is blocked, for every possible moves, we'll check if the cell is blocked or not.</li> <li>We'll also check if we have gone out of bounds, that is we've crossed the array boundaries.</li> <li>The number of rows and columns will be given.</li></ul> <p>Our pseudo-code will be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>Procedure <span class="token function">BFS2D</span><span class="token punctuation">(</span>Graph<span class="token punctuation">,</span> blocksign<span class="token punctuation">,</span> row<span class="token punctuation">,</span> column<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">for</span> i from <span class="token number">1</span> to row
<span class="token keyword">for</span> j from <span class="token number">1</span> to column
visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> <span class="token boolean">false</span>
end <span class="token keyword">for</span>
end <span class="token keyword">for</span>
visited<span class="token punctuation">[</span>source<span class="token punctuation">.</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>source<span class="token punctuation">.</span>y<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> <span class="token boolean">true</span>
level<span class="token punctuation">[</span>source<span class="token punctuation">.</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>source<span class="token punctuation">.</span>y<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> <span class="token number">0</span>
Q <span class="token operator">=</span> <span class="token function">queue</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>source<span class="token punctuation">)</span>
m <span class="token operator">:</span><span class="token operator">=</span> dx<span class="token punctuation">.</span>size
<span class="token keyword">while</span> Q is <span class="token operator">not</span> empty
top <span class="token operator">:</span><span class="token operator">=</span> Q<span class="token punctuation">.</span>pop
<span class="token keyword">for</span> i from <span class="token number">1</span> to m
temp<span class="token punctuation">.</span>x <span class="token operator">:</span><span class="token operator">=</span> top<span class="token punctuation">.</span>x <span class="token operator">+</span> dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
temp<span class="token punctuation">.</span>y <span class="token operator">:</span><span class="token operator">=</span> top<span class="token punctuation">.</span>y <span class="token operator">+</span> dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
<span class="token keyword">if</span> temp is inside the row <span class="token operator">and</span> column <span class="token operator">and</span> top doesn<span class="token number">'</span>t equal to blocksign
visited<span class="token punctuation">[</span>temp<span class="token punctuation">.</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>temp<span class="token punctuation">.</span>y<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> <span class="token boolean">true</span>
level<span class="token punctuation">[</span>temp<span class="token punctuation">.</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>temp<span class="token punctuation">.</span>y<span class="token punctuation">]</span> <span class="token operator">:</span><span class="token operator">=</span> level<span class="token punctuation">[</span>top<span class="token punctuation">.</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>top<span class="token punctuation">.</span>y<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span>
Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span>
end <span class="token keyword">if</span>
end <span class="token keyword">for</span>
end <span class="token keyword">while</span>
Return level
</code></pre></div><p>As we have discussed earlier, BFS only works for unweighted graphs. For weighted graphs, we'll need <a href="http://stackoverflow.com/documentation/algorithm/7151/dijkstra-s-algorithm/23947/dijkstras-shortest-path-algorithm" target="_blank" rel="noopener noreferrer">Dijkstra<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>'s algorithm. For negative edge cycles, we need <a href="http://stackoverflow.com/documentation/algorithm/4791/bellman-ford-algorithm" target="_blank" rel="noopener noreferrer">Bellman-Ford<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>'s algorithm. Again this algorithm is single source shortest path algorithm. If we need to find out distance from each nodes to all other nodes, we'll need <a href="http://stackoverflow.com/documentation/algorithm/7193/floyd-warshall-algorithm" target="_blank" rel="noopener noreferrer">Floyd-Warshall<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>'s algorithm.</p> <h2 id="connected-components-of-undirected-graph-using-bfs"><a href="#connected-components-of-undirected-graph-using-bfs" class="header-anchor">#</a> Connected Components Of Undirected Graph Using BFS.</h2> <p><strong>BFS</strong> can be used to find the connected components of an <a href="http://mathinsight.org/definition/undirected_graph" target="_blank" rel="noopener noreferrer">undirected graph<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>. We can also find if the given graph is connected or not. Our subsequent discussion assumes we are dealing with undirected graphs.The definition of a connected graph is:</p> <blockquote></blockquote> <p>A graph is connected if there is a path between every pair of
vertices.</p> <p>Following is a <strong>connected graph</strong>.</p> <p><a href="https://i.stack.imgur.com/qeDii.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/qeDii.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Following graph is <strong>not connected</strong> and has 2 connected components:</p> <ol><li>Connected Component 1: {a,b,c,d,e}</li> <li>Connected Component 2: {f}</li></ol> <p><a href="https://i.stack.imgur.com/gbTR8.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/gbTR8.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>BFS is a graph traversal algorithm. So starting from a random source node, if on termination of algorithm, all nodes are visited, then the graph is connected,otherwise it is not connected.</p> <p>PseudoCode for the algorithm.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>boolean <span class="token function">isConnected</span><span class="token punctuation">(</span>Graph g<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">BFS</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token comment">//v is a random source node.</span>
<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">allVisited</span><span class="token punctuation">(</span>g<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>C implementation for finding the whether an undirected graph is connected or not:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><stdio.h></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><stdlib.h></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">MAXVERTICES</span> <span class="token expression"><span class="token number">100</span> </span></span>
<span class="token keyword">void</span> <span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">deque</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">isConnected</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">,</span><span class="token keyword">int</span> noOfVertices<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">BFS</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">,</span><span class="token keyword">int</span> vertex<span class="token punctuation">,</span><span class="token keyword">int</span> noOfVertices<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token comment">//Queue node depicts a single Queue element</span>
<span class="token comment">//It is NOT a graph node.</span>
<span class="token keyword">struct</span> <span class="token class-name">node</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> v<span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">node</span> <span class="token operator">*</span>next<span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">node</span> Node<span class="token punctuation">;</span>
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token class-name">node</span> <span class="token operator">*</span>Nodeptr<span class="token punctuation">;</span>
Nodeptr Qfront <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
Nodeptr Qrear <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> <span class="token operator">*</span>visited<span class="token punctuation">;</span><span class="token comment">//array that keeps track of visited vertices.</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>e<span class="token punctuation">;</span><span class="token comment">//n is number of vertices, e is number of edges.</span>
<span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span>
<span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">;</span><span class="token comment">//adjacency matrix</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Enter number of vertices:"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>n <span class="token operator"><</span> <span class="token number">0</span> <span class="token operator">||</span> n <span class="token operator">></span> MAXVERTICES<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">fprintf</span><span class="token punctuation">(</span><span class="token constant">stderr</span><span class="token punctuation">,</span> <span class="token string">"Please enter a valid positive integer from 1 to %d"</span><span class="token punctuation">,</span>MAXVERTICES<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
graph <span class="token operator">=</span> <span class="token function">malloc</span><span class="token punctuation">(</span>n <span class="token operator">*</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
visited <span class="token operator">=</span> <span class="token function">malloc</span><span class="token punctuation">(</span>n<span class="token operator">*</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">char</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator"><</span> n<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
graph<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">malloc</span><span class="token punctuation">(</span>n<span class="token operator">*</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">'N'</span><span class="token punctuation">;</span><span class="token comment">//initially all vertices are not visited.</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>j <span class="token operator"><</span> n<span class="token punctuation">;</span><span class="token operator">++</span>j<span class="token punctuation">)</span>
graph<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"enter number of edges and then enter them in pairs:"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator"><</span> e<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> u<span class="token punctuation">,</span>v<span class="token punctuation">;</span>
<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&</span>u<span class="token punctuation">,</span><span class="token operator">&</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
graph<span class="token punctuation">[</span>u<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>v<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
graph<span class="token punctuation">[</span>v<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>u<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isConnected</span><span class="token punctuation">(</span>graph<span class="token punctuation">,</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"The graph is connected"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"The graph is NOT connected\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">void</span> <span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token keyword">int</span> vertex<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>Qfront <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
Qfront <span class="token operator">=</span> <span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>Node<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
Qfront<span class="token operator">-></span>v <span class="token operator">=</span> vertex<span class="token punctuation">;</span>
Qfront<span class="token operator">-></span>next <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
Qrear <span class="token operator">=</span> Qfront<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
<span class="token punctuation">{</span>
Nodeptr newNode <span class="token operator">=</span> <span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>Node<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
newNode<span class="token operator">-></span>v <span class="token operator">=</span> vertex<span class="token punctuation">;</span>
newNode<span class="token operator">-></span>next <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
Qrear<span class="token operator">-></span>next <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
Qrear <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">deque</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>Qfront <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Q is empty , returning -1\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> v <span class="token operator">=</span> Qfront<span class="token operator">-></span>v<span class="token punctuation">;</span>
Nodeptr temp<span class="token operator">=</span> Qfront<span class="token punctuation">;</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>Qfront <span class="token operator">==</span> Qrear<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
Qfront <span class="token operator">=</span> Qfront<span class="token operator">-></span>next<span class="token punctuation">;</span>
Qrear <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">else</span>
Qfront <span class="token operator">=</span> Qfront<span class="token operator">-></span>next<span class="token punctuation">;</span>
<span class="token function">free</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> v<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> <span class="token function">isConnected</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">,</span><span class="token keyword">int</span> noOfVertices<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token comment">//let random source vertex be vertex 0;</span>
<span class="token function">BFS</span><span class="token punctuation">(</span>graph<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>noOfVertices<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator"><</span> noOfVertices<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">'N'</span><span class="token punctuation">)</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//0 implies false;</span>
<span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//1 implies true;</span>
<span class="token punctuation">}</span>
<span class="token keyword">void</span> <span class="token function">BFS</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">,</span><span class="token keyword">int</span> noOfVertices<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i<span class="token punctuation">,</span>vertex<span class="token punctuation">;</span>
visited<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">'Y'</span><span class="token punctuation">;</span>
<span class="token function">enqueue</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token punctuation">(</span>vertex <span class="token operator">=</span> <span class="token function">deque</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator"><</span> noOfVertices<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>graph<span class="token punctuation">[</span>vertex<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">1</span> <span class="token operator">&&</span> visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">'N'</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">enqueue</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token string">'Y'</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>For Finding all the Connected components of an undirected graph, we only need to add 2 lines of code to the BFS function. The idea is to call BFS function until all vertices are visited.</p> <p>The lines to be added are:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\nConnected component %d\n"</span><span class="token punctuation">,</span><span class="token operator">++</span>count<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//count is a global variable initialized to 0</span>
<span class="token comment">//add this as first line to BFS function </span>
</code></pre></div><p>AND</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d "</span><span class="token punctuation">,</span>vertex<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
add <span class="token keyword">this</span> as first line of <span class="token keyword">while</span> loop in BFS
</code></pre></div><p>and we define the following function:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">listConnectedComponents</span><span class="token punctuation">(</span><span class="token keyword">char</span> <span class="token operator">*</span><span class="token operator">*</span>graph<span class="token punctuation">,</span><span class="token keyword">int</span> noOfVertices<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> i<span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator"><</span> noOfVertices<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">'N'</span><span class="token punctuation">)</span>
<span class="token function">BFS</span><span class="token punctuation">(</span>graph<span class="token punctuation">,</span>i<span class="token punctuation">,</span>noOfVertices<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/breadth-first-search.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/substring-search.html" class="prev">
Substring Search
</a></span> <span class="next"><a href="/algorithm/depth-first-search.html">
Depth First Search
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/21.0a6a3974.js" defer></script>
</body>
</html>