-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathmax-Island-visual.html
268 lines (267 loc) · 9.81 KB
/
max-Island-visual.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta
name="description"
content="depth first search, breadth first search, number of islands"
/>
<meta
name="keywords"
content="breadth first search, breadth first algorithm, depth first search, depth first traversal, breadth first traversal, path finding, graph algorithms, graphs, algorithms, visualization, visual, graphs, graph traversal, traversal"
/>
<meta name="author" content="lumunge" />
<meta name="HandheldFriendly" content="True" />
<meta
property="og:site_name"
content="OpenGenus IQ: Computing Expertise & Legacy"
/>
<meta property="og:type" content="article" />
<meta property="og:title" content="Making a large island visualization." />
<meta
property="og:description"
content="data structures and algorithms visualization, path finding algorithms, graph algorithms visualization, visual, graphs, graph traversal, traversal"
/>
<meta
property="og:url"
content="https://iq.opengenus.org/algorithm-visualization/"
/>
<meta
property="article:published_time"
content="2021-12-08T10:39:05.000Z"
/>
<meta property="article:modified_time" content="2021-12-08T19:39:45.000Z" />
<meta property="article:tag" content="Algorithms" />
<meta property="article:tag" content="Data Structures" />
<meta property="article:tag" content="Visualization" />
<meta
property="article:publisher"
content="https://www.facebook.com/opengenus"
/>
<meta name="twitter:card" content="summary" />
<meta name="twitter:title" content="Visualization" />
<meta
name="twitter:description"
content="A visualization of making a large island given smaller islands by connecting neighboring islands to achive a maximum size."
/>
<meta
name="twitter:url"
content="https://iq.opengenus.org/algorithm-visualization/"
/>
<meta name="twitter:label1" content="Written by" />
<meta name="twitter:data1" content="Erick Lumunge" />
<meta name="twitter:label2" content="Filed under" />
<meta
name="twitter:data2"
content="Visualization, Algorithms, Data Structures"
/>
<meta name="twitter:site" content="@OpenGenus" />
<link
rel="shortcut icon"
type="image/png"
href="./src/assets/images/fav1.ico"
/>
<link rel="stylesheet" href="./src/assets/css/index.min.css" />
<link rel="stylesheet" href="./src/assets/css/pathFinding.min.css" />
<title>Making a large island.</title>
</head>
<body>
<div class="menu">
<div class="nav">
<div class="logo">
<a href="index.html">OpenGenus Visuals</a>
</div>
<div class="nav-links">
<a href="bfs-visual.html">bfs</a>
<a href="dfs-visual.html">dfs</a>
<a href="dijkstra-visual.html">dijkstra's</a>
<a href="bellman-ford-visual.html">bellman-ford's</a>
<a href="islands-visual.html">num islands</a>
<a href="max-Island-visual.html">max island</a>
<a
href="https://github.com/lumunge/Graph-Algorithms-Visualization/wiki"
>docs</a
>
</div>
</div>
<div class="hamburger">
<span class="bar"></span>
<span class="bar"></span>
<span class="bar"></span>
</div>
</div>
<header>
<div class="heading">
<h2 class="algorithm maxIsland">Making a large island visualization</h2>
<hr />
</div>
<div class="controlsContainer">
<div class="visualControls">
<div class="visualSpeed">
<p>Speed</p>
<input
type="range"
min="1"
max="20"
value="10"
class="speedSlider"
/>
</div>
<div class="obstacles">
<p>Create islands</p>
<div class="obstaclesElements">
<input type="range" min="1" value="50" class="obstacleSlider" />
<button class="setWalls btn">islands</button>
</div>
</div>
<div class="controlBtns">
<button class="clearPath btn" style="display: none">
clear path
</button>
<select name="" class="islandsAlgo" style="display: none">
<option value=""></option>
</select>
<button class="start btn">start</button>
<button class="findNext btn" style="display: none">
find next
</button>
<button class="manual btn" style="display: none">manual</button>
<button class="reset btn">reload</button>
</div>
<div class="tutorialContainer">
<span
><img
class="info"
src="./src/assets/images/icons8-info-60.png"
alt=""
/></span>
<div class="tutorialContent">
<h4>Controls</h4>
<p>
<span>Speed</span> - increase or decrease the speed of the
visualization
</p>
<p>
<span>Islands-</span> - create islands on the grid. <br />
You can adjust the number of islands generated per click. <br />
- You can also click on the grid cells to create an island.
</p>
<p>
<span>Start</span> - After adjusting the speed and creating
islands, you can now start the visualization to see the workings
of the algorithm.
</p>
<p>
<span>Speed</span> - If the grid becomes to cluttered you can
reload it and repeat the above steps.
</p>
</div>
</div>
</div>
<!-- not displayed -->
<div class="controls" style="display: none">
<select class="algo">
<option value=""></option>
</select>
<select class="weight">
<option value="Unweighted"></option>
</select>
</div>
</div>
</header>
<main class="">
<div class="visualizationContainer">
<div id="gridContainer"></div>
<div class="notification" style="display: none"></div>
<div class="algoInfo">
<div>
<div class="infoHeading">
<h3 class="title">Getting the maximum island</h3>
</div>
<div class="description">
<p>
We are given a binary grid(matrix) map of '1's and '0's(water).
We are allowed to change at most one '0' t0 be '1'(flip one '0'
to '1'). Return the size of the largest island in the grid after
applying the above opperation. In this case an island is
classified as a <em><b>4-directionally</b></em> connected group
of 1s.
<br />
In this <em><b>dfs</b></em> approach for every 0 encountered, we
temporarily change if to a 1 and estimate the maximum island
formed. <br />
After finding the size we change the 1 back to a 0.
<br />Finally we will have the maximum island which we return.
</p>
</div>
<div class="algo-steps">
<p class="subtitle">Algorithm</p>
<p>
1. Traverse the entire grid swapping 1s for each island with an
assigned group id(representing that island).
</p>
<p>
2. Create a hashmap with mapId as key and size of island as
value(this done in the first traversal).
</p>
<p>3. Traverse the grid for the ssecond time and find the 0s.</p>
<p>
4. Calculate the suns of all neighbors(4-directional) and add 1
to represent the flipped 0.
</p>
<p>
5. Determine the maximum island by comparing previous sizes.
</p>
<p>
6. If max is 0 after both traversals, return grid size, this is
one big island.
</p>
</div>
<div class="complexity">
<p class="subtitle">Computational complexity</p>
This algorithm takes <b><em>O(M + N)</em></b> where M is the
number of rows and N is the number of columns. The space
complexity is <b><em>O(L)</em></b> where L is the size of the
largest island.
</div>
<div class="reference">
<p>References</p>
<a href="https://iq.opengenus.org/number-of-islands/"
>number of islands</a
>
<br />
<a href="https://iq.opengenus.org/making-a-large-island/"
>max island</a
>
</div>
</div>
</div>
</div>
</main>
<footer>
<div class="copy">
<p>
OpenGenus IQ ©
<script>
document.write(/\d{4}/.exec(Date())[0]);
</script>
All rights reserved ™ [email:
<a href="mailto:team@opengenus.org">team@opengenus.org]</a>
</p>
</div>
<div class="links">
<span><a href="https://iq.opengenus.org/"> Top Posts </a></span>
<span
><a href="https://www.linkedin.com/company/opengenus">
LinkedIn</a
></span
>
<span><a href="https://twitter.com/OpenGenus"> Twitter</a></span>
</div>
</footer>
<script src="./dist/main.js"></script>
</body>
</html>