Lost in my C programming class Can anyone help please Think

Lost in my C programming class! Can anyone help please?!

Think of a heuristic for the graph vertex coloring problem. write a pseudo code to explain your heuristic Use an example to show how your heuristic works Find a counter-example where your heuristic fails to find an solution.

Solution

Heuristic: Heuristic is used in algorithms to find the solution in all the possible caese,but it is not sure that the solution is the best one . The heuristic we are using is the greedy algorithm.

1) pseudo code to explain the heuristic:

code:

#include <iostream>

#include <list>

using namespace std;

class graph;

int v;

list<int> *adj;

/ a dynamic array of adjacency lists /

public:

graph(int v) {this v-> v; adj=new list<int>[v];}

~graph() {delete [] adj: }

void add edge(int v, int w);

void greedy coloring();

};

void graph ::addedge (int v,int w)

{

adj[v].push-back(w);

adj[v].push=back(v);

}

void graph :: greedycoloring()

{

int result[v];

result[0]=0;

for(u=1; u<v; u++)

result[u]= -1;

/ no colour is assigned to u /

bool available[v];

for (cr=0; cr<v; cr++)

available[cr] =false;

for (u=1;u<v;u++)

{

list<int> :: iterator i;

for (i=adj[u].begin(); i != adj[u].end(); ++i)

if (result[*i} != -1)

available[result[*i]] = true;

int cr;

for (cr=0; cr<v; cr++)

if (available[cr] == false)

break;

result[u] = cr;

for (i = adj[u] . begin(); i != adj[u].end(); ++i)

if(result[*i] != -1)

available [result[*i]] = false;

}

for ( int u=0; u<v; u++)

cout << \"vertex\" << u << \"----> color\"

<< result[u] << end1;

}

2) Example program to show how the heuristic works:

This example is used to show hoew the functions in the above function of the heuristic works:

Example:

int main()

{

Graph g1(5);

g1.addedge(0,1);

g1.addedge(0,2);

g1.addedge(1,2);

g1.addedge(1,3);

g1.addedge(2,3);

g1.addedge(3,4);

cout << \"coloring of graph 1 \ \";

g1.greedycoloring();

Graph g2(5);

g2.addedge(0,1);

g2.addedge(0,2);

g2.addedge(1,2);

g2.addedge(1,4);

g2.addedge(2,4);

g2.addedge(4,3);

cout < \"\ coloring of graph 2 \ \";

g2.greedycoloring();

return 0;

}

3) Example where the heuristic fails to find an optimal solution:

In the above example if we do not assign the vertex with the proper colour as mentioned in the code then it will fail to find an optimal solution.