C++ Program to Perform Edge Coloring of a Graph

Code:

#include    bits/stdc++.h

using namespace std;

int n,e,i,j;
vector > > graph;
vector color;
bool vis[100011];

void colour(int node)
{
queue q;
int c=0;
set already_colored;
if(vis[node])
return;
vis[node]=1;

for(i=0;i
{
if(color[graph[node][i].second]!=-1)
{
already_colored.insert(color[graph[node][i].second]);
}
}

for(i=0;i
{
if(!vis[graph[node][i].first])
{
q.push(graph[node][i].first);
}
if(color[graph[node][i].second]==-1)
{
while(already_colored.find(c)!=already_colored.end())
c++;
//cout<
color[graph[node][i].second]=c;
already_colored.insert(c);
c++;
}
}
while(!q.empty())
{
int temp=q.front();
q.pop();
colour(temp);
}
return;
}

int main()
{
int x,y;
set empty;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"\n";
graph.resize(n); //  Number of Vertices.
color.resize(e,-1); // Number of Edges.
memset(vis,0,sizeof(vis));
for(i=0;i
{
cout<<"\nEnter edge vertices of edge "<
cin>>x>>y;
x--; y--;
graph[x].push_back(make_pair(y,i));
graph[y].push_back(make_pair(x,i));
}
colour(0);
for(i=0;i
{
cout<<"Edge "<
}
}


Output:

Case 1:
Enter number of vertices and edges respectively:4 6


Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :2 3

Enter edge vertices of edge 3 :3 4

Enter edge vertices of edge 4 :1 4

Enter edge vertices of edge 5 :2 4

Enter edge vertices of edge 6 :1 3

Edge 1 is coloured 1
Edge 2 is coloured 2
Edge 3 is coloured 1
Edge 4 is coloured 2
Edge 5 is coloured 3
Edge 6 is coloured 3


More C++ Programs: