Graphs — Simple English

77 lessons · Data Structures & Algorithms · Simple English · Beginner Friendly

01 Why We Need Graphs: The Travel Booking ProblemFree Why We Need Graphs: The Travel Booking Problem Before we learn what a graph is, let's understand why graphs even exist. … 02 Graphs: Modeling Many-to-Many Relationships with Cities and FlightsFree Why We Need Graphs Some information is naturally tangled together. Think about flights between cities: one city can have… 03 Graph Terminologies: Vertex, Edge, Degree, and PathFree Graph Terminologies A graph is an advanced kind of data structure. Unlike an array or a linked list, where items sit one… 04 Types of Graphs: Directed, Weighted, Cyclic, DAG, and Bipartite🔒 Types of Graphs A graph is a way to show how things are connected. It is made of two simple parts: - Vertices (also call… 05 Storing a Graph as an Adjacency Matrix🔒 What an adjacency matrix is A graph is a way of showing how things are connected. Each thing is a node (a dot), and each… 06 Building a Graph with an Adjacency Matrix🔒 Building a Graph with an Adjacency Matrix A graph is just a set of things, plus the connections between them. The "thing… 07 Storing Edge Weights and Node Data in an Adjacency Matrix🔒 Storing Edge Weights and Node Data in an Adjacency Matrix A graph is a set of points (called nodes) joined by lines (cal… 08 Graphs with an Adjacency List🔒 Storing a Graph as an Adjacency List A graph is just a set of points (called nodes) joined by connections (called edges)… 09 How to Build a Graph Using an Adjacency List🔒 How to Build a Graph Using an Adjacency List A graph is just a set of points connected by lines. We call the points node… 10 Enhanced Adjacency Lists: Storing Edge Weights and Node Data🔒 Enhanced Adjacency Lists: Storing Edge Weights and Node Data A graph is a way of showing connections — think of cities j… 11 Cloning an Adjacency List of a Directed Graph🔒 Cloning an Adjacency List Before we solve anything, let's make sure we understand the building blocks. What is a graph? … 12 Converting an Adjacency List into an Adjacency Matrix🔒 Two Ways to Store a Graph A graph is just a set of points connected by lines. We call the points nodes (or vertices) and… 13 Converting an Adjacency Matrix to an Adjacency List🔒 Converting an Adjacency Matrix to an Adjacency List A graph is just a set of points (called nodes or vertices) connected… 14 Depth-First Traversal of a Graph🔒 Depth-First Traversal of a Graph When you have a simple list or an array, visiting every item is easy: you just run a lo… 15 Depth First Traversal of a Graph🔒 Depth First Traversal of a Graph A graph is just a collection of points (called nodes) connected by lines (called edges)… 16 Breadth-First Traversal of a Graph🔒 Breadth-First Traversal of a Graph Imagine you drop a stone in a pond. The water moves out in rings — first a small circ… 17 Breadth-First Traversal of a Graph🔒 Breadth-First Traversal of a Graph When you have a graph — a set of points (called nodes) joined by connections (called … 18 Treating a Grid as a Graph (and How to Move Around It)🔒 Treating a Grid as a Graph What is a grid? A grid is just a table of values arranged in rows and columns. Think of it li… 19 Depth-First Search on a Grid🔒 Depth-First Search on a Grid A grid is just a table of cells arranged in rows and columns — think of a chessboard or a s… 20 Depth-First Traversal on a Grid🔒 Depth-First Traversal on a Grid Imagine a piece of graph paper made of little squares arranged in rows and columns. This… 21 Breadth-First Traversal on a Grid🔒 Breadth-First Traversal on a Grid A grid is just a table of cells arranged in rows and columns — like a spreadsheet or a… 22 Breadth-First Traversal on a Grid🔒 Breadth-First Traversal on a Grid Imagine a piece of graph paper, like a checkerboard. Each little square is called a ce… 23 Detecting a Cycle in an Undirected Graph🔒 Detecting a Cycle in an Undirected Graph A graph is just a bunch of points (called nodes) joined by connections (called … 24 Detecting a Cycle in an Undirected Graph🔒 Detecting a Cycle in an Undirected Graph Imagine a set of cities connected by two-way roads. Each city is a node (a poin… 25 Detecting a Cycle in a Directed Graph🔒 Detecting a Cycle in a Directed Graph What is a directed graph? A graph is a set of points (called nodes) joined by line… 26 Detecting a Cycle in a Directed Graph🔒 Detecting a Cycle in a Directed Graph Imagine a set of one-way streets connecting different places in a town. You start … 27 Topological Sort: Putting Things in the Right Order🔒 Topological Sort: Putting Things in the Right Order Imagine you are getting dressed in the morning. You must put on your… 28 Topological Sort Using Depth-First Search🔒 Topological Sort Using Depth-First Search Imagine you have a list of tasks where some tasks must be done before others. … 29 Topological Sort: Putting Tasks in the Right Order🔒 Topological Sort: Putting Tasks in the Right Order Imagine you are getting ready in the morning. You must put on your so… 30 Topological Sort: Putting Tasks in the Right Order🔒 Topological Sort: Putting Tasks in the Right Order Imagine you are getting ready in the morning. You must put on your so… 31 The Single Source Shortest Path Problem🔒 Finding the Shortest Path to Everywhere Imagine you are standing at one spot, and you want to know the shortest way to r… 32 Dijkstra's Algorithm: Finding Shortest Paths in Weighted Graphs🔒 Dijkstra's Algorithm: Finding the Shortest Path Imagine you are standing at one city on a map, and roads connect it to m… 33 Implementing Dijkstra's Algorithm with a Priority Queue🔒 Implementing Dijkstra's Algorithm with a Priority Queue Dijkstra's algorithm finds the shortest distance from one starti… 34 Dijkstra's Algorithm: Finding the Shortest Path from One Node to All Others🔒 Dijkstra's Algorithm: Shortest Path in a Weighted Graph Imagine you are looking at a map of cities. Roads connect the ci… 35 Understanding Negative-Weight Edges (and Why Dijkstra Breaks)🔒 Understanding Negative-Weight Edges Until now, every shortest-path example used edge weights that were positive. An edge… 36 The Bellman-Ford Algorithm: Shortest Paths with Negative Edges🔒 The Bellman-Ford Algorithm Imagine you are standing at one city on a map and you want to know the cheapest way to reach … 37 The Bellman-Ford Algorithm: Shortest Paths with Negative Weights🔒 The Bellman-Ford Algorithm: Shortest Paths with Negative Weights Imagine you have a map of cities. Roads connect some ci… 38 The All-Pair Shortest Path Problem🔒 The All-Pair Shortest Path Problem Imagine you have a map full of cities, and roads connect them with different travel c… 39 Floyd-Warshall: Shortest Paths Between Every Pair of Nodes🔒 Floyd-Warshall: Shortest Paths Between Every Pair of Nodes Imagine you have a map of cities connected by roads, and each… 40 Floyd-Warshall: Finding the Shortest Path Between Every Pair of Nodes🔒 Floyd-Warshall: Shortest Paths Between All Pairs Imagine you have a map of cities connected by one-way roads. Each road … 41 The Maximum Flow Problem🔒 The Maximum Flow Problem Imagine a network of water pipes. Water enters at one point, travels through pipes of different… 42 The Max-Flow Min-Cut Theorem🔒 The Max-Flow Min-Cut Theorem Imagine a network of water pipes. Water starts at one place called the source and must reac… 43 The Ford-Fulkerson Method: Finding Maximum Flow in a Network🔒 The Ford-Fulkerson Method: Finding Maximum Flow Imagine a network of water pipes. Water starts at one tank, called the s… 44 Why Ford-Fulkerson Uses Reverse Edges🔒 Why Ford-Fulkerson Uses Reverse Edges Imagine you want to push as much water as possible from a starting tap (the source… 45 Maximum Flow in a Graph🔒 Maximum Flow in a Graph Imagine a network of water pipes. Water enters at one point and leaves at another. Each pipe can… 46 Maximum Bipartite Matching: Pairing Two Groups the Best Way🔒 Maximum Bipartite Matching What is a bipartite graph? A graph is just a set of points (we call them nodes) joined by lin… 47 Solving Maximum Bipartite Matching with Maximum Flow🔒 Solving Maximum Bipartite Matching with Maximum Flow What problem are we solving? Imagine you have two groups of things … 48 Maximum Bipartite Matching🔒 Maximum Bipartite Matching Imagine you have two separate groups of people. On the left side you have job applicants, and… 49 Maximum Bipartite Matching: Pairing Applicants with Jobs🔒 Matching Applicants to Jobs Imagine you are running a small hiring office. You have a group of people looking for work (… 50 Understanding the Depth-First Search (DFS) Pattern🔒 Understanding the Depth-First Search (DFS) Pattern What is depth-first search? Imagine you are walking through a maze. A… 51 The Depth-First Search (DFS) Pattern: Finding All Paths in a Graph🔒 The Depth-First Search (DFS) Pattern: Finding All Paths A graph is just a set of points (called nodes) joined by connect… 52 Finding All Paths from the Start to the End of a Graph🔒 Source to Target Paths Imagine a city map where roads only go one way. You start at one place and want to know every pos… 53 Finding All Paths in a Graph That Add Up to a Target Weight🔒 Target Paths: Finding Routes That Add Up to a Target Imagine a map of cities connected by one-way roads. Each road has a… 54 Finding All Hamiltonian Paths in a Directed Graph🔒 Finding All Hamiltonian Paths Imagine a city with several places to visit, and one-way roads connecting them. You start … 55 Counting Simple Cycles Through a Source and Destination🔒 Counting Simple Cycles in a Directed Graph What is a graph? A graph is just a set of points connected by lines. The poin… 56 Connected Components in a Graph (and How to Process Them with DFS)🔒 Connected Components in a Graph What is a connected component? Imagine a map of small towns with roads between some of t… 57 Finding Connected Components in a Graph (with Depth-First Search)🔒 Finding Connected Components in a Graph Imagine a map of cities joined by roads. If you can drive from one city to anoth… 58 Finding Connected Components in a Graph🔒 Finding Connected Components in a Graph A graph is just a way to show how things are linked together. Think of a group o… 59 Sum of Minimums in Connected Components of a Graph🔒 Sum of Minimums in a Graph Let's learn a classic graph problem step by step. By the end, you will understand what the qu… 60 Counting Islands in a Grid🔒 Counting Islands in a Grid Imagine you are looking down at a map made of little square boxes. Some boxes are land and so… 61 Size of the Largest Island in a Grid🔒 Size of the Largest Island Imagine a map drawn on graph paper. Every little square is either land or water. Your job is … 62 Two-Colouring a Graph: Can You Colour It With Just Two Colours?🔒 Two-Colouring a Graph Imagine you have a map of cities connected by roads. You want to paint each city using only two co… 63 Spotting and Solving the Two-Colouring (Bipartite) Pattern🔒 Spotting and Solving the Two-Colouring (Bipartite) Pattern Many graph problems look completely different on the surface,… 64 Two-Colourable Graphs: Can You Colour It With Just Two Colours?🔒 Two-Colourable Graphs Imagine you have a map of friendships. Each person is a dot, and a line connects two people who ar… 65 Dislike Pairs: Splitting People into Two Groups🔒 Dislike Pairs: Can We Split People into Two Friendly Groups? Imagine you are planning a party. You have N people, and yo… 66 Colour Repair: Can a Graph Be Coloured With Just Two Colours?🔒 Colour Repair: Two-Colour a Graph Imagine you have a group of people, and some pairs of them do not get along. You want … 67 Group Colourable: Painting a Graph With Two Colours🔒 Group Colourable: Painting a Graph With Two Colours Imagine you have a set of dots, and some of these dots are connected… 68 Breadth-First Search for the Shortest Path in a Grid🔒 Finding the Shortest Path with Breadth-First Search Imagine you are standing in a maze and you want to reach the exit us… 69 Minimum Steps in a Grid: Finding the Shortest Path🔒 Minimum Steps in a Grid Imagine a city map drawn as a checkerboard. Some squares are open roads you can walk on, and som… 70 Nearest Distance of 1 in a Grid🔒 Finding the Nearest 1 in a Grid Imagine a grid of squares, like a checkerboard. Every square holds either a 0 or a 1. Yo… 71 Shortest Word Transformation: Changing One Letter at a Time🔒 Shortest Word Transformation Imagine you have a starting word and you want to turn it into a different word. But there i… 72 Minimum Steps in a Grid (With k Wall-Breaks)🔒 Minimum Steps in a Grid (With k Wall-Breaks) Imagine a small maze drawn on graph paper. It has N rows and M columns, so … 73 Dijkstra's Algorithm: Finding the Cheapest Path in a Grid🔒 Dijkstra's Algorithm: Finding the Cheapest Path Imagine you are standing at the top-left corner of a board made of squar… 74 Minimum Cost Path in a Grid🔒 Minimum Cost Path in a Grid Imagine a board made of small boxes arranged in rows and columns. This is called a grid. The… 75 Cheapest Flights Within K Stops🔒 Finding the Cheapest Flight With a Limited Number of Stops Imagine you want to fly from one city to another, but you don… 76 Minimum Travel Time Between Cities (with an Odd-Time Waiting Rule)🔒 Finding the Fastest Way Between Two Cities Imagine you have a map of cities connected by roads. Each road takes a certai… 77 Teleporter Grid: Shortest Path with Magic Portals🔒 Teleporter Grid: Finding the Cheapest Path Imagine a board made of small boxes arranged in rows and columns, like a ches…