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
Rating
(30)
Level
Beginner
Updated
Jul 19, 2017
Duration
2h 14m
Table of contents
Course Overview
Introducing the Graph Data Structure
Understanding Topological Sort
Working with Shortest Path Algorithms
Working with Spanning Tree Algorithms
Description
Course info
Rating
(30)
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
Using PyTorch in the Cloud: PyTorch Playbook
Intermediate
2h 21m
Apr 25, 2019
Building Clustering Models with scikit-learn
Intermediate
2h 33m
Apr 24, 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.

Working with Shortest Path Algorithms
If you have a graph modeling a real world relationship, a very common use case is finding the shortest path between two nodes on a graph. How many degrees away is a particular connection on LinkedIn. Who can I ask to get introduced to her? How can I get from one city to another quickly? What's a shortcut that I can use? All of these boil down to shortest path algorithms, which is what we'll study in this module. We had mentioned earlier that we'll be looking at three broad categories of graph problems in this course. One type establishes precedence relationship between nodes, another type helps us to get from point A to point B, and the third allows us to cover all nodes in a graph. We've already covered topological sort, which establishes precedence. We'll speak about shortest path algorithms in this module, and we'll cover minimum spanning tree algorithms in the next module. We've spoken briefly of how neural networks rely on topological sort for their computation. In this module, we'll talk about the shortest path, which enables the fastest and most efficient deliveries from warehouses to customers. We'll talk about planning railway lines in the next module. We'll start off with a discussion of shortest path algorithms, which are widely used in transportation and scheduling. The objective of these algorithms is to find the most efficient or the cheapest route between a pair of nodes. The lengths of the different edges, or the cost of travel between two edges, can be represented by something called an edge weight. This is used to calculate something called the cost of a path. We'll be studying two different kinds of algorithms. If all edge weights are equal, we'll use the unweighted shortest path algorithm. If edge weights are unequal, we'll use Dijkstra's algorithm.

Working with Spanning Tree Algorithms
In this module, we'll work with spanning tree algorithms, which ensure that all nodes in a graph are connected by exactly one edge. In this class, we've studied three common types of graph problems. One, way you establish precedence between nodes, two, way you get from point A to point B, and finally, three, where we want to cover all nodes in a graph. In previous modules, we've seen both the logic and implementation of topological sort as the less shortest path algorithms. In this module, we cover the minimum spanning tree which connects all nodes in a graph. Each node is connected by exactly one edge. We've seen that topological sort and the shortest path algorithms have wide uses in the real world, as does the minimum spanning tree algorithms that we'll study now. Let's say you want to find the cheapest way to interconnect a bunch of cities with transportation links, minimum spanning tree is what you'd use. In this module, we'll talk about spanning tree algorithms. We'll seek to find the shortest and the minimal cost way to cover all nodes in a graph. In these algorithms, there is no directionality to how we are moving from node to node. It does not matter what the start and end nodes are. There are two specific algorithms that we'll cover. Prim's algorithm works well for connected, undirected graphs, and Kruskal's algorithm works even for disconnected graphs, graphs where there may not be a path from one node to all other nodes.