Week 6: Graph Algorithms

A graph is informally thought of as a collection of points in a plane called vertices or nodes, some of which may be connected by line segments called edges.

Formally a graph $G = (V, E)$ is defined by a set of ordered pairs. Edges may be directed, if $(v, e) \ne (e, v)$ and called a digraph, or undirected. They may also be weighted or unweighted.

A complete graph is one where every pair of its vertices is connected by an edge.
A graph with relatively few possible edges missing is called dense, and one with few edges is called sparse.

A tree is a connected undirected graph with no cycles.

Graph representations:

Adjacency list: Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices.
Store graph: $\mathcal{O}(|V| + |E|)$
Add vertex: $\mathcal{O}(1)$
Add edge: $\mathcal{O}(1)$
Remove vertex: $\mathcal{O}(|E|)$
Remove edge: $\mathcal{O}(|V|)$
Determine whether vertices x and y are adjacent: $\mathcal{O}(|V|)$

Slow to remove vertices and edges, because it needs to find all vertices and edges

Adjacency matrix: A two dimensional matrix, in which the rows represent source vertices and columns represent destination vertices.
Store graph: $\mathcal{O}(|V|^2)$
Add vertex: $\mathcal{O}(|V^2|)$
Add edge: $\mathcal{O}(1)$
Remove vertex: $\mathcal{O}(|V^2|)$
Remove edge: $\mathcal{O}(1)$
Determine whether vertices x and y are adjacent: $\mathcal{O}(1)$

Slow to add or remove vertices, because matrix must be resized/copied

---

DFS and BFS are both used as general problem space searching methods.

Input: A search problem, represented as a graph.
Output: An ordered list of actions to get from a start state to a goal state.

Depth First Search

Idea: Begin at an arbitrary or start vertex. Then explore as far as possible along each connected branch before backtracking.

Use a stack to keep track of vertices needing to be processed.

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges.

Applications:

• Finding connected components
• Topological sorting
• Maze generation
• Adversarial games

Complexity

Breadth First Search

Idea: Begin at an arbitrary or start vertex. Explore all of it's neighbors before moving to the next layer of depth.

Use a queue to keep track of vertices needing to be processed.

Time and space complexity:

Time: $\mathcal{O}(|V| + |E|)$ in the worst case, since every vertex and every edge will be explored.
Space: $\mathcal{O}(|V|)$, since we need to keep a queue of the vertices to visit.