Determine if the value of any vertex in a graph is more than double the value of

Question

Determine if the value of any vertex in a graph is more than double the value of the adjacent vertex.

An absolute value function has been defined for you. You can pass an integer to this function and it will return the absolute value.

For ex: absolute(-6) = 6

Write a function which takes one parameter, which is the value of the starting vertex. The value of the vertex is an integer.

The function should print "Yes" if the value of any vertex is more than double the value of adjacent vertex. Otherwise it should print "No".

void Graph::findAdjacentWithDoubleValue(int startingNode);

The vertex structure includes a "visited" variable, set to false by default. You can use this variable in the findAdjacentWithDoubleValue function.

/////////////////////////////////////

adjVertex struct:

////////////////////////////////////

Vertex struct:

/////////////////////////////////

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

class Graph
{
int V;
list<int> *adj;

  
void DFSUtil(int v, vector<bool> &visited);
public:
Graph(int V);
void addEdge(int v, int w);
int findMother();
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::DFSUtil(int v, vector<bool> &visited)
{
  
visited[v] = true;


list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}

int Graph::findMother()
{
  
vector <bool> visited(V, false);

  
int v = 0;

  
for (int i = 0; i < V; i++)
{
if (visited[i] == false)
{
DFSUtil(i, visited);
v = i;
}
}

  
fill(visited.begin(), visited.end(), false);
DFSUtil(v, visited);
for (int i=0; i<V; i++)
if (visited[i] == false)
return -1;

return v;
}
int main()
{
  
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(4, 1);
g.addEdge(6, 4);
g.addEdge(5, 6);
g.addEdge(5, 2);
g.addEdge(6, 0);

cout << "A mother vertex is " << g.findMother();

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.