Time: $O(V+E)$. Used for shortest path in unweighted graphs, finding connected components.

Depth-First Search (DFS):

Explores as far as possible along each branch before backtracking. Uses a Stack (or recursion).
Algorithm: Start at source $s$, visit $s$, push $s$ to stack. While stack not empty, pop $u$, for each unvisited neighbor $v$ of $u$, visit $v$, push $v$ to stack.
Time: $O(V+E)$. Used for topological sort, finding connected components, cycle detection.

Minimum Spanning Tree (MST):

A subgraph of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Prim's Algorithm:
- Grows the MST from an arbitrary starting vertex. At each step, adds the cheapest edge connecting a vertex in the MST to a vertex outside the MST.
- Uses a min-priority queue.
- Time: $O(E \log V)$ with binary heap, $O(E+V \log V)$ with Fibonacci heap.
Kruskal's Algorithm:
- Sorts all edges by weight in non-decreasing order. Iterates through sorted edges, adding an edge to the MST if it does not form a cycle with already added edges.
- Uses Disjoint Set Union (DSU) data structure to detect cycles efficiently.
- Time: $O(E \log E)$ or $O(E \log V)$ (since $E \le V^2$, $\log E$ is $2 \log V$).

Shortest Path Algorithms:

Dijkstra's Algorithm:
- Single-source shortest paths for graphs with non-negative edge weights.
- Uses a min-priority queue to always extract the unvisited vertex with the smallest known distance.
- Time: $O(E \log V)$ with binary heap, $O(E+V \log V)$ with Fibonacci heap.
Bellman-Ford Algorithm:
- Single-source shortest paths for graphs with potentially negative edge weights. Can detect negative cycles.
- Relaxes all edges $V-1$ times. If a path can still be relaxed in the $V$-th iteration, a negative cycle exists.
- Time: $O(VE)$.
Floyd-Warshall Algorithm:
- All-pairs shortest paths for graphs with positive or negative edge weights (no negative cycles).
- Dynamic Programming approach: $dist[i][j][k]$ is shortest path from $i$ to $j$ using intermediate vertices from $\{1, \dots, k\}$.
- Time: $O(V^3)$.
A* Search Algorithm:
- Finds shortest path in a graph using a heuristic function $h(n)$ to estimate cost from $n$ to goal.
- Evaluates nodes based on $f(n) = g(n) + h(n)$, where $g(n)$ is cost from start to $n$.
- If $h(n)$ is admissible (never overestimates), A* finds optimal path.
- Time: Depends on heuristic; can be exponential in worst case, but often much faster.

Topological Sort:

A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $u \to v$, vertex $u$ comes before vertex $v$ in the ordering.
Kahn's Algorithm: Uses in-degrees of vertices and a queue.
1. Compute in-degree for all vertices.
2. Enqueue all vertices w