## Lecture 26 - 03/20

### Graphs

• Set of nodes/vertices connected pairwise by edges
• Directed vs undirected graphs
• Cyclic vs acyclic graphs
• Graphs with/without edge labels (edge weights)
• Path: sequence of vertices connected by edges
• Cycle: path whose first and last vertices are the same
• Two vertices are connected if there is a path between them
• Some graph computation problems:
• s-t Path. Is there a path between vertices s and t?
• Shortest s-t Path. What is the shortest path between vertices s and t?
• Cycle. Does the graph contain any cycles?
• Euler Tour. Is there a cycle that uses every edge exactly once?
• Hamilton Tour. Is there a cycle that uses every vertex exactly once?
• Connectivity. Is the graph connected, i.e. is there a path between all vertex pairs?
• Biconnectivity. Is there a vertex whose removal disconnects the graph?
• Planarity. Can you draw the graph on a piece of paper with no crossing edges?
• Isomorphism. Are two graphs isomorphic (the same graph in disguise)?

#### Graph Representation:

• When we want to have a graph connecting a series of labels (for example string labels), we can have map that assigns each label to an integer, and create a graph connecting these integers instead
• Graph API:
public interface Graph {
public Graph(int V);               // Create empty graph with v vertices
int V();                           // number of vertices
int E();                           // number of edges
...
}

• Representation 1: represent the graph with an adjacency matrix (for undirected graphs, each edge represented twice in the matrix - simpler algorithm but more space expensive)
• Representation 2: represent the graph as a collection/HashSet of all edges (pairs of ints and possibly an edge weight)
• Representation 3: represent the graph as an adjacency list (array of lists indexed by vertex number; each vertex's list contains all the vertices that the vertex has edges to)
Runtime for different methods based on representation:

Basic undirected graph adjacency list implementation:

public class Graph {
private final int V;

public Graph(int V) {
this.V = V;
for (int v = 0; v < V; v++) {
}
}

public void addEdge(int v, int w) {
}

}
}


#### Graph Algorithms

• Connectivity Algorithm:
• To check if two nodes s and t are connected, we can mark each vertex as we search (otherwise inefficient and risk of infinite cycles)
• Algorithm is:
• Mark s
• If s == t, return true
• Otherwise, check all of s's unmarked neighbors for connectivity to t
• Let's say we want to make a function Paths that takes in a graph and starting node, and then finds the path from that start node to any of the nodes of the graph, if it exists

• Class would look something like:
public class Paths {
public Paths(Graph G, int s);    // Find all paths in G starting from s
boolean hasPathTo(int v);        // is there a path from s to v?
Iterable<Integer> pathTo(int v); // path from s to v (if any)
}

• We can implement this with DFS:

• To do this, have array of booleans marked of size V$V$, tracking nodes that have been visited/marked
• Also have an array of ints edgeTo of size V$V$, such that for each vertex v in the graph, the integer at v's position in this array stores the previous vertex in the path from s to v
• For example, if the graph has nodes 1$1$ and 4$4$ connected by an edge, and in the DFS we travel from node 1$1$ to 4$4$, then we would say edgeTo[4] = 1
• Implementation like this:

public class DepthFirstPaths {
private boolean[] marked; // true iff vertex v connected to s
private int[] edgeTo;     // previous vertex from pa
private int s;            // starting node s

public DepthFirstPaths(Graph G, int s) {
...         // initialize variables
dfs(G, s);  // in constructor, do the dfs search recursively
}

private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}

boolean hasPathTo(int v) {
return marked[v] == true;
}

Iterable<Integer> pathTo(int v) {
// Start at v, travel to edgeTo[v] and add it to the list to return
// Repeat till at s
...
}
}

• runtime Θ(V+E)$\Theta(V+E)$:
• each vertex visited once, each visit is constant time, and each edge visited at most once
• We consider both V$V$ and E$E$ because algorithm linearly dependent on both of these; depending on the graph one of these terms could "overpower" the other
• space Θ(V)$\Theta(V)$