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

- 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 verticespublic void addEdge(int v, int w); // add an edge v-wIterable<Integer> adj(int v); // vertices adjacent to vint V(); // number of verticesint 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;private List<Integer>[] adj;public Graph(int V) {this.V = V;adj = (List<Integer>[]) new ArrayList[V];for (int v = 0; v < V; v++) {adj[v] = new ArrayList<Integer>();}}public void addEdge(int v, int w) {adj[v].add(w);adj[w].add(v);}public Iterable<Integer> adj(int v) {return adj[v];}}

- 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 sboolean 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 sizeV , tracking nodes that have been visited/marked - Also have an array of ints
`edgeTo`

of sizeV , 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 and4 connected by an edge, and in the DFS we travel from node1 to4 , then we would say`edgeTo[4] = 1`

- For example, if the graph has nodes
Implementation like this:

public class DepthFirstPaths {private boolean[] marked; // true iff vertex v connected to sprivate int[] edgeTo; // previous vertex from paprivate int s; // starting node spublic DepthFirstPaths(Graph G, int s) {... // initialize variablesdfs(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) :- each vertex visited once, each visit is constant time, and each edge visited at most once
- We consider both
V andE because algorithm linearly dependent on both of these; depending on the graph one of these terms could "overpower" the other

- space
Θ(V)

- To do this, have array of booleans

- Class would look something like: