# II.1.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)<img src="/files/-LNjsN6b1YewFgpxc_Hb" alt="" data-size="original">
2. Adjancency-matrix representation (vertex-indexed array of lists) &#x20;

   <img src="/files/-LNjsTEfNENojrrD7hRS" alt="" data-size="original">

```java
 public class Graph {
   private final int V;
   private Bag<Integer>[] adj;
   public Graph(int V)
   {
      this.V = V;
      adj = (Bag<Integer>[]) new Bag[V];
      for (int v = 0; v < V; v++)
         adj[v] = new Bag<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];  }
}
```

## &#x20;Depth First Search & Breadth First Search

Getting out of a maze.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zike.gitbook.io/princeton-algorithms-notebook-python/ii.1.1-undirected-graphs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.