C ++程序查找循环图的色标
色度索引是给定图的边缘着色所需的最大颜色数。这是一个C++程序，用于查找循环图的色标。
算法
Begin Take the input of the number of vertices ‘n’ and number of edges ‘e’. Take the input of ‘e’ vertex pairs for the ‘e’ edges in the graph in edge[][]. Function ChromaticIndex(), Color the graph edges: A) 为当前边缘分配颜色 as c. B) If any of the adjacent edges have the same color then discard this color and go to flag again and try with next color. C) Print the chromatic index of the cyclic graph. Print the color of each edge. End
示例
#include<iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
int i, c, j, max = -1;
//为每个边缘“i”分配有效的颜色。
for(i = 0; i < e; i++) {
c = 1;
flag:
//为当前边缘分配颜色
ed[i][2] = c;
for(j = 0; j < e; j++) {
if(j == i)
continue;
//检查与边缘i相邻的边缘的颜色。
if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
if(ed[j][2] == ed[i][2]) {
c++;
goto flag;
}
}
}
}
//找到着色索引并返回
for(i = 0; i < e; i++) {
if(max < ed[i][2])
max = ed[i][2];
}
return max;
}
int main() {
int i, v, e, j, max = -1;
cout<<"Enter the number of vertices of the graph: ";
cin>>v;
cout<<"Enter the number of edges of the graph: ";
cin>>e;
int ed[e][3];
for(i = 0; i < e; i++) {
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nV(1): ";
cin>>ed[i][0];
cout<<"V(2): ";
cin>>ed[i][1];
ed[i][2] = -1;
}
cout<<"\n\nThe chromatic index of the given graph is: "<<ChromaticIndex(ed , e);
for(i = 0; i < e; i++)
cout<<"\nThe color of the edge between vertex n(1):"<<ed[i][0]<<" and n(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<".";
return 0;
}输出结果
Enter the number of vertices of the graph:4 Enter the number of edges of the graph: 5 Enter the vertex pair for edge 1 V(1): 2 V(2):1 Enter the vertex pair for edge 2 V(1): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 3 V(2): 1 Enter the vertex pair for edge 4 V(1): 4 V(2): 2 Enter the vertex pair for edge 5 V(1):1 V(2): 3 The chromatic index of the given graph is: 4 The color of the edge between vertex n(1):2 and n(2):1 is: color1. The color of the edge between vertex n(1):3 and n(2):2 is: color2. The color of the edge between vertex n(1):3 and n(2):1 is: color3. The color of the edge between vertex n(1):4 and n(2):2 is: color3. The color of the edge between vertex n(1):1 and n(2):3 is: color4.
热门推荐
5 短祝福语简短暖心
10 结婚祝福语粤语大全简短
11 晚上祝福语女生文案简短
12 法语妈妈生日祝福语简短
13 药厂开工祝福语大全简短
14 蛋糕节日祝福语简短英文
15 跨年的生日祝福语简短
16 文案祝福语英文短句简短
17 在家聚餐婚礼祝福语简短
18 学生节祝福语大全简短