DSA: Graphs

> Adjacency Lists

> Basic Implementation

- Depth First Search Approach

- Breadth First Search Approach

- Practice Problem

> Matrix

- Depth First Search Approach

- Breadth First Search Approach

> Cycle Detection

> Implicit Graphs

---

Adjacency Lists

Undirected Graph Problem:

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

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

Building the Adjacency List:

 def adjacency_list(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

---

Basic Implementation

Problem:

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

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

Depth First Search Approach:

def has_path(graph, src, dst, visited):
  visited = set()

  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 Search Approach:

from collections import deque

def has_path(graph, src, dst):
  visited = set([src])
  queue = deque([ src ])
  
  while queue:
    current = queue.popleft()
    
    if current == dst:
      return True
    
    for neighbor in graph[current]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)
    
  return False

If you just have to visit each node once without memory constraints (e.g. number of islands problem), then it doesn't really matter which one you use. It comes down to your personal preference for recursion/stack vs queue.

BFS is better at:

• finding the shortest distance between two vertices

• graph of unknown size, e.g. word ladder, or even infinite size, e.g. knight shortest path

DFS is better at:

• uses less memory than BFS for wide graphs, since BFS has to keep all the nodes in the queue, and for wide graphs this can be quite large.

• finding nodes far away from the root, e.g. looking for an exit in a maze.

Practice Problems

Largest Component

graph = {
  0: [8, 1, 5],
  1: [0],
  5: [0, 8],
  8: [0, 5],
  2: [3, 4],
  3: [2, 4],
  4: [3, 2]
} # -> 4

def largest_component(graph):

    largest = 0
    visited = set()

    for node in graph:
        size = dfs(graph, node, visited)
        largest = max(size, largest)
    
    return largest

def dfs(graph, current, visited):
    if current in visited:
        return 0
    
    visited.add(current)

    size = 1

    for neighbor in graph[current]:
        size += dfs(graph, neighbor, visited)

    return size

Shortest Path

from collections import deque

def shortest_path(graph, node_A, node_B):
  visited = set( [ node_A ] )
  distance = 0
  queue = deque( [ (node_A, distance) ])
  
  while queue:
    current = queue.popleft()
    node, distance = current
    
    if node == node_B:
      return distance
    
    for neighbor in graph[node]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append((neighbor, distance + 1))

---

Matrix

Depth First Search in a Matrix

def matrix_example(grid):
    #Define variables: rows, cols, visited, etc
    rows = range(len(grid))
    cols = range(len(grid[0]))
    visited = set()

    #Traverse through the Matrix using DFS
    for r in rows:
        for c in cols:
            result = dfs(grid, r, c, visited)
            #Do something with result

    return #solution


#Define dfs function
def dfs(grid, r, c, visited):

    #Define row boundaries
    row_bounds = 0 <= r < len(grid)
    col_bounds = 0 <= c < len(grid[0])

    #Check if r or c is out of bounds
    if not row_bounds or not col_bounds:
        return False

    #Check another logic example
    if grid[r][c] == "W":
        return False

    #Check if position is visited
    pos = (r, c)
    if pos in visited:
        return False
    visited.add(pos)

    #Traverse through the matrix/grid
    dfs(grid, r + 1, c, visited)
    dfs(grid, r - 1, c, visited)
    dfs(grid, r, c + 1, visited)
    dfs(grid, r, c - 1, visited)

    return True

Breadth First Search in a Matrix

from collections import deque

def closest_carrot(grid, starting_row, starting_col):
  visited = set([ (starting_row, starting_col) ])
  distance = 0
  queue = deque([ (starting_row, starting_col, distance)])
  
  while queue:
    current = queue.popleft()
    r, c, distance = current
    
    if grid[r][c] == 'C':
      return distance
    
    deltas = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for delta in deltas:
      delta_row, delta_col = delta
      neighbor_row = r + delta_row
      neighbor_col = c + delta_col    

      pos = (neighbor_row, neighbor_col)

      row_inbounds = 0 <= neighbor_row < len(grid)
      col_inbounds = 0 <= neighbor_col < len(grid[0])
      if row_inbounds and col_inbounds and pos not in visited and grid[r][c] != 'X':
        visited.add(pos)
        queue.append((neighbor_row, neighbor_col, distance + 1))
    
  return -1

Practice Problems

Island Count

def island_count(grid):
  rows = range(len(grid))
  cols = range(len(grid[0]))
  visited = set()
  count = 0
  
  for r in rows:
    for c in cols:
      if dfs(grid, r, c, visited) == True:
        count += 1
  
  return count

def dfs(grid, r, c, visited):
  row_bounds = 0 <= r < len(grid)
  col_bounds = 0 <= c < len(grid[0])
  if not row_bounds or not col_bounds:
    return False
    
  if grid[r][c] == 'W':
    return False
  
  pos = (r, c)
  if pos in visited:
    return False
  visited.add(pos)
  
  dfs(grid, r - 1, c, visited)
  dfs(grid, r + 1, c, visited)
  dfs(grid, r, c - 1, visited)
  dfs(grid, r, c + 1, visited)
  
  return True

Minimum Island

 def minimum_island(grid):
  rows = range(len(grid))
  cols = range(len(grid[0]))
  visited = set()
  smallest = float("inf")
    
  for r in rows:
    for c in cols:
      size = dfs(grid, r, c, visited)
      if size > 0 and size < smallest:
        smallest = size
  
  return smallest

def dfs(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 += dfs(grid, r + 1, c, visited)
  size += dfs(grid, r - 1, c, visited)
  size += dfs(grid, r, c + 1, visited)
  size += dfs(grid, r, c - 1, visited)
  
  return size

---

Cycle Detection

 def has_cycle(graph):
  visiting = set()
  visited = set()
  
  for node in graph:
    if cycle_detect(graph, node, visiting, visited) == True:
      return True
  
  return False

def cycle_detect(graph, node, visiting, visited):
  if node in visited:
    return False
  
  if node in visiting:
    return True
  
  visiting.add(node)
  
  for neighbor in graph[node]:
    if cycle_detect(graph, neighbor, visiting, visited) == True:
      return True
    
  visiting.remove(node)
  visited.add(node)
  
  return False

Practice Problems

Prereqs Possible

def prereqs_possible(num_courses, prereqs):
  graph = build_graph(num_courses, prereqs)
  visiting = set()
  visited = set()
  
  for node in range(0, num_courses):
    if has_cycle(graph, node, visiting, visited):
      return False
  return True

def has_cycle(graph, node, visiting, visited):
  if node in visiting:
    return True
  
  if node in visited:
    return False
  
  visiting.add(node)
  
  for neighbor in graph[node]:
    if has_cycle(graph, neighbor, visiting, visited) == True:
      return True
    
  visiting.remove(node)
  visited.add(node)
  
  return False

---

Implicit Graphs

from collections import deque

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if '0000' in deadends:
            return -1

        def children(lock):
            res = []
            for i in range(4):
                digit = str((int(lock[i]) + 1) % 10)
                res.append(lock[:i] + digit + lock[i + 1:])
                digit = str((int(lock[i]) -1 + 10) % 10)
                res.append(lock[:i] + digit + lock[i + 1:])
            return res

        q = deque()
        q.append(['0000', 0])
        visited = set(deadends)
        while q: 
            lock, turns = q.popleft()
            if lock == target:
                return turns

            for child in children(lock):
                if child not in visited:
                    visited.add(child)
                    q.append([child, turns + 1])
        return -1