Graph

Problem:
The code of Depth frist traversal uses stack & Bredth first traverasl uses queue like we saw in case of Binary Tree.

Depth first traversal – Iterative:

def depth_first_print_iterative(graph, start):
    stack = [start]
    while len(stack) > 0:
        current = stack.pop()
        print(current)
        for neighbor in graph[current]:
            stack.append(neighbor)


graph = {"a": ["b", "c"], "b": ["d"], "c": ["e"], "d": ["f"], "e": [], "f": []}

depth_first_print_iterative(graph, "a")

Depth first traversal – Recursive

def depth_first_print_recursive(graph, start):
    print(start)
    for neighbor in graph[start]:
        depth_first_print_recursive(graph, neighbor)


graph = {"a": ["b", "c"], "b": ["d"], "c": ["e"], "d": ["f"], "e": [], "f": []}

depth_first_print_recursive(graph, "a")

Breadth first traversal:

def breadth_first_print(graph, start):
    queue = [start]
    while queue:
        current = queue.pop(0)
        print(current)
        for neighbor in graph[current]:
            queue.append(neighbor)


graph = {"a": ["b", "c"], "b": ["d"], "c": ["e"], "d": ["f"], "e": [], "f": []}

breadth_first_print(graph, "a")

Problem:
Write a function, has_path, that takes in a dictionary representing the adjacency list of a directed acyclic graph and two nodes (src, dst). The function should return a boolean indicating whether or not there exists a directed path between the source and destination nodes.
Hey. This is our first graph problem, so you should be liberal with watching the Approach and Walkthrough. Be productive, not stubborn. -AZ

# test_00:
graph = {
  'f': ['g', 'i'],
  'g': ['h'],
  'h': [],
  'i': ['g', 'k'],
  'j': ['i'],
  'k': []
}

has_path(graph, 'f', 'k') # True

Solution:
The key point is: you are never changing the dst node at any point of time. Each time you make a recursive call, you will pass the neighbour as your src node. So, you started at src node & kept exploring it’s neighbours. At one point of time, src == dst, which means there is a path from src to dst.

def has_path(graph, src, dst):
    if src == dst:
        return True

    for neighbor in graph[src]:
        if has_path(graph, neighbor, dst) == True:
            return True

    return False

Problem:
Write a function, undirected_path, that takes in a list of edges for an undirected graph and two nodes (node_A, node_B). The function should return a boolean indicating whether or not there exists a path between node_A and node_B.

# test_00:
edges = [
  ('i', 'j'),
  ('k', 'i'),
  ('m', 'k'),
  ('k', 'l'),
  ('o', 'n')
]

undirected_path(edges, 'j', 'm') # -> True

Solution:
When you are doing undirected graph problems, you must look for cycles. For example, in this problem. There are 2 cycles.
i, j & k
o & n
The problem with cycles is, once you enter into these cycles, you can’t come out. Keep revolving in it 🙂

Depth first

def undirected_path(edges, node_A, node_B):
    graph = build_graph(edges)
    return has_path(graph, node_A, node_B, set())
def build_graph(edges):
    graph = {}
    for edge in edges:
        a, b = edge
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append(b)
        graph[b].append(a)
    return graph
def has_path(graph, src, dst, visited):
    if src == dst:
        return True
    if src in visited:
        return False
    visited.add(src)
    for neighbor in graph[src]:
        if has_path(graph, neighbor, dst, visited) == True:
            return True
    return False

Breadth first

from collections import deque
def undirected_path(edges, node_A, node_B):
    graph = build_graph(edges)
    return has_path(graph, node_A, node_B)
def build_graph(edges):
    graph = {}
    for edge in edges:
        a, b = edge
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append(b)
        graph[b].append(a)
    return graph
def has_path(graph, src, dst):
    visited = {src}
    queue = deque([src])
    while queue:
        node = queue.popleft()
        if node == dst:
            return True
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return False

Problem:
Write a function, connected_components_count, that takes in the adjacency list of an undirected graph. The function should return the number of connected components within the graph.

# test_00:
connected_components_count({
  0: [8, 1, 5],
  1: [0],
  5: [0, 8],
  8: [0, 5],
  2: [3, 4],
  3: [2, 4],
  4: [3, 2]
}) # -> 2

Solution:
For each key of the graph, will explore it’s connected nodes using dfs → once this dfs finishes, will return count as 1. Inorder to avoid exploring the same nodes again, will use our visited = set() logic.
For example; for the below graph, connected components count is 3

Depth first

def connected_components_count(graph):
    visited = set()
    count = 0
    for node in graph:
        if explore(graph, node, visited) == True:
            count += 1
    return count
def explore(graph, current, visited):
    if current in visited:
        return False
    visited.add(current)
    for neighbor in graph[current]:
        explore(graph, neighbor, visited)
    return True

Breadth first

from collections import deque
def connected_components_count(graph):
  visited = set()
  count = 0 
  for node in graph:
    if explore(graph, node, visited) == True:
      count += 1      
  return count
def explore(graph, src, visited):
  if src in visited:
    return False
  visited.add(src)
  queue = deque([src])
  while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)
  return True

Problem:
Write a function, largest_component, that takes in the adjacency list of an undirected graph. The function should return the size of the largest connected component in the graph.

# test_00:
largest_component({
  0: [8, 1, 5],
  1: [0],
  5: [0, 8],
  8: [0, 5],
  2: [3, 4],
  3: [2, 4],
  4: [3, 2]
}) # -> 4

Solution:
For each key of the graph, will explore it’s connected nodes using dfs → once this dfs finishes, will return count as 1. Inorder to avoid exploring the same nodes again, will use our visited = set() logic.
For example; for the below graph, connected components count is 3

Depth first

def connected_components_count(graph):
    visited = set()
    count = 0
    for node in graph:
        if explore(graph, node, visited) == True:
            count += 1
    return count
def explore(graph, current, visited):
    if current in visited:
        return False
    visited.add(current)
    for neighbor in graph[current]:
        explore(graph, neighbor, visited)
    return True

Breadth first

from collections import deque
def connected_components_count(graph):
  visited = set()
  count = 0 
  for node in graph:
    if explore(graph, node, visited) == True:
      count += 1      
  return count
def explore(graph, src, visited):
  if src in visited:
    return False
  visited.add(src)
  queue = deque([src])
  while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)
  return True

Problem:
Write a function, shortest_path, that takes in a list of edges for an undirected graph and two nodes (node_A, node_B). The function should return the length of the shortest path between A and B. Consider the length as the number of edges in the path, not the number of nodes. If there is no path between A and B, then return -1. You can assume that A and B exist as nodes in the graph.

# test_00:
edges = [
  ['w', 'x'],
  ['x', 'y'],
  ['z', 'y'],
  ['z', 'v'],
  ['w', 'v']
]
shortest_path(edges, 'w', 'z') # -> 2

Solution:
If you solve this problem using DFS, then the first path you find is not the shortest path. Hence, you need to implement shortest path logic. Where as if you do the BFS; then the first path you are going to find is the shortest path.

Breadth first

from collections import deque
def shortest_path(edges, node_A, node_B):
    graph = build_graph(edges)
    visited = set([node_A])
    queue = deque([(node_A, 0)])
    while queue:
        node, distance = queue.popleft()
        if node == node_B:
            return distance
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    return -1
def build_graph(edges):
    graph = {}
    for edge in edges:
        a, b = edge
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append(b)
        graph[b].append(a)
    return graph

Problem:
Write a function, island_count, that takes in a grid containing Ws and Ls. W represents water and L represents land. The function should return the number of islands on the grid. An island is a vertically or horizontally connected region of land.

# test_00:
grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
]

island_count(grid) # -> 3

Solution:
Grid is represented as list of lists where each list corresponds to an row in grid. Hence, any node on the grid can be accessed with index numbers as grid[3][4].
Once you are at certain node, the surrounding nodes can be accessed as shown below:

Logic of code: Will start with iterative code to navigate through whole grid & during that process will see whether we encounter land / water cell.
If we come across land cell, we don’t do anything….. Eckhart tolle
Instead if we encounter water cell, will do work, but don’t except results….. again spirituality is looking into my code 🙂 That work we do is dfs. Will explore the island we found completly using the dfs in an helper function & make that fn return 1 to indicate that we just explored an island completly.

Depth first

def island_count(grid):
    visited = set()
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if explore(grid, r, c, visited) == True:
                count += 1
    return count
def explore(grid, r, c, visited):
    row_inbounds = 0 <= r < len(grid)
    col_inbounds = 0 <= c < len(grid[0])
    if not row_inbounds or not col_inbounds:
        return False
    if grid[r][c] == "W":
        return False
    pos = (r, c)
    if pos in visited:
        return False
    visited.add(pos)
    explore(grid, r - 1, c, visited)
    explore(grid, r + 1, c, visited)
    explore(grid, r, c - 1, visited)
    explore(grid, r, c + 1, visited)
    return True

Breadth first

from collections import deque
def island_count(grid):
    visited = set()
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if explore(grid, r, c, visited) == True:
                count += 1
    return count
def explore(grid, r, c, visited):
    pos = (r, c)
    if pos in visited or grid[r][c] == "W":
        return False
    visited.add(pos)
    deltas = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([pos])
    while queue:
        currentR, currentC = queue.popleft()
        for delta in deltas:
            dRow, dCol = delta
            neighborR = dRow + currentR
            neighborC = dCol + currentC
            neighborPos = (neighborR, neighborC)
            row_inbounds = 0 <= neighborR < len(grid)
            col_inbounds = 0 <= neighborC < len(grid[0])
            if (
                neighborPos not in visited
                and row_inbounds
                and col_inbounds
                and grid[neighborR][neighborC] == "L"
            ):
                queue.append(neighborPos)
                visited.add(neighborPos)
    return True

Problem:
Write a function, minimum_island, that takes in a grid containing Ws and Ls. W represents water and L represents land. The function should return the size of the smallest island. An island is a vertically or horizontally connected region of land.
You may assume that the grid contains at least one island.

# test_00:
grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
]

minimum_island(grid) # -> 2

Solution:

Depth first

def minimum_island(grid):
    visited = set()
    min_size = float("inf")
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            size = explore_size(grid, r, c, visited)
            if size > 0 and size < min_size:
                min_size = size
    return min_size
def explore_size(grid, r, c, visited):
    row_inbounds = 0 <= r < len(grid)
    col_inbounds = 0 <= c < len(grid[0])
    if not row_inbounds or not col_inbounds:
        return 0
    if grid[r][c] == "W":
        return 0
    pos = (r, c)
    if pos in visited:
        return 0
    visited.add(pos)
    size = 1
    size += explore_size(grid, r - 1, c, visited)
    size += explore_size(grid, r + 1, c, visited)
    size += explore_size(grid, r, c - 1, visited)
    size += explore_size(grid, r, c + 1, visited)
    return size

Breadth first

def minimum_island(grid):
    visited = set()
    min_size = float("inf")
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            size = explore_size(grid, r, c, visited)
            if size > 0 and size < min_size:
                min_size = size
    return min_size
def explore_size(grid, r, c, visited):
    row_inbounds = 0 <= r < len(grid)
    col_inbounds = 0 <= c < len(grid[0])
    if not row_inbounds or not col_inbounds:
        return 0
    if grid[r][c] == "W":
        return 0
    pos = (r, c)
    if pos in visited:
        return 0
    visited.add(pos)
    size = 1
    size += explore_size(grid, r - 1, c, visited)
    size += explore_size(grid, r + 1, c, visited)
    size += explore_size(grid, r, c - 1, visited)
    size += explore_size(grid, r, c + 1, visited)
    return size