Graphs | Skilled.dev
Learn

Graphs

Course launching November 17, 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! 🤓
Loading...

Graphs are a non-linear data structure of nodes connected by edges (pointers to other nodes). Graphs create 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 — you'll also find the questions can be easy once you grasp the fundamentals.

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.

Important terms:

  • node (vertex) - an item in the graph
  • edge - how a nodes are connected to each other

Cheat Sheet

0123456
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(V + E) [the number of vertexes + edges] 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, disconnected, cycles
  • 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 there is a path between nodes
  • Search for nodes 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.

Real-World Examples

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.

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

Viewing it as a graph we're more accustomed to:

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

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

Graphs can be implemented with different constraints. Below are the most common you'll need for coding interviews.

Directed vs Undirected

A directed graph means an edge specifies the direction that you must follow to get to one node from another.

An undirected graph means it move in either direction between.

Cyclic vs Acyclic

A cyclic graph is one that has a path that forms a loop. You can follow items along this path and eventually return to the original node without changing directions.

An acyclic graph means there are no cycles.

Connected vs Disconnected

A connected graph is one where all nodes have a path between every other node.

A disconnected graph is one where there are multiple groups of nodes where there is no path connecting them. These are also called disjoint graphs.

Weighted vs Unweighted

A weighted graph means there is a value assigned to each edge. For the solution, you may want to maximize or minimize the total weight of following a path.

For example, selecting your GPS route works as a weighted graph where an edge's weight which could be the time between the locations (nodes). Google Maps would give you the path that minimizes the time (weight) to visit all the locations, which may or may not be the actual shortest path because of other factors such as traffic.

An unweighted graph is what we've already been discussing where every edge valued the same.

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

One way graphs are represented in interviews is to be given a started node and then traverse it using its edges.

class GraphNode {
  constructor(data) {
    this.data = data;
    this.edges = [];
  }
}

It's also possible to represent graphs using other data structures like a hash table or matrix.

Credit: VisuAlgo

Adjacency List

We'll use the following graph in our examples:

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 each value is array of the node's 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],
};

Adjacency Matrix

A matrix where a 1 means there is a connection between nodes, and a 0 means there is not a connection. The index of the row or column represents the node value.

const adjacencyMatrixGraph = [
  // node: 0, 1, 2, 3, 4
          [0, 1, 1, 0, 0], // node 0
          [1, 0, 0, 1, 0], // node 1
          [1, 0, 0, 1, 0], // node 2
          [0, 1, 1, 0, 1], // node 3
          [0, 0, 0, 1, 0], // node 4
];

Node 3 is has an edge with node 1, 2, and 4. So, adjacencyMatrixGraph[3][1], adjacencyMatrixGraph[3][2], adjacencyMatrixGraph[3][4] all equal 1.

Likewise, adjacencyMatrixGraph[1][3], adjacencyMatrixGraph[2][3], adjacencyMatrixGraph[4][3] all equal 1 (in addition to their other edges).

Edge List

An edge list contains arrays of two items where each array represents two nodes that share an edge.

const edgeListGraph = [
  [0, 1], // edge between 0 and 1
  [0, 2], // edge between 0 and 2
  [1, 3], // edge between 1 and 3
  [2, 3], // edge between 2 and 3
  [3, 4], // edge between 3 and 4
];
Prev
Closest Common Ancestor in Binary Tree
Next
Depth-First Search
Loading...

Table of Contents