GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — JavaScript/Backtracking/MColoringProblem.js at master · TheAlgorithms/JavaScript Expand file tree/ Copy pathMColoringProblem.jsMore file actions 49 lines (42 loc) · 1.27 KB / Copy pathMColoringProblem.jsFile metadata and controls49 lines (42 loc) · 1.27 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * 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 } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |