Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Directed, weighted, and how we store them
step 1 / 14
directed, weighted graph
52173
0
1
2
3
adjacency list
  • 0:[1, 2]
  • 1:[3]
  • 2:[1, 3]
  • 3:[]
Graph vocabulary + a BFS recap
▸
1// a graph = nodes + edges
2edges may be directed and/or weighted
3in-degree(v)  = edges arriving at v
4out-degree(v) = edges leaving v
5a DAG = directed graph with no cycle
6store as adjacency list: adj[u] = [neighbours]
7// traverse (BFS):
8seen = {source}; queue = [source]
9while queue: u = dequeue
10    for v in adj[u]: if v unseen: enqueue v
11done — every reachable node visited
state
  • nodes (V)4
  • edges (E)5

line 1A graph is a set of NODES (also called vertices) joined by EDGES. Unlike a tree there is no root and edges may form cycles. Almost every graph problem is one of three flavours: REACHABILITY (can I get from A to B?), ORDERING (what sequence respects the dependencies?), or SHORTEST PATH (what is the cheapest route?). Learn the vocabulary first.