11"""
22 Graph Coloring also called "m coloring problem"
3- consists of coloring given graph with at most m colors
4- such that no adjacent vertices are assigned same color
3+ consists of coloring a given graph with at most m colors
4+ such that no adjacent vertices are assigned the same color
55
66 Wikipedia: https://en.wikipedia.org/wiki/Graph_coloring
77"""
@@ -11,9 +11,9 @@ def valid_coloring(
1111 neighbours : list [int ], colored_vertices : list [int ], color : int
1212) -> bool :
1313 """
14- For each neighbour check if coloring constraint is satisfied
14+ For each neighbour check if the coloring constraint is satisfied
1515 If any of the neighbours fail the constraint return False
16- If all neighbours validate constraint return True
16+ If all neighbours validate the constraint return True
1717
1818 >>> neighbours = [0,1,0,1,0]
1919 >>> colored_vertices = [0, 2, 1, 2, 0]
@@ -41,14 +41,14 @@ def util_color(
4141
4242 Base Case:
4343 1. Check if coloring is complete
44- 1.1 If complete return True (meaning that we successfully colored graph)
44+ 1.1 If complete return True (meaning that we successfully colored the graph)
4545
4646 Recursive Step:
47- 2. Itterates over each color:
48- Check if current coloring is valid:
47+ 2. Iterates over each color:
48+ Check if the current coloring is valid:
4949 2.1. Color given vertex
50- 2.2. Do recursive call check if this coloring leads to solving problem
51- 2.4. if current coloring leads to solution return
50+ 2.2. Do recursive call, check if this coloring leads to a solution
51+ 2.4. if current coloring leads to a solution return
5252 2.5. Uncolor given vertex
5353
5454 >>> graph = [[0, 1, 0, 0, 0],
0 commit comments