Graph

Summary

Graph

A graph is made up of vertices and edges. Degree of a vertex is the number of edges connected to it. We can implement a graph as:

class Vertex:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

This structure is essentially the same as a tree, except that a tree is a special case of a graph where each node has at most one parent.

Adjacency List and Adjacency Matrix

Adjacency list is a list of vertices where each vertex has a list of its neighbors with spatial complexity O(V + E).

Adjacency matrix is a 2D array where the element at row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. With spatial complexity O(V^2).

Graph Traversal

Compared to tree, graph can have cycles. Thus, we need to use a visited set to avoid infinite loop.

Depth First Search (DFS)

Vertex Traversal

def traverse(graph, s, visited):
    # base case
    if s < 0 or s >= len(graph):
        return
    if visited[s]:
        return
    # Pre-order position
    visited[s] = True
    print("visit", s)
    for e in graph.neighbors(s):
        traverse(graph, e.to, visited)
    # Post-order position

The time complexity of this algorithm is O(V + E) and the space complexity is O(V).

Edge Traversal

Use a 2D array to record the visited edges.

def traverse_edges(s, visited):
    # base case
    if s is None:
        return
    for neighbor in s.neighbors:
        if visited[s.id][neighbor.id]:
            continue
        visited[s.id][neighbor.id] = True
        print(f"visit edge: {s.id} -> {neighbor.id}")
        traverse_edges(neighbor, visited)
    # Post-order position

Path Traversal

def traverse(graph, src, dest):
    # base case
    if src < 0 or src >= len(graph):
        return
    if on_path[src]:
        return
    if src == dest:
        print(f"find path: {'->'.join(map(str, path))}->{dest}")
        return

    # pre-order position
    on_path[src] = True
    path.append(src)
    for e in graph.neighbors(src):
        traverse(graph, e.to, dest)
    # post-order position
    path.pop()
    on_path[src] = False

Breadth First Search (BFS)

Compared to DFS, BFS is usually used to find the shortest path.

def bfs(graph, s):
    visited = [False] * len(graph)
    from collections import deque
    q = deque([s])
    visited[s] = True

    while q:
        cur = q.popleft()
        print(f"visit {cur}")
        for e in graph.neighbors(cur):
            if visited[e.to]: 
                continue
            q.append(e.to)
            visited[e.to] = True

Eulerian Graph

Eulerian path: A path that visits every edge exactly once.

Eulerian circuit: A circuit that visits every edge exactly once (i.e., start and end at the same vertex).

Based on those definitions, we can categorize the graph into three types:

1. Eulerian graph: A graph that has an Eulerian circuit.
2. Semi-Eulerian graph: A graph that has an Eulerian path but no Eulerian circuit.
3. Non-Eulerian graph: A graph that has no Eulerian path or circuit.

Determine Eulerian Graph

For undirected graph, we have

1. Eulerian graph: All vertices have even degree.
2. Semi-Eulerian graph: Exactly two vertices have odd degree, and all other vertices have even degree.

For directed graph, we have

1. Eulerian graph: All vertices have equal in-degree and out-degree.
2. Semi-Eulerian graph: Exactly one vertex has one more out-degree than in-degree and exactly one vertex has one more in-degree than out-degree, and all other vertices have equal in-degree and out-degree.

Find Eulerian Path

Hierholzer's algorithm

Shortest Path

Single Source Shortest Path

Single source shortest path problem is to find the shortest path from a source vertex to all other vertices in the graph. The classic solutions are

1. Dijkstra's Algorithm (BFS+Greedy): Fast, cannot handle negative weight edges.
2. Bellman-Ford Algorithm (DP): Can handle negative weight edges, but slower.

Dijkstra's Algorithm (BFS+Greedy)

The key difference between Dijkstra's algorithm and BFS is that Dijkstra's algorithm uses a priority queue to always expand the vertex with the smallest distance first.

import heapq
from typing import List

class State:
    def __init__(self, node: int, distFromStart: int):
        self.node = node
        self.distFromStart = distFromStart

    def __lt__(self, other: "State") -> bool:
        return self.distFromStart < other.distFromStart


def dijkstra(graph: Graph, src: int) -> List[int]:
    distTo: List[int] = [float('inf')] * graph.size()
    pq: List[State] = []
    heapq.heappush(pq, State(src, 0))
    distTo[src] = 0

    while pq:
        state = heapq.heappop(pq)
        curNode = state.node
        curDistFromStart = state.distFromStart

        if distTo[curNode] < curDistFromStart: 
            # skip if the current distance is larger than the recorded distance
            continue

        for e in graph.neighbors(curNode):
            nextNode = e.to
            nextDistFromStart = curDistFromStart + e.weight

            if distTo[nextNode] <= nextDistFromStart:
                continue

            heapq.heappush(pq, State(nextNode, nextDistFromStart))
            distTo[nextNode] = nextDistFromStart

    return distTo

Network Delay Time (Leetcode 743)

Bellman-Ford Algorithm

Single Source Single Destination Shortest Path

A* Search

Compared to Dijkstra's algorithm, A* considers both the distance from the source and the estimated distance to the destination.