Stage 4 · Lesson 10 of 10

Graphs at a first look

A is a set of nodes joined by edges (links), with no single root. Examples are cities and roads, people and friendships, or web pages and links. Edges can be one-way (directed) or two-way, and they can carry a weight, such as a distance.

Most code stores a graph as an adjacency list: a map from each node to its neighbours. There are two basic ways to walk a graph. Breadth-first search uses a and explores the nearest nodes first.

Depth-first search uses or a and goes as deep as it can first. The classic bug is forgetting to mark visited nodes, which forever when the graph has a cycle. The DSA roadmap goes much deeper; here, learn to recognise a graph and walk one.

A question to check yourself, an AI practice session and 2 cheat sheet entries come when you add the roadmap to your account. Add it

Resources for this stage

Start with· follow one of these

CoursePaid
Grokking Data Structures & Algorithms for Coding Interviews
Design Gurus · Beginner · Subscription
Each structure built from first principles, with solutions in Python, Java, C++, JavaScript and C#
CourseFree
CS50: Introduction to Computer Science
Harvard University · Beginner
Free: weeks 3 and 5 cover searching, sorting, linked lists, hash tables and trees

Practise

Design Gurus Problem Set
Free problems organised by data structure; stick to the easy ones in this stage

Keep handy

VisuAlgo
Step through linked lists, hash tables and sorts with your own input
Learn C#
The collections articles: List, Dictionary, HashSet, Queue and Stack

Also worth your time

Demystifying Big-O Notation: The Ultimate Guide to Understanding Algorithm Complexity (opens in a new tab)Read
Time and space complexity worked through five common algorithms