Lesson 20.1 · Graph Fundamentals
What a Graph Is
Nodes (vertices) joined by edges. Edges can be one-way or two-way, weighted or not; the graph can have cycles and many components.
12 min
Think of it like this
A city map: intersections are nodes, streets are edges. A one-way street is a directed edge, a street's length is its weight, and an island town with no bridge is a separate component.
1.The words
Vertex / node: a thing. Edge: a connection between two nodes. Undirected: the edge works both ways (friendship). Directed: one way only (following someone, a prerequisite). Weighted: each edge carries a number (distance, cost, time).
Degree: the number of edges at a node; in directed graphs, split into in-degree (edges coming in) and out-degree (edges going out). Path: a sequence of nodes joined by edges. Cycle: a path that returns to its start. Connected component: a group of nodes that can all reach each other.
A tree is a connected undirected graph with no cycles (n nodes, n − 1 edges). A DAG (directed acyclic graph) is a directed graph with no cycles, the shape of task dependencies.
n = 5, edges = [[0,1],[0,2],[1,3],[2,3],[3,4]]Step 1/4Five nodes and five undirected edges.
Remember
- Directed vs undirected, weighted vs unweighted.
- Degree, in-degree, out-degree.
- Trees and DAGs are graphs with restrictions.
Common mistakes
- Assuming a graph is connected.
- Assuming no cycles unless the problem says so.
Words used in this lesson
- Vertex
- Another word for node.
- Component
- A maximal group of nodes that are all reachable from each other.
- DAG
- Directed acyclic graph: one-way edges and no cycles.
- Sparse / dense
- Few edges (E close to V) vs many edges (E close to V²).