> For the complete documentation index, see [llms.txt](https://blog.gomchik.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.gomchik.com/tech/c++/algorithms.md).

# Graph Algorithms

#### Graph Terms

An undirected graph G is said to be **connected** if every pair of vertices in G is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called **disconnected**. G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. A graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected.

A directed graph is called

* **Weakly connected:** if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
* **Unilaterally connected:** if it contains a directed path from u to v OR a directed path from v to u for every pair of vertices u, v.
* **Strongly connected:** if it contains a directed path from u to v AND a directed path from v to u for every pair of vertices u, v.
* **Disconnected:** if replacing all of its directed edges with undirected edges produces a disconnected (undirected) graph.

#### Important Graph Algorithms

* BFS on a Tree
* DFS on a Tree
* BFS on a Graph
* DFS on a Graph
  * Disconnected Graph
  * Connected Graph
    * Weakly connected
    * Unilaterally connected
    * Strongly connected
* DFS on a Graph to detect cycle

Shortest path algorithms

* (Single pair of nodes) or (Single source node to all nodes)
  * Dijkstra => weighted graph (only positive weights)
    * E + Vlog(V)
  * Bellman Ford => weighted graph (can contain negative weights, can't contain negative cycle)
* All pair of nodes (both directions)
  * Floyd warshall => weighted graph (can contain negative weights, can't contain negative cycle)
* Topological Sort
* Minimum Spanning Tree
  * Kruskel
  * Prim

#### Trees

* Binary Trees
* BST (Binary Search Trees)
* Balanced Trees
* Min Heap, Max Heap
* Segment Trees
* Prefix Tree
* Trie
* Suffix Tree
* Binary Indexed Tree
* Dynamic Programming Problems
  * [Link](https://people.computing.clemson.edu/~bcdean/dp_practice)
* Binary Search Problems
* String Algorithms Problems
* Union Find Problems
* Sliding Window