حل مساله رنگ آمیزی گراف با الگوریتم پس گرد — به زبان ساده
انواع گوناگونی از مسائل رنگآمیزی گراف وجود دارد که مساله رنگ کردن راسهای گراف، یکی از محبوبترین و متداولترین آنها به شمار میآید. در این مساله، یک گراف غیر مستقیم و عدد m داده شده است. هدف رنگ کردن راسهای گراف به صورتی است که هیچ دو راس مجاوری، دارای رنگ مشابه نباشند. m تعداد رنگهای داده شده است. باید توجه داشت که در اینجا منظور از رنگآمیزی، تخصیص رنگ به راسهای گراف است. برای حل مساله رنگ آمیزی گراف، الگوریتمهای گوناگونی ارائه شده که «الگوریتم پس گرد» (Backtracking) و «حریصانه» (Greedy) از این جمله هستند. در این مطلب، هدف حل مساله رنگ آمیزی گراف با الگوریتم پس گرد است.
تعریف مساله
تعداد m رنگ و یک گراف داده شده است. هدف رنگ کردن راسهای این گراف به صورتی است که هیچ دو راس مجاوری دارای یک رنگ مشابه نباشند. ورودی و خروجی مساله، به طور دقیق به شرح زیر هستند.
ورودی:
- یک آرایه دو بعدی، یعنی گراف [graph[V][V که در آن، V تعداد یالها در گراف را مشخص میکند و [graph[V][V نمایش ماتریس همسایگی گراف است. مقدار [graph[i][j در صورتی که یک یال مستقیم از i به j وجود داشته باشد برابر با یک، و در غیر این صورت، مقدار [graph[i][j برابر با ۰ است.
- عدد صحیح m، تعداد کل رنگهایی است که میتوان از آنها استفاده کرد.
خروجی:
آرایه [color[V که باید حاوی اعدادی از ۱ تا m باشد. [color[i باید رنگ تخصیص یافته به iاُمین راس را نشان دهد. همچنین، در صورتی که نمیتوان گراف را با m رنگ طبق شرط موجود رنگآمیزی کرد، کد باید مقدار False را بازگرداند. در ادامه، تصویری از یک گراف داده شده که با m=3 رنگ (سفید، سبز، قرمز) رنگآمیزی شده است.
الگوریتم ساده
الگوریتم ساده ارائه شده در زیر، همه پیکربندیهای ممکن برای رنگآمیزی گراف را که شروط داده شده در آنها رعایت میشود، در خروجی چاپ میکند.
while there are untried conflagrations { generate the next configuration if no adjacent vertices are colored with same color { print this configuration; } }
به تعداد Vm پیکربندی مختلف از رنگها وجود دارد.
حل مساله رنگ آمیزی گراف با الگوریتم پس گرد
ایده اساسی آن است که رنگها یکی یکی به راسهای مختلف اختصاص پیدا کنند. این کار با شروع از راس صفر (۰) آغاز میشود. پیش از تخصیص رنگ، امکانپذیری تخصیص رنگ بر اساس شرط داده شده بررسی میشود.
این کار، با در نظر گرفتن رنگهایی که در حال حاضر به راسهای همسایه تخصیص پیدا کردهاند، صورت میپذیرد. اگر الگوریتم تشخیص دهد که تخصیص یک رنگ مشخص در شرط داده شده صدق میکند، تخصیص رنگ به عنوان بخشی از راهکار انجام میشود. اگر رنگی برای یک راس مشخص پیدا نشود که در شرط مذکور صدق کند، پسگرد انجام و پیغام خطای False صادر میشود.
کد راه حل مساله رنگ آمیزی گراف در ++C/C
1#include<stdio.h>
2#include<stdbool.h>
3
4// Number of vertices in the graph
5#define V 4
6
7void printSolution(int color[]);
8
9/* A utility function to check if the current color assignment
10is safe for vertex v i.e. checks whether the edge exists or not
11(i.e, graph[v][i]==1). If exist then checks whether the color to
12be filled in the new vertex(c is sent in the parameter) is already
13used by its adjacent vertices(i-->adj vertices) or not (i.e, color[i]==c) */
14bool isSafe (int v, bool graph[V][V], int color[], int c)
15{
16 for (int i = 0; i < V; i++)
17 if (graph[v][i] && c == color[i])
18 return false;
19 return true;
20}
21
22/* A recursive utility function to solve m coloring problem */
23bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)
24{
25 /* base case: If all vertices are assigned a color then
26 return true */
27 if (v == V)
28 return true;
29
30 /* Consider this vertex v and try different colors */
31 for (int c = 1; c <= m; c++)
32 {
33 /* Check if assignment of color c to v is fine*/
34 if (isSafe(v, graph, color, c))
35 {
36 color[v] = c;
37
38 /* recur to assign colors to rest of the vertices */
39 if (graphColoringUtil (graph, m, color, v+1) == true)
40 return true;
41
42 /* If assigning color c doesn't lead to a solution
43 then remove it */
44 color[v] = 0;
45 }
46 }
47
48 /* If no color can be assigned to this vertex then return false */
49 return false;
50}
51
52/* This function solves the m Coloring problem using Backtracking.
53 It mainly uses graphColoringUtil() to solve the problem. It returns
54 false if the m colors cannot be assigned, otherwise return true and
55 prints assignments of colors to all vertices. Please note that there
56 may be more than one solutions, this function prints one of the
57 feasible solutions.*/
58bool graphColoring(bool graph[V][V], int m)
59{
60 // Initialize all color values as 0. This initialization is needed
61 // correct functioning of isSafe()
62 int color[V];
63 for (int i = 0; i < V; i++)
64 color[i] = 0;
65
66 // Call graphColoringUtil() for vertex 0
67 if (graphColoringUtil(graph, m, color, 0) == false)
68 {
69 printf("Solution does not exist");
70 return false;
71 }
72
73 // Print the solution
74 printSolution(color);
75 return true;
76}
77
78/* A utility function to print solution */
79void printSolution(int color[])
80{
81 printf("Solution Exists:"
82 " Following are the assigned colors \n");
83 for (int i = 0; i < V; i++)
84 printf(" %d ", color[i]);
85 printf("\n");
86}
87
88// driver program to test above function
89int main()
90{
91 /* Create following graph and test whether it is 3 colorable
92 (3)---(2)
93 | / |
94 | / |
95 | / |
96 (0)---(1)
97 */
98 bool graph[V][V] = {{0, 1, 1, 1},
99 {1, 0, 1, 0},
100 {1, 1, 0, 1},
101 {1, 0, 1, 0},
102 };
103 int m = 3; // Number of colors
104 graphColoring (graph, m);
105 return 0;
106}
کد راه حل مساله رنگ آمیزی گراف در جاوا
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
خروجی
Solution Exists: Following are the assigned colors 1 2 3 2
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
^^
پیچیدگی زمانی این الگوریتم چیست؟