Review Intro to Algorithms (Graph)

2 min readDec 29, 2018

Graph basics

Vertex (V), Edge (E)

Undirected and directed graph: for undirected graph, there is a handshaking lemma, sum(degree(v)) = 2|E|

Adjacency list: O(|V|+|E|) * w where w is the word size. The advantage is that 1) for sparse adjacency matrix; 2) multiple graphs can use the same nodes

Adjacency matrix: O(V²) * 1bit, good for dense matrix

OOP: one graph use one set of nodes, good for clean code

Breadth-first search (BFS)

Graph representation: adjacency list

Goal: traversal the connected component of one graph from one starting node level by level

Application: find the shortest path from a starting node to any node (shortest path from me to some person on Facebook)

Psudo code:

When frontiers are stored in a list:

# a graph is represented in an adjacency list, adj[key] = list
level = {‘s’: 0}
parent = {‘s’: None}
frontiers = [‘s’]while frontiers:
    next_frontiers = []
    for s in frontiers:
        for v in adj[v]:
            if v not in level:
                level[v] = level[s] + 1
                parent = {s: v}
                next_frontiers.append(v)
    frontiers = next_frontiers

When frontiers are stored in a queue:

from collections import deque
level = {'s': 0}
parent = {'s': None}
frontiers = queue()
frontiers.append('s')while frontiers:
    s = frontiers.popleft()
    for v in adj[s]:
        if v not in level:
        level[v] = level[s] + 1
        parent[v] = s
        frontiers.append(v)

Both of them are in O(|E|) time, linear time. If level is implemented in an array with True or False flags, the time is O(V+E).

Depth-first search (DFS)

BFS will find the shortest path from a given vertex, while DFS won’t find it. Instead, DFS finds the dependency (start time and finishing time). It is more common to have a DFS-visit function for a single vertex and a DFS-main function to loop vertices. The time complexity is also O(V+E).

Can be used to classify edges: tree, forward, back and cross. Only tree edges are in the path of DFS. In other words, DFS generate a tree through tree edges. One application is to detect cycles in graphs. A graph is cyclic if and only if back edges exist.

Undirected graph only has tree edges and back edges.

I guess one question I have is whether it is i possible to find dependencies when the directed graph is created. Why do we have to DFS to find them after waiting for the graph is built? Maybe an example would be helpful to understand the need of building a graph and then perform BFS and DFS to do different things on the graph.

Topological sort

Works for directed acyclic graph (DAG). Find the dependency order, from no dependency to source. Reverse order of finishing time.

Review Intro to Algorithms (Graph)

Written by regularizer