C ++程序执行图形的边缘着色
在此程序中，我们将执行图的边缘着色，其中我们必须为图的边缘着色，以使两个相邻的边缘都不具有相同的颜色。示例中的步骤。
算法
Begin Take the input of the number of vertices, n, and then number of edges, e, in the graph. The graph is stored as adjacency list. BFS is implemented using queue and colors are assigned to each edge. End
示例
#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
queue<int> q;
int c = 0;
set<int> vertex_colored;
if(v[n])
return;
v[n] = 1;
for(i = 0;i<g[n].size();i++) {
if(color[g[n][i].second]!=-1) {
vertex_colored.insert(color[g[n][i].second]);
}
}
for(i = 0;i<g[n].size();i++) {
if(!v[g[n][i].first]) {
q.push(g[n][i].first);
}
if(color[g[n][i].second]==-1) {
while(vertex_colored.find(c)!=vertex_colored.end())
c++;
color[g[n][i].second] = c;
vertex_colored.insert(c);
c++;
}
}
while(!q.empty()) {
int temp = q.front();
q.pop();
col(temp);
}
return;
}
int main() {
int u,w;
set<int> empty;
cout<<"分别输入顶点和边的数量：";
cin>>n>>e;
cout<<"\n";
g.resize(n); //number of vertices
color.resize(e,-1); //number of edges
memset(v,0,sizeof(v));
for(i = 0;i<e;i++) {
cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
cin>>u>>w;
u--; w--;
g[u].push_back(make_pair(w,i));
g[w].push_back(make_pair(u,i));
}
col(0);
for(i = 0;i<e;i++) {
cout<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
<< "\n";
}
}输出结果
分别输入顶点和边的数量：4 5 Enter edge vertices of edge 1 :1 2 Enter edge vertices of edge 2 :2 3 Enter edge vertices of edge 3 :1 1 Enter edge vertices of edge 4 :3 4 Enter edge vertices of edge 5 :1 4 Edge 1 is coloured with colour 1 Edge 2 is coloured with colour 2 Edge 3 is coloured with colour 2 Edge 4 is coloured with colour 1 Edge 5 is coloured with colour 3
热门推荐
10 财运虎年祝福语简短语
11 单亲爸爸春节祝福语简短
12 狗狗上厕所训练
13 植物种植祝福语简短
14 翻译考试祝福语朋友简短
15 个人周年庆简短祝福语
16 狗狗怎么训练
17 分别祝福语简短搞笑英文
18 生日广州男生祝福语简短