This course will teach you the most important graph algorithms, covering both theory and implementations in C++.

Intermediate

42 Lessons

5h

Certificate of Completion

This course will teach you the most important graph algorithms, covering both theory and implementations in C++.

AI-POWERED

AI-POWERED

Explanations

This course includes

18 Playgrounds

5 Challenges

11 Quizzes

This course includes

18 Playgrounds

5 Challenges

11 Quizzes

Course Overview

Graph algorithms are the core of many real-world applications of computer science, such as automotive navigation or routing in computer networks. They’re also a common subject in coding interviews at top-tier tech companies. In this course, we’ll learn about the basic concepts of graph theory and how to represent graphs as data structures in code. We’ll study essential graph algorithms such as depth-first search or Dijkstra's algorithm to traverse graphs and find shortest paths. Finally, we’ll learn to s...

What You'll Learn

Learn how graphs can be represented as data structures

Traverse graphs using search algorithms

Find the shortest paths in graphs

Find maximum matchings

Solve flow problems

Compute minimum spanning trees

What You'll Learn

Learn how graphs can be represented as data structures

Show more

Course Content

1.

Introduction

Introduction to Graph AlgorithmsDirected and Undirected GraphsGraph Terminology IGraph Terminology IIWeighted GraphsExcursion: Algorithm AnalysisQuiz: Introduction to Graph Algorithms

2.

Graph Representations

Adjacency MatrixAdjacency ListRepresenting Weighted GraphsComparison of Graph RepresentationsQuiz: Graph RepresentationsChallenge: Converting Graph Representations

3.

Graph Traversal

Depth-first Search (DFS)Implementation of DFSBreadth First Search (BFS)Implementation of BFSApplication 1: Topological SortApplication 2: Strongly Connected ComponentsImplementation of Kosaraju's AlgorithmQuiz: Graph TraversalChallenge: Bipartite Graph Check

4.

Shortest Paths

Shortest Path ProblemsDijkstra's Algorithm for the SSSPImplementation of DijkstraFloyd-Warshall Algorithm for the ASSPImplementation of Floyd-WarshallQuiz: Shortest PathsChallenge: Bellmann-Ford

5.

Spanning Trees

The Minimum Spanning Tree ProblemKruskal's AlgorithmImplementation of Kruskal's AlgorithmQuiz: Spanning TreesChallenge: Maximum Spanning Trees

6.

Flow Problems

6 Lessons

7.

Conclusion

1 Lesson

8.

Appendix

1 Lesson

Course Author

Trusted by 1.4 million developers working at companies

Anthony Walker

@_webarchitect_

Emma Bostian 🐞

@EmmaBostian

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_

Emma Bostian 🐞

@EmmaBostian

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