Graphs | Skilled.dev
Learn

Graphs

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

Graphs are a non-linear data structure of nodes connected by edges (). Graphs creates a network of nodes. While graphs can be intimidating as a data structure, they actually have many direct real-world applications that make them easier to visualize. This section will make sure you fully understand graphs by first understanding them in a practical context, then moving to the most simple case in how we think about them in our code, and finally building from this until you fully understand everything you need to know for interviews.

(SOMEWHERE IN ARTICLE) NEED TO DISCUSS HOW GRAPHS ARE CONSTRUCTED WITH NODES AND EDGES. Or is this in the implement section?

Cheat Sheet

Graph SVG
Pros 🔥
  • Model Relationships
    Graphs are the best data structure to represent data/items/people that have complex relationships.
Cons 🤕
  • Scalability
    Most graph algorithms are slow at O(n log n) or worse.

Graphs in Interviews

  • Take an input node an be able to walk through a graph
  • Traverse a graph using DFS vs BFS and know the benefits of each method
  • Understand or detect the corner cases: empty, one or two nodes, disjoint, cycles [MENTION THIS SOMEWHERE IN THE ARTICLE?]
  • How to handle graphs represented using other data structures such as a 2D matrix
  • Find the shortest path between two nodes
  • In a directed graph, determine if you can there is a path between node(s)
  • Looking for node(s) and start a new traversal from them if found
  • Determine the number of siblings to a node that matches a certain criteria or determine if they follow a pattern

Graphs Explained

You may be thinking graphs look very similar to linked lists and trees, and you would be right! Linked lists and trees are implementations of graphs with specific constraints, so everything you learned in those sections will just be generalized here and built upon.

terms: node, vertex, edge, pointer

Real-World Examples

(define terms here or below the real world example? I use them, but hopefully they're obvious and can be solidified at the bottom)

Before we dive, let's understand how we use graphs in the real world. With Twitter, at its most basic level, it is a bunch of user accounts that follow each other.

(IMAGE - people following, maybe following back, friends through friends, people not connected at all.)

Each user is a node and the follower relationship is the edge that connects them. The types of relationships include:

  1. A single direction (a person follows and the other does not follow back)
  2. Bi-directional relationship where they each follow
  3. Clusters of friends where many people follow each other
  4. Connected through friends where neither person follows each other but there is a path from a mututal connection
  5. People who don't follow each other and have no friends in common

All of these cases directly translate to different constructions of graphs that you will learn about below.

Another common example of graphs are families, and we even borrow terminology from families when we discuss graphs (ie. child, parent, sibling, cousin nodes). You are directly related to your parents and siblings, you have cousins that are your family based on your parents relationships, and if you have your own children, you are extending the family with new nodes.

Other examples of graphs include:

  • Web pages (nodes) and being connected through links (edges)
  • Google maps with the locations being nodes and the streets connecting them as edges
  • Amazon product recommendations where they advertise items based on other people who bought similar goods

Types of Graphs

The term "graph" broadly applies to all data structures and implementations where nodes are connected by edges. We have already covered two special implementations of graphs that impose constraints which we recognize as their own data structures: linked lists and trees.

^ use this or nore really the same thing?

We can define how the edges or nodes are implemented to model how we use a graph in our code or in an interview.

Do I even need an intro or just jump in?

Directed vs Undirected

A directed graph means you can only move in one direction....

An undirected graph means it move in either direction....

Cyclic vs Acyclic

Connected vs Unconnected

Weighted vs Unweighted

Example, using google maths where an edge has weight which could be the time between the nodes. Google maps would give you the path that minimizes the time (weight) to visit all the locations.

Color Graphs?

Traversing a Graph: DFS vs BFS

Understanding breadth-first search (BFS) and depth-first search (DFS) is essential, and you should feel comfortable implementing both.

**Depth-first search: Implemented using a stack and goes as deep as it can first. It fully explores a path before checking another. It goes deep before it goes wide. DFS is often more intuitive and can easily be represented recursively.

Breadth-first search: Implemented using a queue and visits the closest nodes first. It explores neighbors before children and goes wide before it goes deep. This is used to find the shortest past of one node to another.

This is the exact same for graphs and trees. We mostly perform DFS on trees, but it can also be done by traversing the tree levels which is BFS. With graphs, the implementation is very similar, but we just have to consider additional edge cases since the the structure is less defined. We also must choose between DFS and BFS based on how the problem's requirements.

Often for graph interview questions, performing the traverse is half the battle. Then you just visit each node and utilize or validate its data.

Representing a Graph

Although the most common way to represent a graph is by using single nodes connected by pointers, it can be represened using other data structures as well.

Adjacency matrix, adjacency list, edge list, hash map of hash maps?

adjacency list is the most common

https://visualgo.net/en/graphds

Adjacency List

An adjacency list is one of the most common ways to represent a graph. A hash table is used where the keys are nodes and the values are arrays of its connected neighbors. A given key will have edges to the nodes in its array which can either be directed or undirected.

const adjacencyListGraph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3],
};

Which can be visualized as:

Exercise: Guess the Graph

Different graph images and a hidden answer.

Or a real-world description and the answer.

Prev
Closest Common Ancestor in Binary Tree
Next
Depth-First Search

Table of Contents