# 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


---

# 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://blog.gomchik.com/tech/c++/algorithms.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.