Section Menu

How do I use this section?

1. LESSON

The Simple Reference to Graphs

Graphs are one of the most common data structures in computer science. Especially with today's machine learning and artificial intelligence trends, understanding them is crucial. A shocking amount of real life things can be modeled with graphs. Humans think in associations, so it's obvious why connecting things in this way is practical. But graph...

20 minutes Mark Completed

2. LESSON

Implementing Graphs: Edge List, Adjacency List, Adjacency Matrix

For many students, the graph data structure can be intimidating and difficult to learn. In fact, some of their properties can be baffling to even experienced developers and computer science graduates who haven't worked with them for a while. But graphs are interesting and integral, as they are a vital way of modeling and displaying information...

57 minutes Mark Completed

3. LESSON

Graph Theory: Basic Graph Algorithms Explained

A graph is made up of a limited number of vertices or nodes and a set of edges that link them. When two vertices are connected by the same edge, they are said to be neighboring. In real-world settings such as social media networks, online pages and connections, and GPS locations and itineraries, _graphs have become a v...

79 minutes Mark Completed

4. LESSON

Stay On Top of Topological Sort

Objective: In this lesson, we'll cover this concept, and focus on these outcomes: You'll learn what topological sort is. We'll show you how to use this concept in programming interviews. You'll see how to utilize this concept in challenges. In this lesson, we are g...

27 minutes Mark Completed

5. LESSON

An Illustrated Guide to Dijkstra's Algorithm

In this lesson, we will learn about Dijkstra's algorithm, with a focus on following key points: What is Dijkstra's Algorithm? What are shortest path problems? See a working implementation of Djikstra's algorithm in Python The field of computer science encompasses a wide variety of p...

79 minutes Mark Completed

6. LESSON

An Illustrated Guide to Bellman-Ford and Floyd-Warshall

In this lesson, we will continue where we left off with Dijkstra's, and learn about other different shortest path algorithms. We'll have a focus on following key points: What are some other shortest path algorithms, other than Dijkstra's algorithm? How can we better understand Bellman-Ford and `Floyd-W...

22 minutes Mark Completed

7. LESSON

Understanding Prim's Algorithm

Objective: In this lesson, we’ll deep-dive into one of the most widely used greedy algorithms – Prim’s algorithm. We’ll focus on: Defining the algorithm Going through a detailed step-by-step example on how the algorithm works The algorithm’s real-life applications **Pr...

33 minutes Mark Completed

8. LESSON

Getting to Know Greedy Algorithms Through Examples

In this tutorial, we'll look at yet another technique for finding an optimal solution to a problem. Dynamic programming considers all the solutions of a problem and selects the best or optimal one. But despite finding the most efficient solution, the problem is still speed and memory. For a large...

34 minutes Mark Completed

9. LESSON

What to Know About the Union Find Algorithm

Objective: Unlocking the Power of Union-Find In Today's Lesson, You Will: Understand what Union-Find is and why it's crucial. Learn how to apply Union-Find in technical interviews. Gain insights into solving challenges that require network connectivity. Setting the Stage: Where Al...

77 minutes Mark Completed

10. LESSON

Kruskal's Algorithm: Navigating Minimum Spanning Trees

Kruskal's Algorithm: Your Coding Interview Compass for Navigating Minimum Spanning Trees Welcome to the fascinating realm of graph algorithms! Today, we're diving into Kruskal's Algorithm—a topic that often surfaces in coding interviews. Why? Because it's like a Swiss Army knife for showcasing your mastery of computer science basics. Intr...

30 minutes Mark Completed

11. LESSON

What Is The Manhattan Distance?

The Manhattan Distance is used to calculate the distance between two coordinates in a grid-like path. Imagine you are on holidays in New York City, you are visiting the Empire State Building and decide to walk to The Morgan Library & Museum by the route below. From the map it is easy to see why Manhattan Di...

18 minutes Mark Completed

12. CHALLENGE

Implement a Graph

Since a graph is one of the more difficult data structures to conceptualize in a programmatic 2D manner, let's go ahead and implement it! We'll go with an adjacency list version. Note that there's also the adjacency matrix method which we will cover later. <img src="https://storage.go...

Difficulty: 4/10 Mark Completed

13. CHALLENGE

Find Deletion Distance

Can you determine the deletion distance between two strings? Let's define the deletion distance as the numbers of characters needed to delete from two strings to make them equal. <img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/multistep/find-deletion-distance/find-deletion-distance-4.png" class="img...

Difficulty: 7/10 Mark Completed

14. CHALLENGE

Levenshtein Edit Distance

An edit distance is a way to quantify how different two strings are. This is calculated using the minimum number of transformations to turn one string to another. The transformations include insertion, deletion, and substitution. So when comparing two identical strings, say cat and cat, the edit distance would be `...

Difficulty: 7/10 Mark Completed

15. CHALLENGE

Is This Graph a Tree

Given an undirected graph, can you see if it's a tree? If so, return true and false otherwise. An undirected graph is a tree base...

Difficulty: 7/10 Mark Completed

16. CHALLENGE

Pick A Sign

We're given an array of positive integers like the following: `js [2, 1, 3, 2] ` Imagine that we're allowed to make each element of the array either a positive or negative number, indicated by a signage -- either a plus (+) or minus (-) sign that appears before it. If we sum up all the signed elements, we will get a tot...

Difficulty: 7/10 Mark Completed

17. CHALLENGE

Flood Fill Paintbucket

Imagine the implementation for the paintbucket feature in Microsoft Paint, or how certain image filters work. You click on a specific pixel on a screen, and every similar-colored neighboring pixel would change to your selected color. Let's implement a simpler version of that feature. <img src="https://storage.googleapis.com/algo...

Difficulty: 7/10 Mark Completed

18. CHALLENGE

Most Strongly Connected

Challenge: Finding the Largest Island of Connected Ones in a Matrix Introduction Imagine you're an explorer on a digital ocean filled with islands made up of ones (1s) and water represented by zeroes (0s). Your task is to find the largest island composed of connected 1s in a given 2D grid (or matrix). Here's a samp...

Difficulty: 8/10 Mark Completed

19. CHALLENGE

Course Prerequisites

Here's a classic challenge that comes up in real-life interviews surprisingly often. Interviewers like it as a way to assess your ability to find the right data structure for a non-obvious and non-trivial use case. <img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/course-prerequisites-cover-image.p...

Difficulty: 8/10 Mark Completed

20. CHALLENGE

Detect An Undirected Graph Cycle

Can you detect a cycle in an undirected graph? Recall that an undirected graph is one where the edges are bidirectional. A cycle is one where there is a closed path, that is, the first and last graph vertices can be the same. <img src="https://stor...

Difficulty: 9/10 Mark Completed

21. CHALLENGE

The Two Coloring Graph Problem

Question Given a graph, can you use two colors to color each node of the graph, such that no two adjacent nodes have the same color? The Problem The graph coloring problem is a well-known problem in computer science. It requires coloring different node...

Difficulty: 6/10 Mark Completed

22. CHALLENGE

Shortest Path Distance in Matrix

You are given a 2D matrix with several characters contained in its cells. You will also have two distinct characters which are guaranteed to be in the given matrix. Your job will be to find the minimum manhattan distance between the two characters in the matrix. The manhattan distance of...

Difficulty: 8/10 Mark Completed

Cheat Sheet

• Quick summary: a data structure that stores items in a connected, non-hierarchical network.
• Important facts:
  • Each graph element is called a node, or vertex.
  • Graph nodes are connected by edges.
  • Graphs can be directed or undirected.
  • Graphs can be cyclic or acyclic. A cyclic graph contains a path from at least one node back to itself.
  • Graphs can be weighted or unweighted. In a weighted graph, each edge has a certain numerical weight.
  • Graphs can be traversed. See important facts under Tree for an overview of traversal algorithms.
  • Data structures used to represent graphs:
    • Edge list: a list of all graph edges represented by pairs of nodes that these edges connect.
    • Adjacency list: a list or hash table where a key represents a node and its value represents the list of this node's neighbors.
    • Adjacency matrix: a matrix of binary values indicating whether any two nodes are connected.
• Pros:
  • Ideal for representing entities interconnected with links.
• Cons:
  • Low performance makes scaling hard.
• Notable uses:
  • Social media networks.
  • Recommendations in ecommerce websites.
  • Mapping services.
• Time complexity (worst case): varies depending on the choice of algorithm. O(n*lg(n)) or slower for most graph algorithms.
• See also:
  • The Simple Reference to Graphs