JavaScript/Backtracking/MColoringProblem.js at master · ChrisJr404/JavaScript

49 lines (42 loc) · 1.27 KB

/**
 * Colors a graph using up to m colors such that no two adjacent vertices share the same color.
 * @param {number[][]} graph - Adjacency matrix of the graph, using 0 for no edge.
 * @param {number} m - The number of colors to use.
 * @returns {?Array.<number>} A valid M-coloring of the graph using colors 1 to m, or null if none exists.
 * @see https://en.wikipedia.org/wiki/Graph_coloring
 */
function mColoring(graph, m) {
  const colors = new Array(graph.length).fill(0)

  // Check if it's safe to color a vertex with a given color.
  function isSafe(vertex, color) {
    for (let i = 0; i < graph.length; i++) {
      if (graph[vertex][i] && colors[i] === color) {
        return false
      }
    }
    return true
  }

  // Use backtracking to try and color the graph.
  function solveColoring(vertex = 0) {
    if (vertex === graph.length) {
      return true
    }

    for (let color = 1; color <= m; color++) {
      if (isSafe(vertex, color)) {
        colors[vertex] = color

        if (solveColoring(vertex + 1)) {
          return true
        }

        // If no solution, backtrack.
        colors[vertex] = 0
      }
    }
    return false
  }

  // If coloring is possible, return the colors.
  if (solveColoring()) {
    return colors
  }
  return null
}

export { mColoring }

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Expand file tree

Search code, repositories, users, issues, pull requests...

FilesExpand file tree

MColoringProblem.js

Latest commit

History

MColoringProblem.js

File metadata and controls

Expand file tree