# BFS in Graph

• Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

http://www.lintcode.com/en/problem/graph-valid-tree/

https://leetcode.com/problems/graph-valid-tree/#/description

``````

In [2]:

class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
dic = {i: [] for i in range(n)}
for i, j in edges:
dic[i].append(j)
dic[j].append(i)
visited = [0 for i in range(n)]
layer, visited[0] = [0], 1
while layer:
next_layer = []
for node in layer:
for next_node in dic[node]:
if visited[next_node]:
return False
dic[next_node].remove(node)
next_layer.append(next_node)
visited[next_node] = 1
layer = next_layer

return True if sum(visited) == n else False

``````
``````

In [3]:

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def __init__(self):
self.dict = {}

def cloneGraph(self, node):
if node is None:
return

nodeCopy = UndirectedGraphNode(node.label)
self.dict[node] = nodeCopy

queue = [node]
while queue:
node = queue.pop(0)
for n in node.neighbors:
if n not in self.dict:
nc = UndirectedGraphNode(n.label)
self.dict[n] = nc
self.dict[node].neighbors.append(nc)
queue.append(n)
else:
self.dict[node].neighbors.append(self.dict[n])

return nodeCopy

``````
• Search Graph Nodes

Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.

There is a mapping store the nodes' values in the given parameters.

Notice

It's guaranteed there is only one available solution

http://www.lintcode.com/en/problem/search-graph-nodes/

``````

In [8]:

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
# @param {UndirectedGraphNode[]} graph a list of undirected graph node
# @param {dict} values a dict, <UndirectedGraphNode, (int)value>
# @param {UndirectedGraphNode} node an Undirected graph node
# @param {int} target an integer
# @return {UndirectedGraphNode} a node
def searchNode(self, graph, values, node, target):
if not node:
return None

if values[node] == target:
return node

queue = [node]
visited = set([node])
while queue:
node = queue.pop(0)
for n in node.neighbors:
if values[n] == target:
return n
if n not in visited:
queue.append(n)

return None

``````
• Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph.

http://www.lintcode.com/en/problem/topological-sorting/

``````

In [18]:

# Definition for a Directed graph node
# class DirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
"""
@param graph: A list of Directed graph node
@return: A list of graph nodes in topological order.
"""
def topSort(self, graph):
dic = {}
for node in graph:
dic[node] = 0

for node in graph:
for n in node.neighbors:
dic[n] += 1

order = []
for node in graph:
if dic[node] == 0:
order.append(node)

queue = order[:]   ## right way to copy a list!!!
while queue:
node = queue.pop(0)
for n in node.neighbors:
dic[n] -= 1
if dic[n] == 0:
order.append(n)
queue.append(n)

return order if len(order) == len(dic) else None

``````

# BFS in Matrix

• Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110 11010 11000 00000 Answer: 1

Example 2:

11000 11000 00100 00011 Answer: 3

https://leetcode.com/problems/number-of-islands/#/description

http://www.lintcode.com/en/problem/number-of-islands/

``````

In [20]:

class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return 0

m, n = len(grid), len(grid[0])
visited = [[False for i in range(n)] for j in range(m)]
count = 0

def bfs(grid, m, n, x, y):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

queue = [[x, y]]
visited[x][y] = True
while queue:
x, y = queue.pop(0)
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < m and 0 <= yy < n:
if not visited[xx][yy] and grid[xx][yy] == '1':
queue.append([xx, yy])
visited[xx][yy] = True

for x in range(m):
for y in range(n):
if not visited[x][y] and grid[x][y] == '1':
count += 1
bfs(grid, m, n, x, y)

return count

``````
``````

In [21]:

class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def numIslands(self, grid):
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return 0

m, n = len(grid), len(grid[0])
visited = [[False for y in range(n)] for x in range(m)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 0

def bfs(x, y):
queue = [[x, y]]
while queue:
x, y = queue.pop(0)
visited[x][y] = True
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
if 0 <= xx < m and 0 <= yy < n:
if not visited[xx][yy] and grid[xx][yy] == 1:
queue.append([xx, yy])
visited[xx][yy] = True

for x in range(m):
for y in range(n):
if not visited[x][y] and grid[x][y] == 1:
count += 1
bfs(x, y)

return count

``````
• Zombie in Matrix

Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.

Example Given a matrix:

0 1 2 0 0 1 0 0 2 1 0 1 0 0 0 return 2

http://www.lintcode.com/en/problem/zombie-in-matrix/

``````

In [22]:

class Solution:
# @param {int[][]} grid  a 2D integer grid
# @return {int} an integer
def zombie(self, grid):
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return -1

m, n = len(grid), len(grid[0])
day, people, zombies = -1, 0, []
di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

for i in range(m):
for j in range(n):
if grid[i][j] == 0:
people += 1
elif grid[i][j] == 1:
zombies.append([i, j])

while zombies:
new_zombies = []
for i, j in zombies:
for k in range(4):
zi, zj = i + di[k], j + dj[k]
if 0 <= zi < m and 0 <= zj < n and grid[zi][zj] == 0:
new_zombies.append([zi, zj])
grid[zi][zj] = 1
people -= 1
day += 1
zombies = new_zombies
# print day, zombies

return -1 if people > 0 else day

``````
``````

In [23]:

# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
# @param {boolean[][]} grid a chessboard included 0 (False) and 1 (True)
# @param {Point} source a point
# @param {Point} destination a point
# @return {int} the shortest path
def shortestPath(self, grid, source, destination):
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return -1

m, n = len(grid), len(grid[0])
d = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]

path, step = [[source.x, source.y]], -1

while path:
step += 1
new_path = []
for x, y in path:
if [x, y] == [destination.x, destination.y]:
return step
for dx, dy in d:
xx, yy = x + dx, y + dy
if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] != 1:
new_path.append([xx, yy])
grid[xx][yy] = 1
path = new_path

return -1

``````
``````

In [ ]:

``````