我们介绍 图着色及其应用 在之前的帖子中。正如前一篇文章所讨论的，图着色被广泛使用。不幸的是，由于这个问题是已知的，目前还没有有效的算法来为一个具有最少颜色数的图着色 NP完全问题 .不过，有一些近似算法可以解决这个问题。下面是分配颜色的基本贪婪算法。它并不保证使用最小颜色，但它保证了颜色数量的上限。基本算法从不使用超过d+1的颜色，其中d是给定图形中顶点的最大度数。
null
基本贪婪着色算法：
1. 使用第一种颜色为第一个顶点着色。 2. 对剩余的V-1顶点执行以下操作。 ….. （a） 考虑当前选中的顶点并将其与 编号最低的颜色，以前任何颜色上都没有使用过 相邻的彩色顶点。如果所有以前使用过的颜色 出现在与v相邻的顶点上，为其指定新颜色。
下面是上述贪婪算法的实现。
C++
// A C++ program to implement greedy algorithm for graph coloring #include <iostream> #include <list> using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list< int > *adj; // A dynamic array of adjacency lists public : // Constructor and destructor Graph( int V) { this ->V = V; adj = new list< int >[V]; } ~Graph() { delete [] adj; } // function to add an edge to graph void addEdge( int v, int w); // Prints greedy coloring of the vertices void greedyColoring(); }; void Graph::addEdge( int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph::greedyColoring() { int result[V]; // Assign the first color to first vertex result[0] = 0; // Initialize remaining V-1 vertices as unassigned for ( int u = 1; u < V; u++) result[u] = -1; // no color is assigned to u // A temporary array to store the available colors. True // value of available[cr] would mean that the color cr is // assigned to one of its adjacent vertices bool available[V]; for ( int cr = 0; cr < V; cr++) available[cr] = false ; // Assign colors to remaining V-1 vertices for ( int u = 1; u < V; u++) { // Process all adjacent vertices and flag their colors // as unavailable list< int >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (result[*i] != -1) available[result[*i]] = true ; // Find the first available color int cr; for (cr = 0; cr < V; cr++) if (available[cr] == false ) break ; result[u] = cr; // Assign the found color // Reset the values back to false for the next iteration for (i = adj[u].begin(); i != adj[u].end(); ++i) if (result[*i] != -1) available[result[*i]] = false ; } // print the result for ( int u = 0; u < V; u++) cout << "Vertex " << u << " ---> Color " << result[u] << endl; } // Driver program to test above function int main() { Graph g1(5); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(2, 3); g1.addEdge(3, 4); cout << "Coloring of graph 1 " ; g1.greedyColoring(); Graph g2(5); g2.addEdge(0, 1); g2.addEdge(0, 2); g2.addEdge(1, 2); g2.addEdge(1, 4); g2.addEdge(2, 4); g2.addEdge(4, 3); cout << "Coloring of graph 2 " ; g2.greedyColoring(); return 0; } |
JAVA
// A Java program to implement greedy algorithm for graph coloring import java.io.*; import java.util.*; import java.util.LinkedList; // This class represents an undirected graph using adjacency list class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; //Adjacency List //Constructor Graph( int v) { V = v; adj = new LinkedList[v]; for ( int i= 0 ; i<v; ++i) adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge( int v, int w) { adj[v].add(w); adj[w].add(v); //Graph is undirected } // Assigns colors (starting from 0) to all vertices and // prints the assignment of colors void greedyColoring() { int result[] = new int [V]; // Initialize all vertices as unassigned Arrays.fill(result, - 1 ); // Assign the first color to first vertex result[ 0 ] = 0 ; // A temporary array to store the available colors. False // value of available[cr] would mean that the color cr is // assigned to one of its adjacent vertices boolean available[] = new boolean [V]; // Initially, all colors are available Arrays.fill(available, true ); // Assign colors to remaining V-1 vertices for ( int u = 1 ; u < V; u++) { // Process all adjacent vertices and flag their colors // as unavailable Iterator<Integer> it = adj[u].iterator() ; while (it.hasNext()) { int i = it.next(); if (result[i] != - 1 ) available[result[i]] = false ; } // Find the first available color int cr; for (cr = 0 ; cr < V; cr++){ if (available[cr]) break ; } result[u] = cr; // Assign the found color // Reset the values back to true for the next iteration Arrays.fill(available, true ); } // print the result for ( int u = 0 ; u < V; u++) System.out.println( "Vertex " + u + " ---> Color " + result[u]); } // Driver method public static void main(String args[]) { Graph g1 = new Graph( 5 ); g1.addEdge( 0 , 1 ); g1.addEdge( 0 , 2 ); g1.addEdge( 1 , 2 ); g1.addEdge( 1 , 3 ); g1.addEdge( 2 , 3 ); g1.addEdge( 3 , 4 ); System.out.println( "Coloring of graph 1" ); g1.greedyColoring(); System.out.println(); Graph g2 = new Graph( 5 ); g2.addEdge( 0 , 1 ); g2.addEdge( 0 , 2 ); g2.addEdge( 1 , 2 ); g2.addEdge( 1 , 4 ); g2.addEdge( 2 , 4 ); g2.addEdge( 4 , 3 ); System.out.println( "Coloring of graph 2 " ); g2.greedyColoring(); } } // This code is contributed by Aakash Hasija |
Python3
# Python3 program to implement greedy # algorithm for graph coloring def addEdge(adj, v, w): adj[v].append(w) # Note: the graph is undirected adj[w].append(v) return adj # Assigns colors (starting from 0) to all # vertices and prints the assignment of colors def greedyColoring(adj, V): result = [ - 1 ] * V # Assign the first color to first vertex result[ 0 ] = 0 ; # A temporary array to store the available colors. # True value of available[cr] would mean that the # color cr is assigned to one of its adjacent vertices available = [ False ] * V # Assign colors to remaining V-1 vertices for u in range ( 1 , V): # Process all adjacent vertices and # flag their colors as unavailable for i in adj[u]: if (result[i] ! = - 1 ): available[result[i]] = True # Find the first available color cr = 0 while cr < V: if (available[cr] = = False ): break cr + = 1 # Assign the found color result[u] = cr # Reset the values back to false # for the next iteration for i in adj[u]: if (result[i] ! = - 1 ): available[result[i]] = False # Print the result for u in range (V): print ( "Vertex" , u, " ---> Color" , result[u]) # Driver Code if __name__ = = '__main__' : g1 = [[] for i in range ( 5 )] g1 = addEdge(g1, 0 , 1 ) g1 = addEdge(g1, 0 , 2 ) g1 = addEdge(g1, 1 , 2 ) g1 = addEdge(g1, 1 , 3 ) g1 = addEdge(g1, 2 , 3 ) g1 = addEdge(g1, 3 , 4 ) print ( "Coloring of graph 1 " ) greedyColoring(g1, 5 ) g2 = [[] for i in range ( 5 )] g2 = addEdge(g2, 0 , 1 ) g2 = addEdge(g2, 0 , 2 ) g2 = addEdge(g2, 1 , 2 ) g2 = addEdge(g2, 1 , 4 ) g2 = addEdge(g2, 2 , 4 ) g2 = addEdge(g2, 4 , 3 ) print ( "Coloring of graph 2" ) greedyColoring(g2, 5 ) # This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript program to implement greedy // algorithm for graph coloring // This class represents a directed graph // using adjacency list representation class Graph{ // Constructor constructor(v) { this .V = v; this .adj = new Array(v); for (let i = 0; i < v; ++i) this .adj[i] = []; this .Time = 0; } // Function to add an edge into the graph addEdge(v,w) { this .adj[v].push(w); // Graph is undirected this .adj[w].push(v); } // Assigns colors (starting from 0) to all // vertices and prints the assignment of colors greedyColoring() { let result = new Array( this .V); // Initialize all vertices as unassigned for (let i = 0; i < this .V; i++) result[i] = -1; // Assign the first color to first vertex result[0] = 0; // A temporary array to store the available // colors. False value of available[cr] would // mean that the color cr is assigned to one // of its adjacent vertices let available = new Array( this .V); // Initially, all colors are available for (let i = 0; i < this .V; i++) available[i] = true ; // Assign colors to remaining V-1 vertices for (let u = 1; u < this .V; u++) { // Process all adjacent vertices and // flag their colors as unavailable for (let it of this .adj[u]) { let i = it; if (result[i] != -1) available[result[i]] = false ; } // Find the first available color let cr; for (cr = 0; cr < this .V; cr++) { if (available[cr]) break ; } // Assign the found color result[u] = cr; // Reset the values back to true // for the next iteration for (let i = 0; i < this .V; i++) available[i] = true ; } // print the result for (let u = 0; u < this .V; u++) document.write( "Vertex " + u + " ---> Color " + result[u] + "<br>" ); } } // Driver code let g1 = new Graph(5); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(2, 3); g1.addEdge(3, 4); document.write( "Coloring of graph 1<br>" ); g1.greedyColoring(); document.write( "<br>" ); let g2 = new Graph(5); g2.addEdge(0, 1); g2.addEdge(0, 2); g2.addEdge(1, 2); g2.addEdge(1, 4); g2.addEdge(2, 4); g2.addEdge(4, 3); document.write( "Coloring of graph 2<br> " ); g2.greedyColoring(); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Coloring of graph 1Vertex 0 ---> Color 0Vertex 1 ---> Color 1Vertex 2 ---> Color 2Vertex 3 ---> Color 0Vertex 4 ---> Color 1Coloring of graph 2Vertex 0 ---> Color 0Vertex 1 ---> Color 1Vertex 2 ---> Color 2Vertex 3 ---> Color 0Vertex 4 ---> Color 3
时间复杂度：最坏情况下为O（V^2+E）。
基本算法分析 上述算法并不总是使用最少的颜色数。此外，有时使用的颜色数量取决于顶点的处理顺序。例如，考虑下面两个图。请注意，在右侧的图中，顶点3和4是交换的。如果我们考虑左图中的顶点0, 1, 2，3, 4，我们可以使用3种颜色来着色图。但是如果我们考虑右图中的顶点0, 1, 2、3, 4，则需要4种颜色。
所以顶点的拾取顺序很重要。许多人提出了不同的方法来寻找比基本算法平均效果更好的排序。最常见的是 威尔士-鲍威尔算法 它按度的降序考虑顶点。
基本算法如何保证d+1的上界？ 这里d是给定图中的最大度数。因为d是最大度数，一个顶点不能附加到超过d个顶点。当我们给一个顶点上色时，相邻顶点最多可能已经使用了d色。要给这个顶点上色，我们需要选择相邻顶点不使用的最小编号颜色。如果颜色编号为1，2…。，然后，此类最小数的值必须介于1到d+1之间（请注意，相邻顶点已经拾取了d个数）。 这也可以用归纳法证明。看见 这 视频讲座证明。 我们将很快讨论一些关于色数和图着色的有趣事实。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
