How to think in graphs: An illustrative introduction to Graph Theory and its applications

Graph theory can be difficult to understand
He meant Monte Cristo


Seven Bridges of Königsberg

Our area of interest
Seven bridges of Königsberg
Leonhard Euler (photo from Wikipedia)
Number of bridges
Examples of 2 bridge lands
Notice the new bridge
Lines are a bit twisty
Exactly two vertices have an odd degree in the illustration at the left, and all vertices are of an odd degree in illustration at the right
Undirected Graph

Graph representation: Intro

Just a sample
Colors are just for bright visualization

Intro to Graph representation and binary trees (Airbnb example)

A glimpse on Airbnb Homes Search
Airbnb House Amenities
Bitset allows to save 20 different values using just 20 bits
More like a graph

Graph representation: Outro

Both are graphs

Twitter Example: Tweet Delivery Problem

Directed graph
Twitter’s example
82000Tb. Photo source
Adjacency matrix vs adjacency list
Excerpt of Airbnb filters
Airbnb filters with types
Looks messy
Number of vertices are more than it may appear
house_type: "entire_place",
adults_number: 2,
price_range_start: 56,
price_range_end: 80,
beds_number: 2,
amenities: ["tv", "wifi", "laptop friendly workspace"],
facilities: ["gym"]

Graph Algorithms: Intro

Detailed tracing of pre-order traversal

Netflix and Amazon: Inverted Index Example

“KISK” or “let’s keep it simple” or “for the sake of simplicity”, a super excuse for tutorial writers to abstract from the real problem and make tons of assumptions by bringing an “abc” easy example and its solution in pseudocode that works even on your grandma’s laptop.

Not the best illustration, I know (and has a typo)
Inverted index
Fetching Movies or Products by keyword in sorted order (by rating)

Traversals: DFS and BFS

Uber and the Shortest Path Problem (Dijkstra’s Algorithm)

Possible variants to reach the user

This is no longer updated. Go to instead

Vardan Grigoryan (vardanator)

Written by

Backend Engineer,

This is no longer updated. Go to instead