↓Skip to main content
  1. Sipping Go/

Graph Theory Algorithms for Competitive Programming

·3 mins
Table of Contents

Graph theory remain challenging, especially in the scope of competitive programming, this is your best friend to succeed your next challenge.

Course Syllabus #

Introduction #

  • Course Orientation!
  • Q/A Section & Discord Community
  • Graphs Code Repository C++ and Java!
  • Exercise Solutions - Code Repository!
  • Sharing Feedback

Setting Up Sublime [optional] #

  • Sublime Setup
  • Adding Master Header File
  • Escaping Online Judges
  • Common Code Snippets
  • Using Macros
  • Example Code Explained

Graph Representation #

  • Graphs Introduction
  • Graph Applications
  • Graph Key Terms
  • Adjacency List Representation
  • Adjacency List Representation with Node Class
  • Some Helpful Webinars [Optional]
  • Breadth First Search
  • BFS Code
  • BFS Shortest Path
  • BFS Shortest Path Code
  • Snakes and Ladder Solution
  • DFS Concept
  • DFS Code
  • Largest Island Solution

Cycle Detection #

  • Cycle Detection in Undirected Graph
  • Cycle Detection in Undirected Graph Code
  • Directed Graph - Cycle Detection
  • Directed Graph - Cycle Detection Code
  • Bipartite Graph
  • Bipartite Graph Code

Directed Acyclic Graph #

  • Directed Acyclic Graph & Topological Ordering
  • Topological Sort Algorithm
  • Topological Ordering BFS Code
  • Toplogical Order using DFS
  • Topological Ordering using DFS Code

Disjoint Set Union #

  • Disjoint Set Union Introduction
  • DSU Data Structure - Union & Find Ops
  • DSU Data Structure
  • DSU Implementation
  • Union by Rank
  • Path Compression Optimisation
  • DSU Dry Run

Minimum Spanning Trees #

  • Introduction to Minimum Spanning Trees!
  • Prim’s Algorithm
  • Prim’s Code
  • Kruskal’s Algorithm
  • Kruskal’s Code

Shortest Path Algorithms #

  • Introduction to Shortest Path Algorithms
  • Dijkshtra’s Algorithm
  • Dijkshtra’s Algorithm Code
  • Bellman Ford Algorithm
  • Bellman Ford Code
  • Floyd Warshall
  • Floyd Warshall Code
  • Solution - Shortest Path in Grid!

Travelling Salesman Problem #

  • Travelling Salesman Problem
  • Travelling Salesman Intution
  • TSP Brute Force
  • TSP DP + Bitmasking

Flood Fill #

  • Flood Fill Introduction
  • Number of Islands
  • Coloring Islands
  • Biggest Island
  • Make Largest island

Multi - Source BFS #

  • Introduction to Multi Source BFS
  • Problem on Multi Source BFS
  • Bonus Problem on Multi Source BFS
  • 0/1 BFS

DFS-Tree and Backedges #

  • Introduction to DFS tree and Backedges
  • DFS Tree and backedges in Undirected graph
  • DFS Tree and Backedges in Directed and Undirectde graphs
  • Print cycle in a graph

Articulation Points & Bridges #

  • Introduction and definitions
  • Discovered Time
  • Lowest Time or Low Link
  • Algorithm
  • Coding the Algorithm

Strongly Connected Components #

  • Introduction to Topological Order and Strongly Connected Components
  • Algorithm and Code to find Topological Ordering
  • Introduction to Strongly Connected Component
  • Condensed Component Graph
  • Kosaraju Algorithm for Strongly Connected Component
  • Kosaraju Algorithm for Strongly Connected Component Code

Trees #

  • Introduction and properties of trees
  • DFS on trees
  • Print all ancestors in a tree

Euler Tour #

  • Introduction
  • Applications
  • Code

LCA #

  • Introduction
  • LCA (Brute Force)
  • LCA using Binary Lifting

Re-rooting of trees #

  • Introduction and brute force
  • Approach to re root the tree
  • Code for re rooting of the tree

Dynamic Programming On Trees #

  • DP introduction
  • Vertex Cover (greedy)
  • Definitions and Rules
  • Vertex Cover DP
  • DP code (Recursion + Memoisation)
  • DP on trees using DFS
  • DP on trees using bfs
  • Tree Diameter CSES
  • Tree Diameter (code)
  • Nitpick
  • Distance Tree 1
  • Distance Tree (code)
  • Try These

Network Flow #

  • Introduction to Network
  • Introduction to Maximum Flow in a Network
  • Residual Networks and Augmenting Paths
  • Ford-Fulkerson and Edmond-Karp Algorithm
  • Dinic’s Algorithm
  • Dinic’s Algorithm Code
  • Applications of Max Flow as Maximum Bipartite Matching

Bonus : Graph + Data Structures #

  • Board Game
  • Board Game Code
↑