Mastering Graph Algorithms

Mastering Graph Algorithms

Beginner

91 Lessons

15h

Certificate of Completion

AI-POWERED

Explanations

Explanations

This course includes

32 Playgrounds

50 Quizzes

288 Illustrations

This course includes

32 Playgrounds

50 Quizzes

288 Illustrations

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

Course Content

1

Introduction

What Is This Course About?

2

Review: Asymptotic Notation and Math Prerequisites

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

3

Working with Graphs

Graphs Adjacency Matrix Adjacency List Directed Graphs Weighted Graphs Subgraphs, Paths, Cycles and Components Trees Bipartite Graphs Quiz: Working with Graphs

4

Depth-First Search and Applications

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

5

Prelude: Shortest Paths

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

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

FOR TEAMS

Interested in this course for your business or team?

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