Basics of Graph Theory

Date: February 1, 2021
Conducted By: Utkarsh, Rishik and Hemant

Agenda

• What is a Graph?

  • Real-life examples and applications
  • Directed and undirected graphs
  • Weighted and unweighted graphs

• Common Terminologies

  • Nodes and Edges
  • Paths and Shortest Paths
  • Components
  • Levels and Neighbours

• Graph Representation

  • Adjacency Matrix
  • Adjacency List and its importance in contests

• Trees

  • Properties
    1. No Cycles
    2. Unique Path between any pair of nodes
    3. Connected graph
    4. N-1 edges, if there are N nodes
  • Importance of Trees

• Graph Traversals

  • Breadth First Search (BFS)
  • Depth First Search (DFS)
  • Visualisation + Code

Resources

• Path-finding Visualizer
• Codes
  • Graph Representation
  • BFS
  • DFS

Further Reading

• Graph Theory 1 - Hackerearth
• Algorithms Live! - Party with Trees
• William Fiset - Graph Theory Playlist

Practice Problems

• Graphs - HackerEarth
• DSA Learning Series - Graph Theory Basics - CodeChef
• Graph Theory - CSES
• CodeChef Prepare
  • Trees
  • DFS, BFS