Graphs

• Directed graphs versus undirected graphs. Examples.
• Paths in graphs (directed and undirected). Examples.
• Connected versus not connected graphs. Examples.
• Connected digraphs for which there exists no path from a node A to a node B. Examples.

Graph representations

• adjacency list
  • each vertex stores a list of adjacent neighbors
• adjacency matrix
  • n by n matrix that has a row for each vertex and a column for each vertex
  • a 1 in entry ij if an edge exists from i to j and a 0 otherwise
• incidence matrix
  • m by n matrix that has a row for each edge and a column for each vertex
    • a 1 in entry if the vertex in that column is an endpoint of the edge in that rowand a 0 otherwise

Graph traversals

Start at a node v and "visits" all the nodes that can be reached by (un)directed paths from v.

DFS and BFS

• Depth-first search (DFS) from node v: from each node, follow a path as far as you can, while visiting only vertices that you have not previously seen. When you reach a previously visited vertex, back up to where you came from and visit the next child of the current node, if any exists. Otherwise back up and repeat this procedure. Stop when you are at v and have backed up from its last child.
  • Use recursion (and therefore implicitly a stack)
  • Example of how DFS works.
• Simulation of how the code is executed for a graph given by its adjacency list representation.
• Breadth-first search (BFS) from node v: visiting by layers
  • Uses a queue!

Pseudocode: DFS and BFS

from CLRS

Pseudocode: DFS

Maintains:

• color: white (initially), gray (discovered), black (finished)
• pi: predecessor (parent in tree being built)

For this class:

• we will always perform DFS from a specific node -- what changes in the pseudocode?
• we will not keep track of gray vs black; instead, just keep track of what's been explored
• we will not keep track of predecessor in the implementation

Pseudocode: BFS

Maintains:

• color: white (initially), gray (discovered), black (finished)
• d: distance from starting node
• pi: predecessor (parent in tree being built)

Note:

• we also do not need to keep track of gray vs black; instead, just keep track of what's been explored
• we will not keep track of distance or predecessor in the implementation

Application to Connectivity problems

• Decide if an undirected graph is connected.
• Decide if there exists a path from a given node v to another node u in a directed graph.
• Decide if there exists a node that cannot be reached from a node v, in a directed graph.
• List all the nodes reachable from a given node v.
• Interpretation for computer networks, road networks, etc.