Graphs

The idea behind this is simple: we iterate through each level of the tree, visiting all of the nodes in that level from left to right.

The steps for pre-order traversal are:

1. Start at the root. Visit the root.
2. If there is a left child, go left and recurse.
3. Otherwise, go right and recurse.

The steps for in-order traversal are:

1. If there is a left child, go left and recurse.
2. Otherwise if there is no left child, visit the node.
3. If there is a right child, go right and recurse.

In other words, here we first go down the left branch, and then we print:

The steps for post-order traversal are:

1. If there is a left child, go left and recurse.
2. Otherwise if there is a right child, go right and recurse.
3. Finally, visit the node.

Depth first search explores a neighbor’s subgraph completely before moving on to the next neighbor. In this way, it is called “depth-first” because you go as deep as possible for each path:

The runtime of depth-first search is \(\Theta (V+E)\), where \(V\) is the number of vertices and \(E\) is the number of edges.

Breadth first search explores each child first before moving on, similar to the level search for trees:

We also need a data structure to represent our graph in code. An adjacency list is an array where each index is a vertex number. Then, each element in the array is a list representing all of the vertices adjacent to that particular vertex.

DFS and BFS both gets the job done, but which one is more efficient at doing so?

DFS is worse for spindly graphs, as the call stack gets very deep. On the other hand, BFS is worse for absurdly bushy graphs, as the queue gets very large.

Say we want to find the shortest path between some vertex and every other vertex. To do so, we can utilize BFS.

We first initialize a queue with the starting vertex. Then, we repeat the following steps until the queue is empty:

1. Dequeue a vertex v from the queue.
2. For each unmarked neighbor n of that vertex, mark the neighbor and add it to the queue.
   • Set edgeTo[n] = v.
   • Set distTo[n] = distTo[v] + 1.

In the real world, however, different edges have different weights. For example, if we model a real-world map as a graph, longer paths should have higher weights:

The problem is that since our BFS implementation doesn’t consider these weights, we get the wrong result:

Say we want to consider the union of the shortest path from some source vertex to every other vertex:

We observe that the solution will always be a tree. This is known as the shortest paths tree (SPT) of a graph. The SPT of a graph will store the edges connecting each node (edgeTo) as well as the distance of each node from the source (distTo).

The idea behind Dijkstra’s algorithm is that we visit vertices in closest first order, building the SPT as we go. Visitng nodes in closest first order means that instead of using a queue like we did for BFS, we use a priority queue, prioritizing weights that are smaller (paths that are shorter).

First, we insert all of the vertices of our graph into the priority queue. Their starting weights will be infinity, since we don’t know of any path to any of them yet. Then, repeating until the queue is empty, we remove the closest vertex from the priority queue and relax all edges pointing from that vertex, modifying distTo and edgeTo as necessary:

A cut is an assignment of a graph’s nodes to two non-empty sets. A crossing edge is an edge which connects a node from one set to a node from the other set:

The cut property states that given any cut, the minimum weight crossing edge must be in the minimum spanning tree.

We start from some arbitrary start node. Then, out of all the edges that has one node inside the current MST, we add the shortest one to the MST. Repeat this until we get \(V-1\) edges:

Prim’s works because if we consider all the nodes connected to the start node as one side, and all the other nodes as the other side, the cut property tells us that the edge chosen must be in the MST.

We consider edges in order of increasing weight. Add them to the MST unless a cycle is created. Repeat until we get \(V-1\) edges:

To check if adding an edge creates a cycle, we can use a weighted quick union to store what connections we have.

A topological sort of a directed graph returns an ordering that ensures that if there is an edge pointing from vertex v to vertex w, v appears before w in the ordering. In other words, we are sorting our nodes so that they appear in an order consistent with the edges:

To find the topological sort, we can perform a DFS postorder traversal on every vertex with indegree 0, storing the postorder nodes in a list. Then, the topological ordering is given by the reverse of the list:

This algorithm takes \(O(V+E)\) time.

Additionally, a topological sort exists only if the graph is a directed acyclic graph.

The problem with Dijkstra’s is that it fails when trying to find a shortest path on a graph with negative weights. However, for the specific case of working with DAGs, we can solve this by visiting the vertices in topological order and relaxing all of its edges when we visit it:

The runtime for this algorithm takes \(O(V+E)\) time.