One Pager Cheat Sheet

• The Graph Coloring Problem can be solved by partitioning the elements into two different sets such that no two adjacent nodes have the same color.
• A graph can be successfully 2-colored by visiting each node and assigning an arbitrary color to the first node, then assigning the opposite color to a node n for any of its adjacent nodes that have already been assigned the same color, or determining that it cannot be validly colored if two or more of its adjacent nodes already have opposite colors.
• The 2-coloring problem can be solved using breadth-first search with each node being assigned the attributes assigned, red and added.
• The entire method is illustrated in the figure below.
• Executing the 2 coloring problem on an adjacency matrix has a time complexity of O(n^2), whereas an adjacency list would have a time complexity of O(nk) where k is the maximum degree of all nodes in the graph.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

var twoColorGraph = function (N, dislikes) {

  if (!dislikes.length) return true;

  const graph = new Map();

  const marked = Array(N + 1).fill(0);

  const stack = [];

​

  // create adjacency list

  for (let [a, b] of dislikes) {

    graph.set(a, (graph.get(a) || new Set()).add(b));

    graph.set(b, (graph.get(b) || new Set()).add(a));

  }

​

  marked[0] = 1;

  stack.push([dislikes[0][0], 1]);

​

  while (stack.length) {

    const [node, mark] = stack.pop();

    marked[node] = mark;

​

    if (graph.has(node)) {

      const neighbors = graph.get(node);

​

      for (let vertex of neighbors) {

        if (marked[vertex] === mark) return false;

        if (marked[vertex] === 0) stack.push([vertex, ~mark]);

      }

    }

​

    if (stack.length === 0 && marked.includes(0)) {

      for (let i = 1; i < marked.length; i++) {

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.