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

• Binary Search Problems

• String Algorithms Problems

• Union Find Problems

• Sliding Window