Graphs continued

Data structures for graphs

Edge list: unordered list of all edges. No efficient way to locate a particular edge (u, v), or the set of all edges incident to a vertex v.
Schematic representation of the edge list structure for an undirected graph:
Adjacency list: For each vertex v, store a list of all edges that are incident to the vertex.
Schematic representation of adjacency list for an undirected graph:
Adjacency map: Similar to adjacency list, but use a map instead of a list to store the edges incident to a vertex, which allows for O(1) expected time to access a particular edge.
Schematic representation of adjacency map for an undirected graph:
Adjacency matrix: An n x n matrix for a graph with n vertices. Each slot is for a potential edge (u, v) for a particular pair of vertices u and v. If no such edge exists, the slot is empty. Any edge can be accessed in worst-case O(1) time.
Schematic representation of adjacency matrix for an undirected graph:

Check your understanding

Consider the graph represented by the following adjacency matrix.

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?

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.

#ifndef GRAPH_H
#define GRAPH_H

#include <map>
#include <list>
#include <utility>
#include <iostream>

using namespace std;

template <typename V, typename E>
class Graph {
private:
    // Forward declare ActualVertex and ActualEdge
    class ActualVertex;
    class ActualEdge;

//---------- nested ActualVertex class ---------
    class ActualVertex {
    public:
        typedef std::map<ActualVertex*, ActualEdge*> IncidenceMap;
        V element;
        IncidenceMap outgoing;
        IncidenceMap incoming;
        typename std::list<ActualVertex>::iterator pos;  // needed to erase from vertex_list
        ActualVertex(V elem) : element{elem} {}
    }; //---------- end of ActualVertex class ---------

//---------- nested ActualEdge class ---------
    class ActualEdge {
    public:
        ActualVertex* origin;
        ActualVertex* dest;
        int weight;
        E element;
        typename std::list<ActualEdge>::iterator pos;    // needed to erase from edge_list
        ActualEdge(ActualVertex* u, ActualVertex* v, int w, E e)
            : origin{u}, dest{v}, weight{w}, element{e} {}
    }; //---------- end of ActualEdge class ---------

public:
    //---------- nested Vertex class ---------
    class Vertex {
    private:
        friend Graph;
        ActualVertex* vert{nullptr};
        Vertex(const ActualVertex* v) : vert{const_cast<ActualVertex*>(v)} {}

public:
        Vertex() {}
        V& operator*() const { return vert->element; }
        V* operator->() const { return &(vert->element); }
        bool operator==(Vertex other) const { return vert == other.vert; }
        bool operator!=(Vertex other) const { return vert != other.vert; }
        bool operator<(Vertex other) const { return vert < other.vert; }  // Arbitrary comparison
    };

//---------- nested Edge class ---------
    class Edge {
    private:
        friend Graph;
        ActualEdge* edge{nullptr};
        Edge(const ActualEdge* e) : edge{const_cast<ActualEdge*>(e)} {}

public:
        Edge() {}
        int weight() const { return edge->weight; }
        E& operator*() const { return edge->element; }
        E* operator->() const { return &(edge->element); }
        bool operator==(Edge other) const { return edge == other.edge; }
        bool operator!=(Edge other) const { return edge != other.edge; }
        bool operator<(Edge other) const { return edge < other.edge; }  // Arbitrary comparison
    };

private:
    std::list<ActualVertex> vertex_list;
    std::list<ActualEdge> edge_list;
    bool directed;

public:
    // Creates a new graph (directed or undirected, as specified by argument)
    Graph(bool is_directed) : directed{is_directed} {}

// Returns true if graph is directed, false otherwise
    bool is_directed() const { return directed; }
    
    // Returns the number of vertices in the graph
    int num_vertices() const { return vertex_list.size(); }

// Returns the number of edges in the graph
    int num_edges() const { return edge_list.size(); }
    
    // Returns a list of Vertex tokens
    list<Vertex> vertices() const {
        list<Vertex> result;
        for (const ActualVertex& v : vertex_list)      // Note: reference variable to get correct pointer
            result.push_back(Vertex(&v));
        return result;
    }

// Returns a list of Edge tokens
    list<Edge> edges() const {
        list<Edge> result;
        for (const ActualEdge& e : edge_list)         // Note: reference variable to get correct pointer
            result.push_back(Edge(&e));
        return result;
    }

// Return true if there exists an edge from u to v, false otherwise
    bool has_edge(Vertex u, Vertex v) const {
        return (u.vert->outgoing.count(v.vert) == 1);
    }
    
    // Return the edge from u to v; undefined behavior if no such edge exists
    Edge get_edge(Vertex u, Vertex v) const {
        return Edge(u.vert->outgoing.find(v.vert)->second); // find returns {ActualVertex*,ActualEdge*}
    }
    
    // Returns the number of outgoing (or incoming) edges for Vertex v
    int degree(Vertex v, bool outgoing = true) const {
        typename ActualVertex::IncidenceMap& adj(outgoing || !directed ? v.vert->outgoing : v.vert->incoming);
        return adj.size();
    }

// Returns a list of outgoing (or incoming) Vertex tokens for neighbors of Vertex v
    list<Vertex> neighbors(Vertex v, bool outgoing = true) const {
        list<Vertex> result;
        typename ActualVertex::IncidenceMap& adj(outgoing || !directed ? v.vert->outgoing : v.vert->incoming);
        for (auto p : adj)                          // p is {ActualVertex*,ActualEdge*} pair
            result.push_back(Vertex(p.first));
        return result;
    }
    
    // Returns a list of outgoing (or incoming) Edge tokens for Vertex v
    list<Edge> incident_edges(Vertex v, bool outgoing = true) const {
        list<Edge> result;
        typename ActualVertex::IncidenceMap& adj(outgoing || !directed ? v.vert->outgoing : v.vert->incoming);
        for (auto p : adj)                          // p is {ActualVertex*,ActualEdge*} pair
            result.push_back(Edge(p.second));
        return result;
    }
    
    // Returns the (origin,destination) pair for Edge e
    pair<Vertex,Vertex> endpoints(Edge e) const {
        return {Vertex(e.edge->origin), Vertex(e.edge->dest)};
    }
    
    // Returns the opposite endpoint to Vertex v for Edge e
    Vertex opposite(Edge e, Vertex v) const {
        return Vertex(v.vert == e.edge->origin ? e.edge->dest : e.edge->origin);
    }

// Create a new vertex storing given element, and return Vertex token
    Vertex insert_vertex(V elem) {
        auto iter = vertex_list.insert(vertex_list.end(), ActualVertex(elem));
        iter->pos = iter;             // save new vertex's position within vertex_list
        return Vertex(&*iter);        // wrap the pointer to newly stored ActualVertex
    }

// Inserts new edge from u to v, storing given element, and given weight (default 1)
    // If edge already exists, updates weight and element for that existing edge.
    // Returns Edge token
    Edge insert_edge(Vertex u, Vertex v, int weight = 1, E elem = E()) {
        if (u.vert->outgoing.count(v.vert) == 0) {  // new edge
            auto iter = edge_list.insert(edge_list.end(), ActualEdge(u.vert, v.vert, weight, elem));
            iter->pos = iter;                   // save new edge's position within edge_list
            ActualEdge* stored = &*iter;        // pointer to newly stored ActualEdge
            // now add edge to adjacency maps for vertices
            u.vert->outgoing[v.vert] = stored;  // outgoing edge for u
            typename ActualVertex::IncidenceMap& adj{directed ? v.vert->incoming : v.vert->outgoing};
            adj[u.vert] = stored;               // incoming edge for v (if directed graph)

return Edge(stored);
        } else {                                     // update existing edge
            Edge e{get_edge(u,v)};
            e.edge->weight = weight;
            e.edge->element = elem;
            return e;
        }
    }

// Remove edge e from the graph
    void erase(Edge e) {
        // first remove the edge from the endpoint adjacencies
        ActualVertex *u{e.edge->origin}, *v{e.edge->dest};
        u->outgoing.erase(v);
        typename ActualVertex::IncidenceMap& adj{directed ? v->incoming : v->outgoing};
        adj.erase(u);

// now remove the edge from the edge list
        edge_list.erase(e.edge->pos);
    }

// Remove vertex v, and all its incident edges, from the graph
    void erase(Vertex v) {
        for (auto p : v.vert->outgoing) {         // p is {ActualVertex*,ActualEdge*} pair
            typename ActualVertex::IncidenceMap& adj{directed ? p.first->incoming : p.first->outgoing};
            adj.erase(v.vert);                    // remove edge from opposite vertex's map
            edge_list.erase(p.second->pos);       // remove edge from overall edge_list
        }
        for (auto p : v.vert->incoming) {         // for undirected graph, incoming is empty
            p.first->outgoing.erase(v.vert);
            edge_list.erase(p.second->pos);
        }
        
        // now remove the vertex from the vertex list
        vertex_list.erase(v.vert->pos);
    }
};

#endif

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:

Discovery edge (tree edge): an edge used to discover a new vertex v in DFS.
All other edges are non-tree edges, which take us to a previously visited vertex:

Back edge: connects a vertex to an ancestor in the DFS tree
Forward edge: connects a vertex to a descendant in the DFS tree
Cross edge: connects two vertices that are neither ancestors nor descendants of each other

Let's perform DFS on the following graph:

DFS(G, vertex A) is called. Vertex A is marked as explored.
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.
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.
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.
Vertex F is labeled explored. The unexplored edge is from F to D. The recursive call to vertex D occurs next.
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.
Backtrack to F. Since there is no unexplored edges at F, backtrack to E.
There is one unexplored edge from E to C. Recursively call vertex C.
Vertex C is labeled explored. The A to C edge is a back edge. No recursive call occurs.
All DFS calls except the first have iterated through incident edges, so each completes.
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.

BFS starts at vertex s, which is at level 0. In the first round, we mark all vertices adjacent to the start vertex s as "visited." These vertices are placed into level 1.
In the second round, we allow explorers to visit all vertices adjacent to level 1 vertices, and place these vertices into level 2, while marking them as "visited."
This process continues in similar fashion, terminaitng when no new vertices are found in a level.

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++

// Performs BFS of the undiscovered portion of Graph g starting at Vertex s
template <typename V, typename E>    
void bfs(const Graph<V,E>& g, typename Graph<V,E>::Vertex s, VertexVertexMap<V,E>& discovered) {
    VertexList<V,E> level;
    level.push_back(s);                                 // first level includes only s
    while (!level.empty()) {
        VertexList<V,E> next_level;                     // prepare to gather newly discovered vertices
        for (auto u : level) {                          // for every u in the previous level
            for (auto v : g.neighbors(u)) {             // for every outgoing neighbor of u
                if (discovered.count(v) == 0) {         // v was previously undiscovered
                    discovered[v] = u;                  // mark v as discovered via u
                    next_level.push_back(v);            // v will be further considered in next pass
                }
            }
        }
        swap(level, next_level);                         // continue by exploring 'next' level
    }
}

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:

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.