INTERACTIVE COURSE

Beginner

91 Lessons

15h

Certificate of Completion

AI Explanations

AI Explanations

32 Playgrounds

50 Quizzes

288 Illustrations

Takeaway Skills

An understanding of classical graph algorithms

The ability to think and visualize in terms of graph structures

An inside-out understanding of what makes each algorithm work the way it does

Cultivation of a broader perspective that informs other computing disciplines

Course Overview

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum...

Course Content

1

Introduction

2

Review: Asymptotic Notation and Math Prerequisites

Getting Started with LogarithmsFood for Thought: Running TimeRunning Time as a Function of Input SizeComparing Running timesBig-O NotationRuminating on Constants in Big-O NotationSome Useful FactsA Big-O DrillLeveraging the Proof by Contradiction TechniqueExercise: Order of GrowthQuiz: Big-O Notation

3

Working with Graphs

GraphsAdjacency MatrixAdjacency ListDirected GraphsWeighted GraphsSubgraphs, Paths, Cycles and ComponentsTreesBipartite GraphsQuiz: Working with Graphs

4

Depth-First Search and Applications

Depth-First SearchEdge Classification in Directed GraphsExercise: Classify Edges of a Directed GraphEdge Classification in Undirected GraphsExercise: Classify Edges of an Undirected GraphIdentifying Cut-VerticesExercise: Identify Cut-VerticesTopological SortingExercise: Sort the Vertices in Topological OrderThought Exercise: Detecting Cycles in Directed GraphsCharacterizing Strongly Connected ComponentsTarjan’s AlgorithmExercise: Practice Tarjan’s AlgorithmThe Kosaraju-Sharir AlgorithmExercise: Practice the Kosaraju-Sharir AlgorithmQuiz: DFS and Applications

5

Prelude: Shortest Paths

The Shortest-Paths ProblemReflections on Shortest PathsQuiz: Shortest Paths TerminologyBreadth-First SearchShortest Paths in Unweighted DigraphsExercise: Print Shortest PathQuiz: BFS and Shortest Paths

6

Single-source Shortest Paths in Weighted Digraphs

12 Lessons

7

All Pairs Shortest Paths

5 Lessons

8

Minimum Spanning Tree

12 Lessons

9

Flows

6 Lessons

10

Matchings and Vertex Covers

11 Lessons

11

Conclusion

1 Lesson

COURSE AUTHOR

How You'll Learn

You don’t get better at swimming by watching others. Coding is no different. Practice as you learn with live code environments inside your browser.

Videos are holding you back. Educative‘s interactive, text-based lessons accelerate learning — no setup, downloads, or alt-tabbing required.

Learn faster and smarter with adaptive AI tools embedded in every Educative course.

Built-in assessments let you test your skills. Completion certificates let you show them off.

Recommended Courses

BEFORE STARTING THIS COURSE

AFTER FINISHING THIS COURSE