Introduction to Graph
EasyVertices, edges, and the choices that matter
Problem
Learn graph terminology: vertices, edges, directed vs undirected, weighted, degree, paths and cycles.
Dots (nodes) joined by lines (edges) - the map behind networks and mazes.
The idea
A graph is a set of vertices joined by edges. Four properties decide everything downstream: directed or undirected, weighted or unweighted, cyclic or acyclic, connected or not — those, rather than the wording of the problem, tell you which algorithm applies.
The trick
- Degree is the number of incident edges; directed graphs split it into in and out.
- A tree is a connected acyclic graph with exactly V-1 edges.
- Always ask whether the graph may be disconnected; it changes the outer loop.
Step 1 of 5. A graph is dots (nodes) joined by lines (edges). Think of people and their friendships.
1/5
Optimal
timeO(V+E)spaceO(V+E)
Neighbors per node.
1const adj = Array.from({length: V}, () => []);2for (const [u, v] of edges) {3 adj[u].push(v);4 adj[v].push(u); // omit for directed5}Input
- nodes
- 5, 5 edges
Memory
- visiting
- —
Output
- reached
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- edges [[0,1],[1,2]]
- Output:
- path exists 0->2
Finished the walkthrough? Add it to your streak.