Home>
Courses>

Mastering Graph Algorithms

Mastering Graph Algorithms

Beginner

91 Lessons

15h

Certificate of Completion

AI-POWERED

Explanations

AI-POWERED

Explanations

This course includes

32 Playgrounds
50 Quizzes

This course includes

32 Playgrounds
50 Quizzes
Course Overview
What You'll Learn
Course Content

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...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

What You'll Learn

An understanding of classical graph algorithms

Show more

Course Content

1.

Introduction

What Is This Course About?
2.

Review: Asymptotic Notation and Math Prerequisites

Getting Started with Logarithms
Food 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 Graphs
Exercise: 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

Trusted by 1.4 million developers working at companies

Anthony Walker

@_webarchitect_

Evan Dunbar

ML Engineer

Carlos Matias La Borde

Software Developer

Souvik Kundu

Front-end Developer

Vinay Krishnaiah

Software Developer

Eric Downs

Musician/Entrepeneur

Kenan Eyvazov

DevOps Engineer

Souvik Kundu

Front-end Developer

Eric Downs

Musician/Entrepeneur

Anthony Walker

@_webarchitect_

Evan Dunbar

ML Engineer

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-Powered Mock Interviews

Adaptive Learning

Explain with AI

AI Code Mentor

FOR TEAMS

Interested in this course for your business or team?

Unlock this course (and 1,000+ more) for your entire org with DevPath