# 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

Binary Search Problems

String Algorithms Problems

Union Find Problems

Sliding Window

Last updated