Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit95cab08

Browse files
committed
Switch to a functional approach instead of class-based.
Use proper JSDoc comments.Refine the comments and remove redundancies.
1 parentf945eb1 commit95cab08

File tree

2 files changed

+45
-63
lines changed

2 files changed

+45
-63
lines changed

‎Backtracking/MColoringProblem.js

Lines changed: 39 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -1,65 +1,49 @@
1-
/*
2-
Problem: M Coloring Problem
3-
Given a graph represented as an adjacency matrix and a number M (number of colors),
4-
determine if the graph can be colored with up to M colors such that no two adjacent
5-
vertices share the same color.
1+
//https://en.wikipedia.org/wiki/Edge_coloring
62

7-
What is the M Coloring Problem?
8-
- This problem is about coloring a graph's vertices with at most M different colors
9-
such that no two adjacent vertices have the same color.
3+
// M Coloring Problem
4+
// Given an adjacency matrix representation of a graph and a number M,
5+
// determine if the graph can be colored with up to M colors such that
6+
// no two adjacent vertices share the same color.
107

11-
Example:
12-
- Consider a triangle (3 nodes connected cyclically). We'd need 3 colors to color each vertex
13-
without adjacent vertices having the same color.
8+
functionmColoring(graph,m){
9+
constcolors=newArray(graph.length).fill(0);
1410

15-
Solution:
16-
- We will be using backtracking to solve this question.
17-
- Color a vertex, then move to an adjacent vertex and try all colors. If a color is valid,
18-
continue to the next vertex, else backtrack.
19-
*/
20-
21-
classMColoring{
22-
constructor(graph,m){
23-
this.graph=graph;// adjacency matrix representation
24-
this.m=m;
25-
this.colors=newArray(graph.length).fill(0);
26-
}
27-
28-
isSafe(vertex,color){
29-
for(leti=0;i<this.graph.length;i++){
30-
if(this.graph[vertex][i]&&this.colors[i]===color){
31-
returnfalse;
32-
}
11+
// Check if it's safe to color a vertex with a given color.
12+
functionisSafe(vertex,color){
13+
for(leti=0;i<graph.length;i++){
14+
if(graph[vertex][i]&&colors[i]===color){
15+
returnfalse;
3316
}
17+
}
18+
returntrue;
19+
}
20+
21+
// Use backtracking to try and color the graph.
22+
functionsolveColoring(vertex=0){
23+
if(vertex===graph.length){
3424
returntrue;
3525
}
36-
37-
solveColoring(vertex=0){
38-
if(vertex===this.graph.length){
39-
returntrue;
40-
}
41-
42-
for(letcolor=1;color<=this.m;color++){
43-
if(this.isSafe(vertex,color)){
44-
this.colors[vertex]=color;
45-
46-
if(this.solveColoring(vertex+1)){
47-
returntrue;
48-
}
49-
50-
this.colors[vertex]=0;// backtrack
26+
27+
for(letcolor=1;color<=m;color++){
28+
if(isSafe(vertex,color)){
29+
colors[vertex]=color;
30+
31+
if(solveColoring(vertex+1)){
32+
returntrue;
5133
}
34+
35+
// If no solution, backtrack.
36+
colors[vertex]=0;
5237
}
53-
returnfalse;
54-
}
55-
56-
getSolution(){
57-
if(this.solveColoring()){
58-
returnthis.colors;
59-
}
60-
return[];
6138
}
39+
returnfalse;
6240
}
63-
64-
export{MColoring}
65-
41+
42+
// If coloring is possible, return the colors.
43+
if(solveColoring()){
44+
returncolors;
45+
}
46+
returnnull;
47+
}
48+
49+
export{mColoring};
Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
import{MColoring}from'../MColoringProblem';
1+
import{mColoring}from'../MColoringProblem';
22

33
describe('MColoringProblem',()=>{
44
it('should color a triangle with 3 colors',()=>{
@@ -7,9 +7,8 @@ describe('MColoringProblem', () => {
77
[1,0,1],
88
[1,1,0]
99
];
10-
consttest1=newMColoring(graph,3);
11-
constsolution=test1.getSolution();
12-
expect(solution).not.toEqual([]);
10+
constsolution=mColoring(graph,3);
11+
expect(solution).not.toBeNull();
1312
});
1413

1514
it('should not color a triangle with 2 colors',()=>{
@@ -18,8 +17,7 @@ describe('MColoringProblem', () => {
1817
[1,0,1],
1918
[1,1,0]
2019
];
21-
consttest2=newMColoring(graph,2);
22-
constsolution=test2.getSolution();
23-
expect(solution).toEqual([]);
20+
constsolution=mColoring(graph,2);
21+
expect(solution).toBeNull();
2422
});
25-
});
23+
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp