Example Graph

Visual Aid

Example Code

class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

let a = new GraphNode("a");
let b = new GraphNode("b");
let c = new GraphNode("c");
let d = new GraphNode("d");
let e = new GraphNode("e");
let f = new GraphNode("f");
a.neighbors = [b, c, e];
c.neighbors = [b, d];
e.neighbors = [a];
f.neighbors = [e];

Basics

A graph is any collection of nodes and edges.
- Much more relaxed in structure than a tree.
It doesn’t have to have a root node (so not every node can be accessed from a single node)
It could have cycles (a group of nodes whose paths begin and end at the same node)
Any number of edges may leave a node

Ways To Reference a Graph Data Structure

Visual Reference

Adjacency Matrix

The row index will corespond to the source of an edge and the column index will correspond to the edges destination.

When the edges have a direction, matrix[i][j] may not be the same as matrix[j][i]
It is common to say that a node is adjacent to itself so matrix[x][x] is true for any node
Will be O(n^2) space complexity

A 2D Array as the method of storing the location of Nodes

let matrix = [

	A	B	C	D	E	F
A	[True,	True,	True,	False,	True,	False]
B	[False,	True,	False,	False,	False,	False]
C	[False,	True,	True,	True,	False,	False]
D	[False,	False,	False,	True,	False,	False]
E	[True,	False,	False,	False,	True,	False]
F	[False,	False,	False,	False,	True,	True]

];

Adjacency List

Seeks to solve the shortcomings of the matrix implementation. It uses an object where keys represent node labels and values associated with that key are the adjacent nodes.

let graph = {
  a: ["b", "c", "e"],
  b: [],
  c: ["b", "d"],
  d: [],
  e: ["a"],
  f: ["e"],
};

Graph Traversal

Depth First

With a Node Class

Node Class Example

There may not always be a suitable root-like starting point. But in this example all the nodes can be traversed to in some way from the “f” node

class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

let a = new GraphNode("a");
let b = new GraphNode("b");
let c = new GraphNode("c");
let d = new GraphNode("d");
let e = new GraphNode("e");
let f = new GraphNode("f");
a.neighbors = [e, c, b];
c.neighbors = [b, d];
e.neighbors = [a];
f.neighbors = [e];

Recursive Traversal

function depthFirstRecur(node, visited = new Set()) {
  if (visited.has(node.val)) return;

  console.log(node.val);
  visited.add(node.val);

  node.neighbors.forEach((neighbor) => {
    depthFirstRecur(neighbor, visited);
  });
}

depthFirstRecur(f); // starting with f as it is a node that can reach all other nodes

Iterative Traversal

 >function depthFirstIter(node) {
  let visited = new Set();
  let stack = [node];

  while (stack.length) {
    let node = stack.pop();

    if (visited.has(node.val)) continue;

    console.log(node.val);
    visited.add(node.val);

    stack.push(...node.neighbors);
  }
}

depthFirstIter(f);

With an Adjacency List

Adjacency List Example

Remember that the nodes are stored as strings in an array in an object.

let graph = {
  a: ["b", "c", "e"],
  b: [],
  c: ["b", "d"],
  d: [],
  e: ["a"],
  f: ["e"],
};

Recursive Example

 >function depthFirstRecur(node, graph, visited = new Set()) {
  if (visited.has(node)) return;

  console.log(node);
  visited.add(node);

  graph[node].forEach((neighbor) => {
    depthFirstRecur(neighbor, graph, visited);
  });
}

depthFirstRecur("f", graph);

Dynamic Recursive Example

 >function depthFirst(graph) {
  let visited = new Set();

  for (let node in graph) {
    _depthFirstRecur(node, graph, visited);
  }
}

function _depthFirstRecur(node, graph, visited) {
  if (visited.has(node)) return;

  console.log(node);
  visited.add(node);

  graph[node].forEach((neighbor) => {
    _depthFirstRecur(neighbor, graph, visited);
  });
}

depthFirst(graph);