Tech Blogs
  • Vivek bhargav
  • Books
    • Seven Databases In Seven Weeks
      • Factors to consider
      • Genres of databases
      • Important questions
      • PostGreSQL
  • Tech
    • C++
      • Type Conversions
      • String
      • Vector
      • Set
      • Unordered Set
      • Map
      • Unordered Map
      • Queue
      • Priority Queue
      • Union find
      • Algorithms
      • Matrix to Graph
      • Trie
      • Dijkstra
      • Math
      • Utils
    • Database Transactions
      • A Simple Transaction Analysis
      • Implementation of Isolation Levels
      • Isolation Levels
      • Isolation
      • Storage Types
      • Transaction Atomicity and Durability
    • Java
      • Important Questions
      • Spring MVC
    • Program execution
      • Node.js
      • Runtimes
    • System Design
      • Basic Terminologies
      • CAP Theorem
      • Normalization of Database
      • Useful Reads
  • Personal Finance
    • Asset Classes
      • Equity instruments
      • Debt instruments
Powered by GitBook
On this page
  1. Tech
  2. C++

Algorithms

#include <algorithm>          // Include algorithm (std namespace)

min(x, y);                    // min out of x and y
max(x, y);                    // max out of x and y

swap(x, y);                   // swap values of variables x and y


sort(a.begin(), a.end());     // sort vector or deque

sort(a, a+n);                 // sort array a[0]..a[n-1] by <

reverse(a.begin(), a.end());  // reverse vector or deque

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

PreviousUnion findNextMatrix to Graph

Last updated 1 month ago

Link