資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究圖著色
圖著色問題是圖示記的一個特殊情況。在這個問題中，每個節點都著上特定顏色。但是著色有一些約束條件。我們不能對任何相鄰頂點使用相同的顏色。
為了解決這個問題，我們需要使用貪婪演算法，但它不能保證使用最小顏色。
輸入和輸出
Input: Adjacency matrix of the graph. 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 Output: Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
演算法
graphColoring(graph)
輸入 − 給定的圖。
輸出 − 每個節點都分配了一些顏色。
Begin declare a list of colors initially set the color 0 for first node define an array colorUsed to track which color is used, and which colors have never used. for all vertices i except first one, do mark i as unassigned to any color done mark colorUsed to false for all vertices for all vertices u in the graph except 1st vertex, do for all vertex v adjacent with u, do if color[v] is unassigned, then mark colorUsed[color[v]] := true done for all colors col in the color list, do if color is not used, then stop the loop done color[u] := col for each vertex v which is adjacent with u, do if color[v] is unassigned, then colorUsed[color[v]] := false done done for all vertices u in the graph, do display the node and its color done End
示例
#include<iostream>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void graphColoring() {
int color[NODE];
color[0] = 0; //Assign first color for the first node
bool colorUsed[NODE]; //Used to check whether color is used or not
for(int i = 1; i<NODE; i++)
color[i] = -1; //initialize all other vertices are unassigned
for(int i = 0; i<NODE; i++)
colorUsed[i] = false; //initially any colors are not chosen
for(int u = 1; u<NODE; u++) { //for all other NODE - 1 vertices
for(int v = 0; v<NODE; v++) {
if(graph[u][v]){
if(color[v] != -1) //when one color is assigned, make it unavailable
colorUsed[color[v]] = true;
}
}
int col;
for(col = 0; col<NODE; col++)
if(!colorUsed[col]) //find a color which is not assigned
break;
color[u] = col; //assign found color in the list
for(int v = 0; v<NODE; v++) { //for next iteration make color availability to false
if(graph[u][v]) {
if(color[v] != -1)
colorUsed[color[v]] = false;
}
}
}
for(int u = 0; u<NODE; u++)
cout <<"Color: " << u << ", Assigned with Color: " <<color[u] <<endl;
}
main() {
graphColoring();
}輸出
Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
更新時間：2020 年 6 月 16 日
6K+ 瀏覽量
廣告