C ++程序对完整图形执行边缘着色
完整图是在任意一对顶点之间具有连接边的图。这是一个在完整图形上执行边缘着色的C++程序。
算法
Begin
输入顶点数“n”。
用e=n*(n-1)/2条边构造一个完整的图，在ed[][]中。
函数EdgeColor()用于为图形边缘着色。
A） 最初将颜色指定给当前边，即1。
B） 不相干
放弃此颜色并再次转到标志并尝试下一种颜色。
C） 打印每个边的颜色。
End示例
#include<iostream>
using namespace std;
void EdgeColor(int ed[][3], int e) {
int i, c, j;
for(i = 0; i < e; i++) {
c = 1; //assign color to current edge as c i.e. 1 initially.
flag:
ed[i][2] = c;
//如果任何相邻边都占据相同的颜色，则
discard this color and go to flag again and try next color.
for(j = 0; j < e; j++) {
if(j == i)
continue;
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;
}
}
}
}
}
int main() {
int i, n, e, j, cnt = 0;
cout<<"Enter the number of vertexes for the complete graph: ";
cin>>n;
e = (n*(n-1))/2;
int ed[e][3];
for(i = 1; i <= n; i++) {
for(j = i+1; j <= n; j++) {
ed[cnt][0] = i;
ed[cnt][1] = j;
ed[cnt][2] = -1;
cnt++;
}
}
EdgeColor(ed , e);
for(i = 0; i < e; i++)
cout<<"\nThe color of the edge between vertex
n1):"<<ed[i][0]<<" and n(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<".";
}输出结果
Enter the number of vertexes for the complete graph: 4 The color of the edge between vertex n(1):1 and n(2):2 is: color1. The color of the edge between vertex n(1):1 and n(2):3 is: color2. The color of the edge between vertex n(1):1 and n(2):4 is: color3. The color of the edge between vertex n(1):2 and n(2):3 is: color3. The color of the edge between vertex n(1):2 and n(2):4 is: color2. The color of the edge between vertex n(1):3 and n(2):4 is: color1.