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 usingbreadth-first search
with each node being assigned the attributesassigned
,red
andadded
. - The entire
method
is illustrated in the figurebelow
. - 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 ofO(nk)
wherek
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
86
}
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++) {
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.