# Graph

### Typical graph problems

1. **Graph traversal problems**: these problems require traversing the graph in some specific order, such as DFS or BFS.
2. **Shortest path problems**: these problems require finding the shortest path between two vertices in the graph, such as Dijkstra's algorithm or Bellman-Ford algorithm.
3. **Minimum spanning tree problems**: these problems require finding a minimum-weight spanning tree of the graph, such as Kruskal's algorithm or Prim's algorithm.
4. **Cycle detection problems**: these problems require detecting whether the graph contains a cycle or not, such as Tarjan's algorithm or Kosaraju's algorithm.
5. **Topological sorting problems**: these problems require finding a valid topological ordering of the vertices in a directed acyclic graph, such as Kahn's algorithm or DFS-based algorithm.
6. **Bipartite graph problems**: these problems require determining whether a graph is bipartite or not, such as the coloring algorithm or BFS-based algorithm.
7. **Connectivity problems**: these problems require determining the connectivity of the graph, such as finding strongly connected components or articulation points.

### Top Leetcode graph problems

1. Number of Islands
2. Course Schedule (and Course Schedule II)
3. Clone Graph
4. Word Ladder (and Word Ladder II)
5. Surrounded Regions
6. Graph Valid Tree
7. Pacific Atlantic Water Flow
8. Redundant Connection (and Redundant Connection II)
9. Perfect Squares
10. Shortest Path in a Grid with Obstacles Elimination

### Top graph algorithms

1. **Depth-first search (DFS)**: This algorithm can be used to traverse a graph and explore its vertices and edges. DFS can also be used for topological sorting, cycle detection, and finding strongly connected components.
2. **Breadth-first search (BFS)**: This algorithm can be used to traverse a graph and explore its vertices and edges, similar to DFS. BFS can also be used for finding the shortest path between two vertices in an unweighted graph.
3. **Dijkstra's algorithm**: This algorithm can be used to find the shortest path between two vertices in a weighted graph. It works by iteratively selecting the vertex with the smallest distance from the source vertex and updating the distances of its neighbors.
4. **Bellman-Ford algorithm**: This algorithm can be used to find the shortest path between two vertices in a weighted graph, even if the graph contains negative-weight edges. It works by relaxing the edges of the graph repeatedly until the shortest paths are found.
5. **Floyd-Warshall algorithm**: This algorithm can be used to find the shortest path between all pairs of vertices in a weighted graph. It works by considering all possible intermediate vertices and updating the shortest distances accordingly.
6. **Kruskal's algorithm**: This algorithm can be used to find the minimum spanning tree of a weighted undirected graph. It works by iteratively adding the smallest edge that does not create a cycle until all vertices are connected.
7. **Prim's algorithm**: This algorithm can also be used to find the minimum spanning tree of a weighted undirected graph. It works by iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.
8. **Tarjan's algorithm**: This algorithm can be used to find the strongly connected components of a directed graph. It works by performing a DFS and maintaining a stack of visited vertices.


---

# 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://coding.bea.ai/graph.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.