@@ -45,7 +45,7 @@ And this graph may have multiple **connected components** (islands):
45
45
46
46
Finding the number of islands is to find the number of ` connected components ` .
47
47
48
- Walk from one node to the adjacent node until all nodes on the island are visited.
48
+ Walk from one vertex (land) to the adjacent vertices until all vertices on the island are visited.
49
49
50
50
## Steps
51
51
1 . Find the first land.
@@ -68,12 +68,12 @@ The benefit of using iteration is better program performance. After all, recursi
68
68
69
69
Maintaining a stack by yourself can accomplish the same function as recursive calls.
70
70
71
- From this sample code bellow, you can see that starting from a node , through recursive calls, it goes up until it can't go any further, turns right, and continues up. The priority order of directions is ` up, right, down, left ` .
71
+ From this sample code bellow, you can see that starting from a vertex , through recursive calls, it goes up until it can't go any further, turns right, and continues up. The priority order of directions is ` up, right, down, left ` .
72
72
``` java
73
- pointStack . push({i, j - 1 }); // left
74
- pointStack . push({i + 1 , j}); // down
75
- pointStack . push({i, j + 1 }); // right
76
- pointStack . push({i - 1 , j}); // up
73
+ vertexStack . push({i, j - 1 }); // left
74
+ vertexStack . push({i + 1 , j}); // down
75
+ vertexStack . push({i, j + 1 }); // right
76
+ vertexStack . push({i - 1 , j}); // up
77
77
```
78
78
79
79
## Solution 3: Breadth-First Search
@@ -88,7 +88,7 @@ Please click [Breadth-First Search Solution](200-number-of-islands-3.md) for `20
88
88
class Solution :
89
89
def __init__ (self ):
90
90
self .grid = None
91
- self .point_stack = []
91
+ self .vertex_stack = []
92
92
93
93
def numIslands (self , grid : List[List[str ]]) -> int :
94
94
island_count = 0
@@ -103,11 +103,11 @@ class Solution:
103
103
104
104
return island_count
105
105
106
- def depth_first_search (self , point ):
107
- self .point_stack .append(point )
106
+ def depth_first_search (self , vertex ):
107
+ self .vertex_stack .append(vertex )
108
108
109
- while self .point_stack :
110
- i, j = self .point_stack .pop()
109
+ while self .vertex_stack :
110
+ i, j = self .vertex_stack .pop()
111
111
112
112
if i < 0 or i >= len (self .grid):
113
113
continue
@@ -120,16 +120,16 @@ class Solution:
120
120
121
121
self .grid[i][j] = ' V'
122
122
123
- self .point_stack .append((i, j - 1 ))
124
- self .point_stack .append((i + 1 , j))
125
- self .point_stack .append((i, j + 1 ))
126
- self .point_stack .append((i - 1 , j))
123
+ self .vertex_stack .append((i, j - 1 ))
124
+ self .vertex_stack .append((i + 1 , j))
125
+ self .vertex_stack .append((i, j + 1 ))
126
+ self .vertex_stack .append((i - 1 , j))
127
127
```
128
128
129
129
# Java
130
130
``` java
131
131
class Solution {
132
- Stack<int[]> pointStack = new Stack<> ();
132
+ Stack<int[]> vertexStack = new Stack<> ();
133
133
char [][] grid;
134
134
135
135
public int numIslands (char [][] grid ) {
@@ -149,13 +149,13 @@ class Solution {
149
149
return islandCount;
150
150
}
151
151
152
- void depthFirstSearch (int [] point ) {
153
- pointStack . push(point );
152
+ void depthFirstSearch (int [] vertex ) {
153
+ vertexStack . push(vertex );
154
154
155
- while (! pointStack . empty()) {
156
- point = pointStack . pop();
157
- int i = point [0 ];
158
- int j = point [1 ];
155
+ while (! vertexStack . empty()) {
156
+ vertex = vertexStack . pop();
157
+ int i = vertex [0 ];
158
+ int j = vertex [1 ];
159
159
160
160
if (i < 0 || i >= grid. length) {
161
161
continue ;
@@ -171,10 +171,10 @@ class Solution {
171
171
172
172
grid[i][j] = ' V' ;
173
173
174
- pointStack . push(new int []{i, j - 1 });
175
- pointStack . push(new int []{i + 1 , j});
176
- pointStack . push(new int []{i, j + 1 });
177
- pointStack . push(new int []{i - 1 , j});
174
+ vertexStack . push(new int []{i, j - 1 });
175
+ vertexStack . push(new int []{i + 1 , j});
176
+ vertexStack . push(new int []{i, j + 1 });
177
+ vertexStack . push(new int []{i - 1 , j});
178
178
}
179
179
}
180
180
}
@@ -185,17 +185,17 @@ class Solution {
185
185
class Solution {
186
186
private:
187
187
vector<vector<char >> grid_ ;
188
- stack<pair<int, int>> point_stack ;
188
+ stack<pair<int, int>> vertex_stack ;
189
189
190
190
void depth_first_search(int i1, int j1) {
191
- point_stack .push({i1, j1});
191
+ vertex_stack .push({i1, j1});
192
192
193
- while (!point_stack .empty()) {
194
- pair<int, int> point = point_stack .top();
195
- point_stack .pop();
193
+ while (!vertex_stack .empty()) {
194
+ pair<int, int> vertex = vertex_stack .top();
195
+ vertex_stack .pop();
196
196
197
- int i = point .first;
198
- int j = point .second;
197
+ int i = vertex .first;
198
+ int j = vertex .second;
199
199
200
200
if (i < 0 || i >= grid_.size()) {
201
201
continue;
@@ -211,10 +211,10 @@ private:
211
211
212
212
grid_[i][j] = 'V';
213
213
214
- point_stack .push({i, j - 1});
215
- point_stack .push({i + 1, j});
216
- point_stack .push({i, j + 1});
217
- point_stack .push({i - 1, j});
214
+ vertex_stack .push({i, j - 1});
215
+ vertex_stack .push({i + 1, j});
216
+ vertex_stack .push({i, j + 1});
217
+ vertex_stack .push({i - 1, j});
218
218
}
219
219
}
220
220
@@ -241,11 +241,11 @@ public:
241
241
# JavaScript
242
242
``` JavaScript
243
243
let grid
244
- let pointStack
244
+ let vertexStack
245
245
246
246
var numIslands = function (grid_ ) {
247
247
grid = grid_
248
- pointStack = []
248
+ vertexStack = []
249
249
let islandCount = 0
250
250
251
251
grid .forEach ((row , i ) => {
@@ -261,11 +261,11 @@ var numIslands = function (grid_) {
261
261
return islandCount
262
262
};
263
263
264
- function depthFirstSearch (point ) {
265
- pointStack .push (point )
264
+ function depthFirstSearch (vertex ) {
265
+ vertexStack .push (vertex )
266
266
267
- while (pointStack .length > 0 ) {
268
- const [i , j ] = pointStack .pop ()
267
+ while (vertexStack .length > 0 ) {
268
+ const [i , j ] = vertexStack .pop ()
269
269
270
270
if (i < 0 || i >= grid .length ) {
271
271
continue
@@ -281,10 +281,10 @@ function depthFirstSearch(point) {
281
281
282
282
grid[i][j] = ' V' ;
283
283
284
- pointStack .push ([i, j - 1 ])
285
- pointStack .push ([i + 1 , j])
286
- pointStack .push ([i, j + 1 ])
287
- pointStack .push ([i - 1 , j])
284
+ vertexStack .push ([i, j - 1 ])
285
+ vertexStack .push ([i + 1 , j])
286
+ vertexStack .push ([i, j + 1 ])
287
+ vertexStack .push ([i - 1 , j])
288
288
}
289
289
}
290
290
```
@@ -293,7 +293,7 @@ function depthFirstSearch(point) {
293
293
``` c#
294
294
public class Solution
295
295
{
296
- Stack <int []> pointStack = new Stack <int []>();
296
+ Stack <int []> vertexStack = new Stack <int []>();
297
297
char [][] grid ;
298
298
299
299
public int NumIslands (char [][] grid )
@@ -317,15 +317,15 @@ public class Solution
317
317
return islandCount ;
318
318
}
319
319
320
- void depthFirstSearch (int [] point )
320
+ void depthFirstSearch (int [] vertex )
321
321
{
322
- pointStack .Push (point );
322
+ vertexStack .Push (vertex );
323
323
324
- while (pointStack .Count > 0 )
324
+ while (vertexStack .Count > 0 )
325
325
{
326
- point = pointStack .Pop ();
327
- int i = point [0 ];
328
- int j = point [1 ];
326
+ vertex = vertexStack .Pop ();
327
+ int i = vertex [0 ];
328
+ int j = vertex [1 ];
329
329
330
330
if (i < 0 || i >= grid .Length )
331
331
{
@@ -342,10 +342,10 @@ public class Solution
342
342
343
343
grid [i ][j ] = 'V' ;
344
344
345
- pointStack .Push ([i , j - 1 ]);
346
- pointStack .Push ([i + 1 , j ]);
347
- pointStack .Push ([i , j + 1 ]);
348
- pointStack .Push ([i - 1 , j ]);
345
+ vertexStack .Push ([i , j - 1 ]);
346
+ vertexStack .Push ([i + 1 , j ]);
347
+ vertexStack .Push ([i , j + 1 ]);
348
+ vertexStack .Push ([i - 1 , j ]);
349
349
}
350
350
}
351
351
}
@@ -354,11 +354,11 @@ public class Solution
354
354
# Go
355
355
``` go
356
356
var grid [][]byte
357
- var pointStack = arraystack.New ()
357
+ var vertexStack = arraystack.New ()
358
358
359
359
func numIslands (grid_ [][]byte ) int {
360
360
grid = grid_
361
- pointStack .Clear ()
361
+ vertexStack .Clear ()
362
362
islandCount := 0
363
363
364
364
for i , row := range grid {
@@ -374,14 +374,14 @@ func numIslands(grid_ [][]byte) int {
374
374
return islandCount
375
375
}
376
376
377
- func depthFirstSearch (point []int ) {
378
- pointStack .Push (point )
377
+ func depthFirstSearch (vertex []int ) {
378
+ vertexStack .Push (vertex )
379
379
380
- for !pointStack .Empty () {
381
- point , _ := pointStack .Pop ();
380
+ for !vertexStack .Empty () {
381
+ vertex , _ := vertexStack .Pop ();
382
382
383
- i := point .([]int )[0 ]
384
- j := point .([]int )[1 ]
383
+ i := vertex .([]int )[0 ]
384
+ j := vertex .([]int )[1 ]
385
385
386
386
if i < 0 || i >= len (grid) {
387
387
continue
@@ -397,10 +397,10 @@ func depthFirstSearch(point []int) {
397
397
398
398
grid[i][j] = ' V'
399
399
400
- pointStack .Push ([]int {i, j - 1 })
401
- pointStack .Push ([]int {i + 1 , j})
402
- pointStack .Push ([]int {i, j + 1 })
403
- pointStack .Push ([]int {i - 1 , j})
400
+ vertexStack .Push ([]int {i, j - 1 })
401
+ vertexStack .Push ([]int {i + 1 , j})
402
+ vertexStack .Push ([]int {i, j + 1 })
403
+ vertexStack .Push ([]int {i - 1 , j})
404
404
}
405
405
}
406
406
```
@@ -409,7 +409,7 @@ func depthFirstSearch(point []int) {
409
409
``` ruby
410
410
def num_islands (grid )
411
411
@grid = grid
412
- @point_stack = []
412
+ @vertex_stack = []
413
413
island_count = 0
414
414
415
415
@grid .each_with_index do |row , i |
@@ -425,14 +425,14 @@ def num_islands(grid)
425
425
island_count
426
426
end
427
427
428
- def depth_first_search (point )
429
- @point_stack << point
428
+ def depth_first_search (vertex )
429
+ @vertex_stack << vertex
430
430
431
- while ! @point_stack .empty?
432
- point = @point_stack .pop
431
+ while ! @vertex_stack .empty?
432
+ vertex = @vertex_stack .pop
433
433
434
- i = point [0 ]
435
- j = point [1 ]
434
+ i = vertex [0 ]
435
+ j = vertex [1 ]
436
436
437
437
next if i < 0 || i >= @grid .size
438
438
@@ -442,10 +442,10 @@ def depth_first_search(point)
442
442
443
443
@grid [i][j] = ' V'
444
444
445
- @point_stack << [i, j - 1 ]
446
- @point_stack << [i + 1 , j]
447
- @point_stack << [i, j + 1 ]
448
- @point_stack << [i - 1 , j]
445
+ @vertex_stack << [i, j - 1 ]
446
+ @vertex_stack << [i + 1 , j]
447
+ @vertex_stack << [i, j + 1 ]
448
+ @vertex_stack << [i - 1 , j]
449
449
end
450
450
end
451
451
```
0 commit comments