Working with Graph Algorithms in Python

This course focuses on how to represent a graph using three common classes of graph algorithms - the topological sort to sort vertices by precedence relationships, the shortest path algorithm, and finally the spanning tree algorithms.
Course info
Level
Beginner
Updated
Jul 19, 2017
Duration
2h 14m
Table of contents
Introducing the Graph Data Structure
Understanding Topological Sort
Working with Shortest Path Algorithms
Working with Spanning Tree Algorithms
Course Overview
Description
Course info
Level
Beginner
Updated
Jul 19, 2017
Duration
2h 14m
Description

A graph is the underlying data structure behind social networks, maps, routing networks and logistics, and a whole range of applications that you commonly use today. In this course, Working with Graph Algorithms in Python, you'll learn different kinds of graphs, their use cases, and how they're represented in code. First, you'll dive into understanding the pros and cons of adjacency matrices, adjacency lists, adjacency sets, and know when you would choose one data structure over another. Next, you'll explore common graph algorithms, such as the topological sort, used to model dependencies in tasks, build components, and manage projects. Additionally, you'll cover how to find the shortest path in a graph, the core algorithm for mapping technologies. Lastly, you'll be introduced to spanning tree algorithms, which are used to find a path and covers all nodes with minimum cost, the fundamental algorithm behind figuring flight paths, and bus routes. By the end of this course, you'll have a better understanding of these principles and the necessary skills to implement them into simple, easy to follow Python code.

About the author
About the author

A problem solver at heart, Janani has a Masters degree from Stanford and worked for 7+ years at Google. She was one of the original engineers on Google Docs and holds 4 patents for its real-time collaborative editing framework.

More from the author
Building Features from Image Data
Advanced
2h 10m
Aug 13, 2019
Designing a Machine Learning Model
Intermediate
3h 25m
Aug 13, 2019
More courses by Janani Ravi
Section Introduction Transcripts
Section Introduction Transcripts

Course Overview
Hi. My name is Janani Ravi, and welcome to this course on Graph Algorithms in Python. I'll introduce myself. I have a master in electrical engineering from Stanford and have worked at companies such as Microsoft, Google, and Flipkart. At Google, I was one of the first engineers working on real time collaborative editing in Google Docs and I hold four patents for its underlying technologies. I currently work on my own startup, Loony Corn, a studio for high-quality video content. A huge number of problems in the real world can be modeled as graphs, social networks. This was allocation for project management, modeling relationships, and mapping algorithms as some of the common applications of graph. This course focuses on how to represent a graph using different kind of data structures and the tradeoffs that are involved. The course then covers three common kinds of graph algorithms. We'll start off with a topological sort used to model dependencies in tasks with components and manage projects. We'll then move onto finding the shortest path in a graph between source and destination nodes, the core algorithm for mapping technologies, learn the shortest path algorithm, and Dijkstra's algorithm to solve this for unweighted as for less weighted graphs. Lastly, we'll introduce spanning tree algorithms used to find a path, which covers all nodes with minimum cost, the fundamental algorithm behind figuring flight paths and bus routes, work with both Prim's and Kruskal's algorithm for the minimum spanning tree, understand all of these from first principles, and implement all of them in simple, easy-to-follow Python code.