Chapter 3 – Graphs

My notes on the assigned sections of Chapter 3 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details many elements of Graphs.

A directed graph consists of nodes that are connected with a specific direction to their connections (edges). Generally a graph refers to an undirected graph. Some examples of graphs include transportation networks, communication networks, information networks, social networks, and dependency networks. Cycles come full circle back to their starting point. A tree is a connected graph that doesn't contain a cycle.

This section was very simplistic and I'd give it a 10/10 on readability and interestingness.

There are 2 algorithms for graph traversal: Breadth-First Search (BFS) and Depth-First Search (DFS). BFS can be thought of as starting at a node s and flooding “the graph with an expanding wave that grows to visit all nodes that it can reach”. Layers of the graph can be defined as L1,…,Ln. Both BFS and DFS have qualitatively similar levels of efficiency.

BFS:

R will consist of nodes to which s has a path
R = {s}
while there is an edge (u,v) where u∈R and v∉R
    add v to R

Depth first traversal can be thought of as being in a maze of rooms. You'd start from s and try the first path leading out of it to a different room. You'd keep following the path until you hit a dead end, in which case you'd backtrack to a room with an unexplored neighbor and resume from there.

DFS:

DFS(u):
    Mark u as “Explored” and add u to R
    For each edge (u, v) incident to u
        If v is not marked “Explored” then
            DFS(v)

This section was very readable, and I'd give it a 9/10 on both enjoyability and readability.