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.

Properties:

• Total Size: \Theta ( |V| + |E| )
• Better on sparse graphs

2. Adjacency Matrix

Store vertices in a square matrix

• Value in matrix is weight of edge

Properties:

• Total Size: ( n^2 )
• Better on dense graphs.

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)

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.

Data Structure: Stack (FILO)

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

Example

TODO Draw graph aecfdb

1. Push a (the start)
2. Push c (we’ll use alphabetic order to break ties)
3. Push d
4. Now a dead end, so…
5. Pop d (now back at c)
6. Push f
7. Push b
8. Push e
9. Now a dead end, so…
10. Pop e
11. Pop b
12. Pop f
13. Pop c
14. Pop a
15. Now, the stack is empty, which means we’ve traversed this entire connected graph.

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

TODO

DFS Forest

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

TODO Diagram

The traversal stack is: TODO

Constructing the DFS Forest from this stack, we get: TODO

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.

TODO Explain

Data Structure: Uses queue

Similar to a level-by-level tree traversal

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

BFS Forest

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

TODO Example