Graph

Representation

Graph can be represented using Adjacency Matrix, Adjacency List and hash table.

Following is an example undirected graph with 5 vertices.

Adjacency Matrix vs. Adjacency Lists

• Adjacency Matrix
  • Time: Edge removal $O(1)$, Query of Edge $O(1)$
  • Space: $O(V^2)$
• Adjacency List
  • Time: Query of Edge $O(V)$
  • Space: $O(V + E)$

Graph Search Algorithms

Draw the Search Graph of Problems

• What does it store on each level?
• How many different states should we try to put on each level?

Tip

• Checking existed and Writing existed nodes should be put at the same place.

Breadth-First Search (BFS-1)

Problems

P1. Level order treverse

P2. Bipartite

The graph can be divided into two parts, in either of which there is no direct edges between nodes.

• use two explored sets
• make sure nodes of two consequent levels do not have nodes in common.

P3. Determine whether a binary tree is a complete binary tree

• find the first node that misses one or two children node.
• ensure the nodes behind have no child.

Best-First Search (BFS-2)

Dijkstra's algorithm

Problems

P1. find the shortest path cost from source node to any other nodes in the graph

• 点到面
• 使用Min Heap记录candidates
• Any node can only be expanded once but can be generated more than once.

Depth First Search (DFS, Back-tracking)

• Draw recursion tree
  • How many levels are there?
  • How many branches can we make from the current code?
  • Two kinds of recursion tree
    • I. in each level, there exists only two branches, that is, to add and not to add.
      • base case should add to result and return
    • II. in each level, there exists many branches that depends on what choices are left. (NOT RECOMMENDED)
      • base case should add to result and may not return
• Issues and tricks
  • inplace
    • split the input array into two parts by using swap (Problem: permutation)
      • Arranged characters | Candidate characters
    • use two resizable container respectively record the arranged charcters and candidate charcters**. In Java, use StringBuilder to record arranged characters and use Set/List/boolean[] to record candidates.
  • remove duplicate
    • sort the array first then use a while loop to move index in each function call when using recursion tree I
    • use extra space like HashSet in Java to record used characters in each level

P1. subsets

P2. make up 99 cents with 4 kinds of coins

- 4 levels in total

P3.

P4. Permutations

P5. List all valid combination of factors that form an integer.

• Recursion I.

  • on each level, we have lots of branches, which represent all possible number of current factor
  • factors go down as along as level increase

        12
    /            \
    6^0           6^1
    /   \          /   \
    4^0  4^1       4^0  4^1
    ...
    

• Recursion II.

  • on each level, we have lots of branches, which represent all the possible and smaller or equal factors.
  • only expand factors that are less than or equal to the previous factor

                12
        /    |    |    \
        6    4    3     2
       /     |    |     |
      2      3    2     2
                  |     |
                  2(v)  x

P6. Print all permutations of ([{

• dfs
• use stack to determine which right parenthesis to add (because we need to do linear scan)

Generic Tree Search Algorithm (BFS and DFS)

Reference - [USC-CSCI561-Lecture-Week2]

Three points

• Initial state
• Expansion/generation rule
• Termination condition

function TreeSearch(problem) return a solution or failure

frontier <- makeQueue(makeNodes(problem.INITIAL_STATE))
loop do
    if isEmpty(frontiers) then return failure
    node <- removeFirst(frontiers)
    if goalTest() applied to node.state succeeds
        then return solution(node)
    frontiers <- insertAll(EXPAND(node, problem))

Expand Function

// @Return: a set of nodes
def expand(node, problem):
    successors = set([])
    for (action, result) in problem.get_successors(node.state):
        s = node(empty)
        s.state = result
        s.parent_node = node
        s.action = action
        s.path_cost = node.path_cost + get_step_cost(node, action, s)
        s.depth = node.depth + 1
        successors.add(s)
    return successors

Note:

• Always remove elements from the front
• BFS places new elements at the end of the queue. FIFO.
• DFS places new elements at the front of the queue(stack). LILO.

Generic Graph Search Algorithm

function GraphSearch(problem) return a solution or failure

frontier <- makeQueue(makeNodes(problem.INITIAL_STATE))
exploredSet <- empty // change 1
loop do
    if isEmpty(frontiers) then return failure
    node <- removeFirst(frontiers)
    if goalTest() applied to node.state succeeds
        then return solution(node)
    exploredSet <- insert(node, exploredSet) // change 2; after goalTest the node.
    candidateNodes <- EXPAND(node, problem)
    candidateNodes.filter(NOT in frontier && NOT in exploredSet)
    frontiers <- insertAll(candidateNodes)

Check if there exists a loop

in a Directed Graph

1. DFS and check if there is duplicate explored node in one path

2. Topological Sorting

Idea

• A circle does not have any nodes with zero in-degree, while other graphs always do.
• So we keep removing nodes with zero in-degrees from the graph and see if there are nodes left.

Steps

• construct edge map (out) and in-degree map
• remove nodes with zero indegree
• keep removing
• if there are nodes left, there exists loops.

in a Undirected Graph

1. Union-find (Disjoint Set)

Princeton Slide

A disjoint-set data structure is a data structure that keeps track of the belongings of nodes.

• Each node has one pointer
• The root has empty pointer
• Each subset only have one root

1 -> 2 -> 3
5 -> 2
4 -> 3

• Operations

  •   - Eg. ```find(1) = 3```, ```find(4) = 3
    

    • 1 and 4 belongs to same subset.
  • union(A, B)
    • rootA = find(A)
    • rootB = find(B)
    • connect rootA -> rootB
• Steps to find circle - find the superfluous edge that contributes to the disjoint-set.
  • given nodes and edges
  • use a parent array to record the parent of each node: parent[node.length]
  • initialize all nodes to be disjoint sets
    • for each node, parent[i] = -1
    • for each edge A -> B,
      • rootA = find(A)
      • rootB = find(B)
      • if rootA != rootB: union(A, B)
      • else: return Circle Detected

LeetCode 685. Redundant Connection II

From S^T to S*T

Viterbi Algorithm Coke Range Machine