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

Commitf945eb1

Browse files
committed
Implemented M Coloring Problem
1 parent60443c7 commitf945eb1

File tree

2 files changed

+90
-0
lines changed

2 files changed

+90
-0
lines changed

‎Backtracking/MColoringProblem.js

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
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.
6+
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.
10+
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.
14+
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+
}
33+
}
34+
returntrue;
35+
}
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
51+
}
52+
}
53+
returnfalse;
54+
}
55+
56+
getSolution(){
57+
if(this.solveColoring()){
58+
returnthis.colors;
59+
}
60+
return[];
61+
}
62+
}
63+
64+
export{MColoring}
65+
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
import{MColoring}from'../MColoringProblem';
2+
3+
describe('MColoringProblem',()=>{
4+
it('should color a triangle with 3 colors',()=>{
5+
constgraph=[
6+
[0,1,1],
7+
[1,0,1],
8+
[1,1,0]
9+
];
10+
consttest1=newMColoring(graph,3);
11+
constsolution=test1.getSolution();
12+
expect(solution).not.toEqual([]);
13+
});
14+
15+
it('should not color a triangle with 2 colors',()=>{
16+
constgraph=[
17+
[0,1,1],
18+
[1,0,1],
19+
[1,1,0]
20+
];
21+
consttest2=newMColoring(graph,2);
22+
constsolution=test2.getSolution();
23+
expect(solution).toEqual([]);
24+
});
25+
});

0 commit comments

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