Advanced-Analysis-and-Design-of-Algorithms/VertexCoverProblem.cpp at master · GiridharaSPK/Advanced-Analysis-and-Design-of-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#define N 4

using namespace std;

void VertexCoverProblem(int Adj[N][N])
{
  bool visited[N];
  for (int i=0; i<N; i++)
      visited[i] = false;

  for (int u=0; u<N; u++)
  {
    if (visited[u] == false)
    {
      for (int i= 0; Adj[u][i] == 1 && i<N; ++i)
      {
        int v = i;
        if (visited[v] == false)
        {
         visited[v] = true;
         visited[u]  = true;
         break;
        }
      }
    }
  }
  for (int i=0; i<N; i++)
      if (visited[i])
        cout << i << " ";
}

int main()
{
//  int Adj[N][N] = { {0,1,1,0,0,0,0},
//              {0,0,0,1,0,0,0},
//              {0,0,0,0,0,0,0},
//              {0,0,0,0,1,0,0},
//              {0,0,0,0,1,0,0},
//              {0,0,0,0,0,1,0},
//              {0,0,0,0,0,0,0}
//            };

	int Adj[N][N]=	{	{0,1,1,1},
						{1,0,1,0},
						{0,1,0,1},
						{1,0,1,0}
					};

  VertexCoverProblem(Adj);
}