HomeCoursesMastering Graph Algorithms

Beginner

15h

Updated 3 months ago

Mastering Graph Algorithms
Save

Gain insights into key graph algorithms, including depth-first search, shortest paths, and flow networks. Explore their applications and foundational role in advanced computing disciplines.

Join 2.7 million developers at

Overview

Content

Reviews

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 spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings. The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engin...Show More

WHAT YOU'LL LEARN

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

An understanding of classical graph algorithms

Content

91 Lessons50 Quizzes

Introduction

1 Lessons

Get familiar with the fundamentals and applications of graph algorithms across disciplines.

What Is This Course About?

Review: Asymptotic Notation and Math Prerequisites

11 Lessons

Grasp the fundamentals of logarithms, running time, and big-O notation for algorithm analysis.

Getting Started with Logarithms

Food for Thought: Running Time

Running Time as a Function of Input Size

Comparing Running times

Big-O Notation

Ruminating on Constants in Big-O Notation

Some Useful Facts

A Big-O Drill

Leveraging the Proof by Contradiction Technique

Exercise: Order of Growth

Quiz: Big-O Notation

Working with Graphs

9 Lessons

Work your way through understanding and representing graphs, including adjacency matrices, lists, and special graph types.

Subgraphs, Paths, Cycles and Components

Trees

Bipartite Graphs

Quiz: Working with Graphs

Depth-First Search and Applications

16 Lessons

Grasp the fundamentals of Depth-First Search and its applications in graph traversal and analysis.

Depth-First Search

Edge Classification in Directed Graphs

Exercise: Classify Edges of a Directed Graph

Edge Classification in Undirected Graphs

Exercise: Classify Edges of an Undirected Graph

Identifying Cut-Vertices

Exercise: Identify Cut-Vertices

Topological Sorting

Exercise: Sort the Vertices in Topological Order

Thought Exercise: Detecting Cycles in Directed Graphs

Characterizing Strongly Connected Components

Tarjan’s Algorithm

Exercise: Practice Tarjan’s Algorithm

The Kosaraju-Sharir Algorithm

Exercise: Practice the Kosaraju-Sharir Algorithm

Quiz: DFS and Applications

Prelude: Shortest Paths

7 Lessons

Explore shortest-path strategies, BFS for unweighted digraphs, and apply graph traversal concepts.

The Shortest-Paths Problem

Reflections on Shortest Paths

Quiz: Shortest Paths Terminology

Breadth-First Search

Shortest Paths in Unweighted Digraphs

Exercise: Print Shortest Path

Quiz: BFS and Shortest Paths

Single-source Shortest Paths in Weighted Digraphs

12 Lessons

Focus on solving the single-source shortest paths problem using various algorithms in weighted digraphs.

Single-Source Shortest-Paths Problem

Exercise: Path-Relaxation

An Immediate Algorithm for DAGs

Thought Exercise: Longest Paths in DAG

Exercise: Shortest Paths in a DAG

Dijkstra’s Algorithm

Exercise: Dijkstra’s Algorithm

Thought Exercise: Negative Weights

The Bellman-Ford Algorithm

Exercise: The Bellman-Ford Algorithm

Thought Exercise: The Bellman-Ford Algorithm

Quiz: Single-Source Shortest-Paths

All Pairs Shortest Paths

5 Lessons

Practice using Johnson's and Floyd-Warshall algorithms for efficient all-pairs shortest paths.

Johnson’s Algorithm

Exercise: Johnson’s Algorithm

The Floyd-Warshall Algorithm

Exercise: Floyd-Warshall Algorithm

Quiz: All-Pairs Shortest Paths

Minimum Spanning Tree

12 Lessons

Learn how to use Minimum Spanning Trees via Prim's and Kruskal's algorithms effectively.

What’s an MST?

Quiz: Minimum Spanning Trees

Thought Exercise: Uniqueness

Prim’s Algorithm

Exercise: Select Edges as Specified by Prim’s Algorithm

Exercise: Prim’s Algorithm

Kruskal’s Algorithm

Implementation of Disjoint-Set Data Structure

Exercise: Select Edges as Specified by Kruskal’s Algorithm

Exercise: Kruskal’s Algorithm

Thought Exercise: MSTs and Shortest Paths

Quiz: Minimum Spanning Trees

Flows

6 Lessons

Walk through network flows, the Ford-Fulkerson algorithm, and practical exercises.

Network Flows

The Essence of the Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm: The Fine Print

Thought Exercise: Rational Capacities

Exercise: The Ford-Fulkerson Algorithm

Quiz: Network Flows

10.

Matchings and Vertex Covers

11 Lessons

Examine matchings, vertex covers, the Ford-Fulkerson algorithm, and the Gale-Shapley algorithm.

Matchings

Maximum Matchings in Bipartite Graphs

Exercise: Maximum Matchings in Bipartite Graphs

The Dual Problem of Minimum Vertex Cover

Minimum Vertex Cover in Bipartite Graphs

Exercise: Minimum Vertex Cover in Bipartite Graphs

The Gale-Shapley Algorithm

Proof that the Gale-Shapley Algorithm Favors the Proposers

Thought Exercise: Asymmetry in the Gale-Shapley Algorithm

Exercise: Find Stable Matching

Quiz: Matchings and Vertex Covers

11.

Conclusion

1 Lessons

Grasp the fundamentals of graph algorithms' applications, utility, and practical significance in various fields.

Final Remarks

Use Simulated Annealing for the Traveling Salesman Problem

Project

Certificate of Completion

Showcase your accomplishment by sharing your certificate of completion.

Developed by MAANG Engineers

Every Educative resource is designed by our in-house team of ex-MAANG software engineers and PhD computer science educators — subject matter experts who’ve shipped production code at scale and taught the theory behind it. The goal is to get you hands-on with the skills you need to stay ahead in today's constantly evolving tech landscape. No videos, no fluff — just interactive, project-based learning with personalized feedback that adapts to your goals and experience.

Trusted by 2.7 million developers working at companies

"These are high-quality courses. Trust me. I own around 10 and the price is worth it for the content quality. EducativeInc came at the right time in my career. I'm understanding topics better than with any book or online video tutorial I've done. Truly made for developers. Thanks"

Anthony Walker

@_webarchitect_

"Just finished my first full #ML course: Machine learning for Software Engineers from Educative, Inc. ... Highly recommend!"

Evan Dunbar

ML Engineer

"You guys are the gold standard of crash-courses... Narrow enough that it doesn't need years of study or a full blown book to get the gist, but broad enough that an afternoon of Googling doesn't cut it."

Carlos Matias La Borde

Software Developer

"I spend my days and nights on Educative. It is indispensable. It is such a unique and reader-friendly site"

Souvik Kundu

Front-end Developer

"Your courses are simply awesome, the depth they go into and the breadth of coverage is so good that I don't have to refer to 10 different websites looking for interview topics and content."

Vinay Krishnaiah

Software Developer

"I've tried probably 5-7 different sites and Educative is easily the best. It perfectly blends explanation with interactivity"

Eric Downs

Musician/Entrepeneur

Hands-on Learning Powered by AI

See how Educative uses AI to make your learning more immersive than ever before.

Instant Code Feedback

Evaluate and debug your code with the click of a button. Get real-time feedback on test cases, including time and space complexity of your solutions.

AI Mock Interviews

Test your skills in a simulated interview setting. Receive personalized feedback based on your performance. Available for Coding Interviews, System Design, and more.

Adaptive Learning

At various checkpoints throughout Educative courses, you will be prompted to take a quick assessment. Receive a condensed curriculum tailored to your strengths and skill gaps.

Explain with AI

Select any text within any Educative course, and get an instant explanation — without ever leaving your browser.

AI Code Mentor

AI Code Mentor helps you quickly identify errors in your code, learn from your mistakes, and nudge you in the right direction — just like a 1:1 tutor!

Course

Grokking Dynamic Programming Interview in C++

The ultimate guide to dynamic programming interviews in C++ with strategies developed by FAANG engineers. Practice with real-world questions and get interview-ready in just a few hours.

25 h

intermediate

Course

Decode the Coding Interview in C++: Real-World Examples

The ultimate guide to coding interviews in C++. Developed by FAANG engineers, practice with real-world examples and get interview-ready in just a few hours. Battle-tested and proven.

18 h

beginner

Course

Genetic Algorithms in Elixir

Gain insights into building genetic algorithm frameworks in Elixir. Learn about statistics, genealogy tracking, and solving practical problems with customizable genetic algorithm frameworks.

25 h 30 m

beginner

Course

Web Application Security for the Everyday Software Engineer

Gain insights into enforcing web app security best practices, such as HTTPS, defending against XSS and clickjacking, managing HTTP cookies, and warding off DDoS attacks.

4 h

intermediate

Course

Data Structures for Coding Interviews in JavaScript

The ultimate guide to data structures for coding interviews in JavaScript. Developed by FAANG engineers to help you write better code and ace industry benchmarks.

35 h

beginner

Course

Data Structures for Coding Interviews in C++

The ultimate guide to data structures for coding interviews. Developed by FAANG engineers. Get interview-ready in hours with C++ implementations and real-world interview questions. Prep faster.

25 h

beginner

Course

Data Structures for Coding Interviews in Python

Explore proven strategies developed by FAANG engineers to ace coding interviews with a structured approach to data structures in Python. Prep faster with real-world questions.

30 h

beginner

Course

Grokking Dynamic Programming Interview in C++

intermediate

25 hour

Course

Decode the Coding Interview in C++: Real-World Examples

beginner

18 hour

Course

Genetic Algorithms in Elixir