Graph Representation

There are two parameters to represent, vertices and edges.

\text{Graph: } G = (V, E)

There are two methods of representation (mathematically):

1. Adjacency List

List all vertices.

• Each vertex has a list of adjacent vertices.

Note — Properties:

• Total Size: \Theta ( |V| + |E| )
• Better on sparse graphs¹1. Graphs where |E| is much closer to |V| than to |V|^2.

2. Adjacency Matrix

Store vertices in a square matrix

• Value in matrix is weight of edge

Note — Properties:

• Total Size: \Theta( |V|^2 )
• Better on dense graphs²2. Graphs where |E| is close to |V|^2..

Traversal Algorithms

Graph Traversal: Problem of visiting all nodes in a graph in a particular manner, updating/checking values along the way.

There are two elementary traversal strategies using brute-force algorithms:

1. Depth-First Search (DFS)
2. Breadth-First Search (BFS)

Note — Both provide efficient ways to visit each vertex and edge, they only differ in order of visiting.

Depth-First Search (DFS)

Visit vertices by always moving away from the last-visited vertex to an unvisited one. Backtracks if no adjacent unvisited vertex is available.

Note — Data Structure: Stack (FILO)

• Vertex pushed on when it’s reached for the first time.
• Vertex popped off when it becomes a dead end³3. i.e., no adjacent unvisited vertex..

Mathematically, we could phrase this as:

a_{1, 6} c_{2, 5} d_{3, 1} f_{4, 4} b_{5, 3} e_{6, 2}

Note — First subscript is the order something was popped-on, second subscript is order it was popped-off.

We aren’t done though, there’s the other portion to traverse:

g_{1,4} h_{2,3} i_{3,2} j_{4,1}

Now, we are truly done.

Pseudocode

ALGORITHM DFS(G)
    // Implements a depth-first search traversal of a given graph
    // Input: Graph G = <V, E>
    // Output: Graph G with its vertices marked with consecutive integers
    // in the order they're first encountered
    mark each vertex in V with 0 as a mark of being "unvisited"
    count \leftarrow 0
    for each vertex v in V do
        if v is marked with 0
            dfs(v)

ALGORITHM dfs(v)
    // visits recursively all the unvisited vertices connected to v
    count \leftarrow count \text{$+$} 1; mark v with count
    for each vertex w in V adjacent to v do
        if w is marked with 0
            dfs(w)

Analysis — Time complexity is \Theta(|V|^2) for adjacency matrix and \Theta(|V| + |E|) for adjacency list. Space complexity is O(|V|) for the recursion stack.

DFS Forest

Note — You can use the traversal’s stack to construct a tree-like graph, which we’ll call a DFS forest.

DFS Forest:

• Root: Starting vertex serves as the root of the first tree in a new forest.
• Tree Edge: When a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. This is called a tree edge.
  • Shown with black line.
• Back Edge: If algorithm encounters an edge leading to a previously-visited vertex other than its immediate predecessor, it is called a back edge, because it connects a vertex to an ancestor other than its parent.
  • Shown with dashed line.

Example: Graph to Stack to Forest

The traversal stack defines the parent-child relationships for the tree edges.

Constructing the DFS Forest from this stack, we get a tree where a connects to c, c connects to d and f, and back edges connect nodes to previously visited ancestors.

Note — For us, we’ll just look at the original graph to determine back-edges, as determining this from the traversal stack is a little more involved.

• We just use the traversal stack to build the easier tree edges.

Breadth-First Search

Visit verticies by moving across to all neighbors of last-visited vertex.

• Proceeds in a concentric mannger by visiting first all the vertices adjacent to a starting vertex.
• If there still remain unvisited vertices, algorithm is restarted at an arbitrary vertex of another connected component of the graph.

Instead of plunging deep, we explore layer by layer, visiting all neighbors of a node before moving to the neighbors’ neighbors.

Note — Data Structure: Uses queue (FIFO)

More Notes:

• Has same efficiency as DFS.
• Yield’s single ordering of vertices.
• Can be implemented with graphs represented as:
  • Adjacency Matrices: \Theta(|V|^2)
  • Adjacency Lists: \Theta(|V| + |E|)

Pseudocode

ALGORITHM BFS(G)
    // Implements a breadth-first search traversal of a given graph
    // Input: Graph G = <V, E>
    // Output: Graph G with its vertices marked with consecutive integers
    mark each vertex in V with 0
    count \leftarrow 0
    for each vertex v in V do
        if v is marked with 0
            bfs(v)

ALGORITHM bfs(v)
    // visits all the unvisited vertices connected to v
    count \leftarrow count \text{$+$} 1; mark v with count
    initialize a queue with v
    while the queue is not empty do
        for each vertex w in V adjacent to the front vertex do
            if w is marked with 0
                count \leftarrow count \text{$+$} 1; mark w with count
                add w to the queue
        remove the front vertex from the queue

Analysis — Time complexity is \Theta(|V|^2) for adjacency matrix and \Theta(|V| + |E|) for adjacency list. Space complexity is O(|V|) for the queue.

BFS Forest

Note — You can use the traversal’s queue to construct a tree-like graph.

Similar to DFS, tree edges are formed when a node discovers an unvisited neighbor. Cross edges (instead of back edges) can connect nodes on the same or adjacent levels.