Presentamos la coloración de gráficos y las aplicaciones en la publicación anterior. Como se discutió en la publicación anterior, la coloración de gráficos se usa ampliamente. Desafortunadamente, no existe un algoritmo eficiente disponible para colorear un gráfico con un número mínimo de colores, ya que el problema es un problema NP completo conocido . Sin embargo, existen algoritmos aproximados para resolver el problema. A continuación se muestra el algoritmo Greedy básico para asignar colores. No garantiza el uso de colores mínimos, pero garantiza un límite superior en la cantidad de colores. El algoritmo básico nunca usa más de d+1 colores donde d es el grado máximo de un vértice en el gráfico dado.
Algoritmo de coloración codicioso básico:
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 \n";
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 << "\nColoring of graph 2 \n";
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("\nColoring 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>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA