Graphs continued

Data structures for graphs

Check your understanding

Consider the graph represented by the following adjacency matrix.

Adjacency matrix example
Exercise: How many degrees does vertex 1 have?

Answer: 4. Outgoing edge (c) and incoming edges (a, d, f) are incident to vertex 1.

Exercise: Which graph does the adjacency matrix represent?
  1. Graph 1
  2. Graph 2
  3. Graph 3

Answer: 2. The second graph correctly portrays the six directed edges from the matrix, for example with edge f going from 3 to 1.

C++ Implementation

Graph implementation based on the adjacency map representation.

Graph traversals

Graph traversal is a systematic procedure for exploring a graph by examining all vertices and edges. A traversal is efficient if it visits all the vertices and edges in linear time.

Graph traversal algorithms are key to answering questions about graphs involving reachability, that is, in determining how to travel from one vertex to another while following paths of a graph.

We will focus on two efficient graph traversal algorithms -- depth-first search and breadth-first search.

Depth-first search (DFS)

DFS explores as far as possible along each branch before backtracking.

Let's think of DFS as wandering in a maze with a string and a can of paint without getting lost. We begin at a starting vertex s in G, which we initialize by fixing one end of our string to s and painting s as "visited." The vertex s is now our "current" vertex. In general, if we call our current vertex u, we traverse G by considering an arbitrary edge (u, v) incident to the current vertex u. If the edge (u, v) leads to an unvisited vertex v, then we go to v and paint v as "visited", making v the current vertex and repeating the computation above. Eventually, we will get to a "dead end," that is, a vertex with no unvisited neighbors. At this point, we backtrack to a previously visited vertex u. We make u our current vertex and repeat the computation above for any edges incident to u that we have not yet considered. If all of u's incident edges lead to visited vertices, we again roll up our string and backtrack to the vertex that led us to u. We continue this process until we have visited all vertices reachable from the starting vertex s.

Algorithm DFS(G, u)
    Input: Graph G and a starting vertex u of G
    Output: A collection of vertices reachable from u in G

    Mark vertex u as visited
    For each of u's outgoing edges e = (u, v):
        If vertex v is not visited:
            Record edge e as the discovery edge for vertex v
            Recursively call DFS(G, v)
    

When performing DFS, these are the different kinds of edges:

Let's perform DFS on the following graph:

  1. DFS(G, vertex A) is called. Vertex A is marked as explored.
  2. Unexplored edges incident to vertex A are examined. The first leads to unexplored vertex B, so the edge is a labeled as a tree edge and DFS(G, vertex B) is called.
  3. Vertex B is labeled explored. The incoming edge is a tree edge and so is already explored. The outgoing edge leads to undiscovered vertex E.
  4. Vertex E is labeled explored. The unexplored edges from E to F and from E to C both connect to unexplored vertices. The recursive call for vertex F occurs next.
  5. Vertex F is labeled explored. The unexplored edge is from F to D. The recursive call to vertex D occurs next.
  6. Vertex D is labeled explored. The D to A edge connects D to an explored vertex and so is a back edge. No recursive call occurs.
  7. Backtrack to F. Since there is no unexplored edges at F, backtrack to E.
  8. There is one unexplored edge from E to C. Recursively call vertex C.
  9. Vertex C is labeled explored. The A to C edge is a back edge. No recursive call occurs.
  10. All DFS calls except the first have iterated through incident edges, so each completes.
  11. The for loop iterates through the remaining edges: A to C and C to D. Each is a back edge and so is already explored.

DFS implementation in C++

Breadth-first search (BFS)

While DFS is similar to a single person traversing through a maze, breadth-first search is more akin to sending out, in all directions, many explorers who collectively traverse a maze in a coordinated fashion.

A BFS proceeds in rounds and subdivides the vertices into levels.

Algorithm BFS(G, s):
    Input: Graph G and a starting vertex s of G
    Output: A collection of vertices reachable from s in G
    
    visited ← empty map
    level ← empty list
    next_level ← empty list

    // Initialize the first level with the start vertex
    level.push_back(s)
    visited[s] ← s    // Mark the start vertex as visited (can mark itself as parent)

    while level is not empty do:
        next_level ← empty list

        // Explore each vertex in the current level
        for each u in level do:
            for each v in neighbors(u) of G do:
                if v is not in visited then:
                    visited[v] ← u         // Mark v as visited via u
                    next_level.push_back(v)   // Add v to the next level

        // Move to the next level
        level ← next_level

Another way to implement BFS is to use a FIFO queue to represent the current fringe of the search. Starting with the source vertex in the queue, we repeatedly remove the vertex from the front of the queue and insert any of its unvisited neighbors to the back of the queue:

Algorithm BFS(G, s):
    Input: Graph G and a starting vertex s of G
    Output: A collection of vertices reachable from s in G

    Create an empty queue Q
    Enqueue s onto Q
    Mark s as visited
    While Q is not empty:
        Dequeue vertex u from Q
        For each of u's outgoing edges e = (u, v):
            If vertex v is not visited:
                Mark v as visited
                Enqueue v onto Q
    

BFS animation

BFS implementation in C++

More BFS and DFS animations

click here and here.

Check your understanding

Let's consider a breadth-first search starting at vertex A of the following directed graph:

BFS graph
Exercise: L0 = {A}. L1 = ?

Answer: {B, D}.

Exercise: L2 = ?

Answer: {G, E, F}.

Exercise: Assuming that neighbors are considered in alphabetical order, in what order are vertices discovered during the breadth-first search?

Answer: ABDFEGC.
A is added to L0. B is then added to L1 followed by D. Because B is the first vertex in L1, outgoing edge (B -> F) is used to add F to L2 before edges (D -> E) and (D -> G) are used to add E and G to L2. Finally, C is added to L3 using edge F -> C.