-
Notifications
You must be signed in to change notification settings - Fork 0
/
8.2-DFS&BFS.py
134 lines (102 loc) · 3.39 KB
/
8.2-DFS&BFS.py
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
import collections
from collections import deque
graph = [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
def dfs(matrix):
# Check for an empty matrix/graph.
if not matrix:
return []
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
def traverse(i, j):
if (i, j) in visited:
return
visited.add((i, j))
# Traverse neighbors.
for direction in directions:
next_i, next_j = i + direction[0], j + direction[1]
if 0 <= next_i < rows and 0 <= next_j < cols:
# Add in question-specific checks, where relevant.
traverse(next_i, next_j)
for i in range(rows):
for j in range(cols):
traverse(i, j)
def bfs(matrix):
# Check for an empty matrix/graph.
if not matrix:
return []
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
def traverse(i, j):
queue = deque([(i, j)])
while queue:
curr_i, curr_j = queue.popleft()
if (curr_i, curr_j) not in visited:
visited.add((curr_i, curr_j))
# Traverse neighbors.
for direction in directions:
next_i, next_j = curr_i + direction[0], curr_j + direction[1]
if 0 <= next_i < rows and 0 <= next_j < cols:
# Add in question-specific checks, where relevant.
queue.append((next_i, next_j))
for i in range(rows):
for j in range(cols):
traverse(i, j)
def bfsnumsIslands(matrix):
if not matrix:
return 0
rows,cols=len(matrix),len(matrix[0])
visit=set()
islands=0
def bfs(r,c):
q=collections.deque()
visit.add((r,c))
q.append((r,c))
while q:
row,col= q.pop() #* If we want to solve it with dfs, we can simply change popleft to pop.
print(row,col)
directions=((1,0),(-1,0),(0,1),(0,-1))
for dr, dc in directions:
r,c = row +dr, col+dc
print("Son",r,c)
if(r in range(rows) and c in range(cols) and matrix[r][c]==1 and (r,c) not in visit):
q.append((r,c))
visit.add((r,c))
for r in range(rows):
for c in range(cols):
if matrix[r][c]==1 and (r,c) not in visit:
bfs(r,c)
islands +=1
return islands
def dfsnumIslands(matrix):
if not matrix:
return 0
rows,cols=len(matrix),len(matrix[0])
visit=set()
islands=0
def dfs(r,c):
q=collections.deque()
visit.add((r,c))
q.append((r,c))
while q:
row,col=q.pop()
directions=((-1,0),(1,0),(0,1),(0,-1))
for dr,dc in directions:
r,c = dr+row,dc+col
if (r in range(rows) and c in range(cols) and matrix[r][c] == 1 and (r,c) not in visit):
visit.add((r,c))
q.append((r,c))
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 1 and (r,c) not in visit:
dfs(r,c)
islands+=1
return islands
print(dfsnumIslands(graph)) #* returns the number of islands