Skip to Content
View all events

Graph Data Structures and Algorithms from Scratch

Published by O'Reilly Media, Inc.

Intermediate content levelIntermediate

Getting started with graphs and networks

This live event utilizes Jupyter Notebook technology

Graphs and networks are fundamental data structures for practicing engineers. Graph databases, graph-based neural networks, and knowledge graphs are rapidly gaining in popularity. Data scientists and engineers need to understand what’s happening “under the hood” of these tools to use them effectively.

Join expert Matthew Singer to gain that under-the-hood knowledge by building graph data structures and algorithms from scratch. Matthew will walk you through the fundamentals of graph theory and implementing graph data structures and algorithms in Python. You’ll get hands-on and implement the two most common graph data structures: adjacency matrices and adjacency lists. Then, you’ll implement graph algorithms such as breadth-first search, depth-first search, and minimum spanning tree. Understanding the fundamental data structures and algorithms behind graphs will enable you to understand what’s going on behind the scenes when you’re using libraries such as NetworkX and graph databases such as Neo4j.

What you’ll learn and how you can apply it

By the end of this live online course, you’ll understand:

  • The fundamentals of graph theory
  • The data structure underlying graph databases, graph NNs, and many other topics in data and computer science
  • The fundamentals of graph algorithms, and how to implement them
  • What problems can be solved with graph algorithms

And you’ll be able to:

  • Implement data structures to represent graphs
  • Implement and use graph algorithms to solve problems
  • Visualize important characteristics of graphs
  • Translate real-world problems into graph problems
  • Use NetworkX proficiently

This live event is for you because...

  • You want to understand how graph algorithms will perform on different graphs.
  • You want to develop an intuition for the properties of different graphs.
  • You want to become proficient with NetworkX so that you can put graph algorithms into practice.

Prerequisites

  • Intermediate Python experience, including stacks and queues

Recommended preparation:

Recommended follow-up:

Schedule

The time frames are only estimates and may vary according to how the class is progressing.

Graph theory (30 minutes)

  • Presentation: What is a graph?; nodes/vertices; edges, and edges with weights; directed versus undirected graphs; naming conventions
  • Hands-on exercises: Graph theory problems—How many nodes are in these sample graphs?; What is the shortest path, both unweighted and weighted?; Which of these graphs are directed and which undirected?; How many cycles are in these graphs?
  • Q&A

Graph data structures (30 minutes)

  • Presentation: Adjacency matrices and lists; how to implement an adjacency matrix and list
  • Hands-on exercise: Write down the adjacency matrix/list for a given graph
  • Group discussion: Pros and cons of both approaches
  • Jupyter notebook: Implement an adjacency matrix and list
  • Q&A
  • Break

Graph properties (60 minutes)

  • Presentation: Graph properties and their uses
  • Group discussion: When might you need to use these properties?
  • Jupyter notebook: Implement code to compute and visualize several properties of graphs
  • Q&A
  • Break

Graph algorithms (50 minutes)

  • Presentation: Search algorithms; motivating problems—trip planning, finding files; breadth-first search (BFS); depth-first search (DFS); modified BFS for weighted graphs; pseudocode for generic search algorithm, BFS, and DFS
  • Group discussion: When would you want to choose BFS instead of DFS, or vice versa?
  • Q&A
  • Break
  • Jupyter notebook: Implement BFS and DFS
  • Q&A

NetworkX (30 minutes)

  • Presentation: NetworkX library purpose; syntax and examples
  • Jupyter notebook: Program with NetworkX
  • Q&A

Advanced graph algorithm (40 minutes)

  • Presentation: Topological sort; dependency graph; Kahn’s algorithm
  • Jupyter notebook: Implement Kahn’s algorithm
  • Group discussion: Recap of class and questions about applications
  • Q&A

Your Instructor

  • Matthew Singer

    Matthew Singer is a computer science teacher at Commonwealth School, where he teaches college-level courses. Previously, he helped run the Fundamentals of Computer Science courses at Northeastern University. Prior to teaching, he accrued years of software development experience in the Boston area, including working at HubSpot as a backend developer. He has a passion for teaching and functional programming, and has been published.

Skill covered

Algorithms