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.