حل مساله رنگ آمیزی گراف با الگوریتم پس گرد — به زبان ساده

1/* Java program for solution of M Coloring problem 
2   using backtracking */
3public class mColoringProblem { 
4    final int V = 4; 
5    int color[]; 
6  
7    /* A utility function to check if the current 
8       color assignment is safe for vertex v */
9    boolean isSafe(int v, int graph[][], int color[], 
10                   int c) 
11    { 
12        for (int i = 0; i < V; i++) 
13            if (graph[v][i] == 1 && c == color[i]) 
14                return false; 
15        return true; 
16    } 
17  
18    /* A recursive utility function to solve m 
19       coloring  problem */
20    boolean graphColoringUtil(int graph[][], int m, 
21                              int color[], int v) 
22    { 
23        /* base case: If all vertices are assigned 
24           a color then return true */
25        if (v == V) 
26            return true; 
27  
28        /* Consider this vertex v and try different 
29           colors */
30        for (int c = 1; c <= m; c++) 
31        { 
32            /* Check if assignment of color c to v 
33               is fine*/
34            if (isSafe(v, graph, color, c)) 
35            { 
36                color[v] = c; 
37  
38                /* recur to assign colors to rest 
39                   of the vertices */
40                if (graphColoringUtil(graph, m, 
41                                      color, v + 1)) 
42                    return true; 
43  
44                /* If assigning color c doesn't lead 
45                   to a solution then remove it */
46                color[v] = 0; 
47            } 
48        } 
49  
50        /* If no color can be assigned to this vertex 
51           then return false */
52        return false; 
53    } 
54  
55    /* This function solves the m Coloring problem using 
56       Backtracking. It mainly uses graphColoringUtil() 
57       to solve the problem. It returns false if the m 
58       colors cannot be assigned, otherwise return true 
59       and  prints assignments of colors to all vertices. 
60       Please note that there  may be more than one 
61       solutions, this function prints one of the 
62       feasible solutions.*/
63    boolean graphColoring(int graph[][], int m) 
64    { 
65        // Initialize all color values as 0. This 
66        // initialization is needed correct functioning 
67        // of isSafe() 
68        color = new int[V]; 
69        for (int i = 0; i < V; i++) 
70            color[i] = 0; 
71  
72        // Call graphColoringUtil() for vertex 0 
73        if (!graphColoringUtil(graph, m, color, 0)) 
74        { 
75            System.out.println("Solution does not exist"); 
76            return false; 
77        } 
78  
79        // Print the solution 
80        printSolution(color); 
81        return true; 
82    } 
83  
84    /* A utility function to print solution */
85    void printSolution(int color[]) 
86    { 
87        System.out.println("Solution Exists: Following" + 
88                           " are the assigned colors"); 
89        for (int i = 0; i < V; i++) 
90            System.out.print(" " + color[i] + " "); 
91        System.out.println(); 
92    } 
93  
94    // driver program to test above function 
95    public static void main(String args[]) 
96    { 
97        mColoringProblem Coloring = new mColoringProblem(); 
98        /* Create following graph and test whether it is 
99           3 colorable 
100          (3)---(2) 
101           |   / | 
102           |  /  | 
103           | /   | 
104          (0)---(1) 
105        */
106        int graph[][] = {{0, 1, 1, 1}, 
107            {1, 0, 1, 0}, 
108            {1, 1, 0, 1}, 
109            {1, 0, 1, 0}, 
110        }; 
111        int m = 3; // Number of colors 
112        Coloring.graphColoring(graph, m); 
113    } 
114} 
115// This code is contributed by Abhishek Shankhadhar 

1# Python program for solution of M Coloring  
2# problem using backtracking 
3  
4class Graph(): 
5  
6    def __init__(self, vertices): 
7        self.V = vertices 
8        self.graph = [[0 for column in range(vertices)]\ 
9                              for row in range(vertices)] 
10  
11    # A utility function to check if the current color assignment 
12    # is safe for vertex v 
13    def isSafe(self, v, colour, c): 
14        for i in range(self.V): 
15            if self.graph[v][i] == 1 and colour[i] == c: 
16                return False
17        return True
18      
19    # A recursive utility function to solve m 
20    # coloring  problem 
21    def graphColourUtil(self, m, colour, v): 
22        if v == self.V: 
23            return True
24  
25        for c in range(1, m+1): 
26            if self.isSafe(v, colour, c) == True: 
27                colour[v] = c 
28                if self.graphColourUtil(m, colour, v+1) == True: 
29                    return True
30                colour[v] = 0
31  
32    def graphColouring(self, m): 
33        colour = [0] * self.V 
34        if self.graphColourUtil(m, colour, 0) == False: 
35            return False
36  
37        # Print the solution 
38        print "Solution exist and Following are the assigned colours:"
39        for c in colour: 
40            print c, 
41        return True
42  
43# Driver Code 
44g  = Graph(4) 
45g.graph = [[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]] 
46m=3
47g.graphColouring(m) 
48  
49# This code is contributed by Divyanshu Mehta