Chapter 3 - Graph

Adjacency List, DFS, BFS, and Topological Sort

Adjacency

Adjacency List

The adjacency list is crucial in terms of traversing the graph, it can be used to process a directed/undirected and DAG/cycle graph. In simple words, you can view the adjacency list as a neighbor's list, for example, if a vertex E is directing a connection to vertices A and B, then the adjacency list for E is

E: A, B

How to initialize an adjacency list?

• Determine the direction of the graph

• Usually use a dictionary for an efficient lookup

• For every V in vertices, store every neighbor of V into a dictionary such that V is the key and neighbors are the value

Directed Graph:

adj_list = defaultdict(list)
for u, v in edges:
    adj_list[u].append(v) #when u is pointing towards v

Undirected Graph:

adj_list = defaultdict(list)
for u, v in edges:
    adj_list[u].append(v) #when u is pointing towards v
    adj_list[v].append(u) #when v is pointing towards u

DFS

Just like the tree, we can use DFS to traverse the furthest vertex in a graph

def DFS(adj_list):
    # Initialize visited set to keep track of visited nodes
    visited = set()

    # Define a helper function for recursive DFS
    def helper(u):
        # Mark the current node as visited
        visited.add(u)
        
        # Recursively visit all unvisited neighbors
        for v in adj_list[u]:
            if v not in visited:
                helper(v)

    # Perform DFS for each unvisited node in the graph
    for u in adj_list:
        if u not in visited:
            helper(u)
        
    return visited

BFS

Just like the tree, we can also use a queue to traverse the graph

from collections import deque

def BFS(adj_list):
    visited = set()
    queue = deque()
    
    # Perform BFS for each unvisited component in the graph
    for u in adj_list:
        if u in visited:
            continue
        
        # Initialize the BFS with the starting node
        queue.append(u)
        visited.add(u)  # Mark the starting node as visited
        
        # Process the queue
        while queue:
            temp = queue.popleft()
            
            # Visit each neighbor of the current node
            for v in adj_list[temp]:
                if v not in visited:
                    queue.append(v)
                    visited.add(v)  

    return visited

DAG, Cycle, and Topological Sort

Definition. A directed graph with no cycles is called a Directed Acyclic Graph or DAG for short.

(In the undirected case, a graph without cycles is just a forest of trees.)

Definition. Let ( G = (V, E) ) be a Directed Acyclic Graph (i.e., a DAG) with ( n ) vertices. We say that the sequence of vertices ( L = (u_1, u_2, \dots, u_n) ) is a topological sort of ( G ) if every ( v ) in ( V ) appears exactly once in ( L ), and for every directed edge ( (x, z) ) in ( E ), the source vertex ( x ) appears earlier in ( L ) than the destination vertex ( z ).

BFS Topological Sort

from collections import defaultdict, deque

def BFS(adj_list):
    # Step 1: Calculate in-degrees of each node
    in_degree = defaultdict(int)
    for u in adj_list:
        for v in adj_list[u]:
            in_degree[v] += 1
            
    # Step 2: Initialize the queue with nodes having in-degree of 0
    ready = deque()
    for node in adj_list:
        if in_degree[node] == 0:
            ready.append(node)
    
    # Step 3: Process the nodes in topological order
    processed_count = 0
    while ready:
        node = ready.popleft()
        print(node)
        processed_count += 1
        
        for neighbor in adj_list[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                ready.append(neighbor)
                
    # Step 4: Detect cycle if not all nodes are processed
    if processed_count != len(adj_list):
        return "cycle detected"
    return "no cycle detected"

Theorem: A directed graph can be topologically sorted if and only if it is a DAG.

Reverse Topological Sort in DFS(Tarjan's)

Pick any vertex v in G and start traversing by using DFS, since G is acyclic, then it means no vertex v can appear more than one time in the traversing steps, therefore, we can delete the visited vertex v

The point is, that a reverse topological sort can print W first therefore it is "reversed"

def DFS(adj_list):
    started = set()
    done = set()
    for u in adj_list:
        if started[u] is False:
            helper(u)
            started[u] = True
    def helper(node):
        for u in adj_list[node]:
            if started[u] is False:
                helper(u)
                started[u] = True
            elif not done[u] or done[u] is False:
                    return "cycle detected" 
        done[node] = True               

One way we can detect a cycle is to initialize two sets that store the current state of vertex v. If v is started but not done that means there is a cycle because supposedly every vertex should be started if they have no cycle, however, if there is a cycle and which means we are reprocessing that vertex again, from that we can know it has a cycle.

Approaching to Problems

If the question asks min/max value question, it is most likely to be a DFS bottom-up approach because you'd have to dissect a big problem into a bunch of small/deepest problems

If the question asks the shortest/longest path question, it is most likely to be a BFS approach such that for every node we visit, we accumulate the steps that already happened before.

Strong Components

We can organize different clusters of nodes as a one-component

Original Graph vs Reduced Graph

The reduced graph represents each strong component in graph G

Def: Let G = (V,E) be a directed graph

For any u and v in V, we can say that u and v are strong component if

u = v

G contains a directed path from u to v and v to u