Graph Data Structures and Algorithms from Scratch
Getting started with graphs and networks
Topic: Data
Graphs and networks are fundamental data structures for practicing engineers. Graph databases, graphbased neural networks, and knowledge graphs are rapidly gaining in popularity. But to use them effectively, data scientists and engineers need to understand what’s happening “under the hood” of these tools.
Join expert Julian Zucker to explore the fundamentals of graph theory and learn how to implement graph data structures and algorithms in Python. You’ll implement the two most common graph data structures—adjacency matrices and adjacency lists—then implement graph algorithms such as breadthfirst search, depthfirst 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 using libraries such as NetworkX and graph databases such as Neo4j.
What you'll learnand how you can apply it
By the end of this live online course, you’ll understand:
 The fundamentals of graph theory
 The fundamental data structure underlying graph databases, graph neural networks, 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 realworld problems into graph problems
 Use NetworkX proficiently
This training course 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
 A working knowledge of Python (e.g., stacks and queues)
Recommended followup:
 Read Graph Algorithms (book)
 Read Graph Databases, second edition (book)
 Read Practical Graph Analytics with Apache Giraph (book)
About your instructor

Julian Zucker is a machine learning engineer at Klaviyo, where he uses functional programming concepts to productionize ML models. Previously, he developed an open source time series database at Pivotal and created largescale data processing systems for analytics at PayPal. He’s published several papers, including one in AAAI about a novel method of resolving ambiguity in orderings of directed graphs. He’s the lead maintainer of an open source library that implements social choice methods, built on top of the NetworkX graph library.
Schedule
The timeframes are only estimates and may vary according to how the class is progressing
Graph theory (30 minutes)
 Presentation: What’s a graph?—nodes and vertices, edges, edges with weights, directed versus undirected graphs, naming conventions
 Jupyter Notebook exercise: Solve graph theory problems—How many nodes are in some sample graphs?; What’s the shortest path in some sample graphs, 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 (25 minutes)
 Presentation: Adjacency matrices and lists; implementing adjacency matrix and list
 Group discussion: The pros and cons of both approaches
 Jupyter Notebook exercise: Write down the adjacency matrix and list for a given graph; implement an adjacency matrix and list
 Q&A
Break (5 minutes)
Graph properties (55 minutes)
 Presentation: Graph properties and their uses
 Group discussion: When might you need to use these properties?
 Jupyter Notebook exercise: Implement code to compute and visualize several properties of graphs
 Q&A
Break (5 minutes)
Graph algorithms: Part 1 (55 minutes)
 Presentation: Search algorithms—motivating problems (trip planning, finding files), breadthfirst search (BFS), depthfirst search (DFS), modified BFS for weighted graphs
 Discussion: When would you want to choose BFS instead of DFS, or vice versa?
 Q&A
Break (5 minutes)
Graph algorithms: Part 2 (20 minutes)
 Presentation: Pseudocode for generic search algorithm, BFS, and DFS
 Jupyter Notebook exercise: Implement BFS and DFS
 Q&A
Graph extensions and applications (30 minutes)
 Presentation: Hypergraphs; graph databases; graph features for machine learning; call graphs; bipartite graphs; win graphs; and social modeling.
Wrapup and Q&A (10 minutes)