Skip to content

NOTE.md

Latest commit

 

History

History
286 lines (226 loc) · 7.72 KB

NOTE.md

File metadata and controls

286 lines (226 loc) · 7.72 KB

04

Graph

A graph is a finite set of vertices and connected by a set of edges.

(1:M)---(0:E)
  |  \    |
  |   \   |
  |    \  |
(2:B)---(3:L)
   \
    \
   (4:P)

Types of graphs:

  • Undirected Graph: nodes are connected by edges that are all bidirectional.
  • Directed Graph: nodes are connected by directed edges – they only go in one direction.

Graph Adjacency List Representation

  • The size of the array is equal to the number of nodes.
  • A single index, array[i] represents the list of nodes adjacent to the ith node.
0 -> 1 -> 3#
1 -> 0 -> 2 -> 3#
2 -> 1 -> 3 -> 4#
3 -> 0 -> 1 -> 2#
4 -> 2#

Graph Adjacency Matrix Representation

  • An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph.
  • A slot matrix[i][j] = 1 indicates that there is an edge from node i to node j.
0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 1 0
2 0 1 0 1 1
3 1 1 1 0 0
4 0 0 1 0 0

Graph Python Implementation

graph = {
    'A': ['B', 'C'],    # A -> B, A -> C
    'B': ['C', 'D'],    # B -> C, B -> D
    'C': ['D'],         # C -> D
    'D': ['C'],         # D -> C
    'E': ['F'],         # E -> F
    'F': ['C']          # F -> C
}

Depth-first Search (DFS)

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

visited = set()

def dfs(node):
    # base case
    if not node:
        return

    # already visited
    if node in visited:
        return

    # process current node
    process(node.val)

    # add to visited
    visited.add(node)

    # process neighbors / children
    for child in node.children:
        dfs(child)

Island Problem

def island(self, grid: List[List[int]]):
    # length of row and column
    m, n = len(grid), len(grid[0])

    def dfs(r, c):
        # base case: grid[r][c] is out of bound
        if not inArea(r, c):
            return

        # current node is ocean, or it's already visited
        if grid[r][c] == 0 or grid[r][c] == -1:
            return

        # mark as visited
        grid[r][c] = -1

        # visit neighbor nodes
        dfs(r+1, c) # UP
        dfs(r-1, c) # DOWN
        dfs(r, c-1) # LEFT
        dfs(r, c+1) # RIGHT

    def inArea(r, c):
        return 0 <= r < m and 0 <= c < n

    for r in range(m):
        for c in range(n):
            # start dfs for each element in grid
            dfs(r, c)

Leetcode Problems

Breadth-first Search (BFS)

Breadth-first search is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

def bfs(root):
    queue = collections.deque([root])
    visited = set()

    # Loop until queue is empty
    while queue:
        # get current node from queue
        node = queue.popleft()

        # already visited
        if node in visited:
            continue

        # process current node
        process(node.val)

        # add to visited
        visited.add(node)

        # process neighbors / children
        for child in node.children:
            queue.append(child)

Level Order

def levelOrder(root):
    queue = collections.deque([root])
    visited = set()
    res = []

    # Loop until queue is empty
    while queue:
        # process all nodes from the current level
        level_nodes = []

        for _ in range(len(queue)):
            # get current node from queue
            node = queue.popleft()

            # check if the node is already visited
            if node in visited:
                continue

            # process current node
            level_nodes.append(node.val)

            # add to visited
            visited.add(node)

            # process children
            if node.children:
                for child in node.children:
                    if child not in visited:
                        queue.append(child)

        res.append(level_nodes)

    return res

Shortest Path

def shortestPath(start, target): # any two nodes, doesn't have to start from the root
    queue = collections.deque([start])
    visited = set([start])
    step = 0

    # Loop until queue is empty
    while queue:
        # spread the search from the current level
        for _ in range(len(queue)):
            # get current node from queue
            node = queue.popleft()

            # see if we reach the target
            if node is target:
                return step

            # process children
            if node.children:
                for child in node.children:
                    if child not in visited:
                        queue.append(child)
                        visited.add(child)

        step += 1

    return 0 # not found

Bidirectional BFS

def biBfs(source, target):
    sourceQueue = collections.deque([source])
    targetQueue = collections.deque([target])
    visited = set([source])
    step = 0

    while sourceQueue and targetQueue:
        # choose the smaller queue to spread
        if len(sourceQueue) > len(targetQueue):
            sourceQueue, targetQueue = targetQueue, sourceQueue

        for _ in range(len(sourceQueue)):
            node = sourceQueue.popleft()

            for child in node.children:
                # source and target meet
                if child in targetQueue:
                    return step + 1

                if child not in visited:
                    sourceQueue.append(child)
                    visited.add(child)

        step += 1

    return 0 # not found

Leetcode Problems

A-Star (A*) Search

A-star is a graph traversal and path search algorithm, which is often used in computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O space complexity, as it stores all generated nodes in memory.

def AstarSearch(graph, start, end):
	pq = collections.priority_queue() # priority —> heuristic function
	pq.append([start])
	visited.add(start)
	while pq:
		node = pq.pop() # can we add more intelligence here?
		visited.add(node)
		process(node)
		nodes = generate_related_nodes(node)
        unvisited = [node for node in nodes if node not in visited]
		pq.push(unvisited)

Leetcode Problems