> For the complete documentation index, see [llms.txt](https://zike.gitbook.io/princeton-algorithms-notebook-python/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zike.gitbook.io/princeton-algorithms-notebook-python/ii.1.1-undirected-graphs.md). # II.1.1 Undirected Graphs Algorithm II Week 1: Undirected Graphs ## Graph **Graph**. Set of vertices connected pairwise by edges. ### Some Problems * **Path**. Is there a path between s and t ? * **Shortest path**. What is the shortest path between s and t ? * **Cycle**. Is there a cycle in the graph? * **Euler tour**. Is there a cycle that uses each edge exactly once? * **Hamilton tour**. Is there a cycle that uses each vertex exactly once. * **Connectivity**. Is there a way to connect all of the vertices? * **MST**. What is the best way to connect all of the vertices? * **Biconnectivity**. Is there a vertex whose removal disconnects the graph? * **Planarity**. Can you draw the graph in the plane with no crossing edges? * **Graph isomorphism**. Do two adjacency lists represent the same graph? ### Graph API ``` Class Graph: void add_edge(int v, int w) list adj(inv) int num_of_V() int num_of_E() str to_string() ``` Representation 1. Set-of-edges representation (linked list or array)

2. Adjancency-matrix representation (vertex-indexed array of lists)

```java public class Graph { private final int V; private Bag[] adj; public Graph(int V) { this.V = V; adj = (Bag[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag(); } public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } public Iterable adj(int v) { return adj[v]; } } ``` ## Depth First Search & Breadth First Search Getting out of a maze.