Given vertex v of graph G = (V,E), we define G-v = (V-{v},E\'),where E\'= { e E

Question

Given vertex v of graph G = (V,E), we define G-v = (V-{v},E'),where E'= { e E | e is not incident with v }
That is, the graph we get by deleting v and all edges having v as an endpoint
Vertex v is said to be a cutpoint of connected graph G is G-v is not connected.
Our goal is to find all the cutpoints of a graphWe will do this via a class methodDepth-first search is the main tool we use, although BFS could
be used instead.

We will adapt depth-first search to determine if G-v is connected
We use a little trick to do thisA crucial data structure used is vector<bool> visited
Its obvious use is to mark vertices as visited during dfs
If, after dfs terminates, the graph is connected if and only ifall entries in visited are true.
But we simulate doing dfs on G-v, by initially setting visited[v] to true before starting the search
This means that v will never be used to reach another vertex

FILL THE MISSISNG CODE ONLY

//graph.h

#ifndef GRPH
#define GRPH
#include <iostream>
#include <vector>

using namespace std;

struct vnode {   
   int vertex;   
   vnode *next;   
   vnode(int u, vnode *n): vertex(u), next(n){};
};

typedef vnode * vnodeptr;

class graph {
   public:   
       graph(); // interactive constructor using cin   
       bool connected(int excluded);   
       void dfs(vector<bool> &visited);   
       vector<int> get_cutpoints();
   private:   
       int size;   
       vector<vnodeptr> adjList;
   };
#endif

-------------------------------------------------

//graph.cpp

#include "graph.h"
#ininclude <cassert>
#include <stack>
graph::graph()
{

int vertex;   
   cin >> size;   
   adjList.resize(size,NULL);   
   for(int i = 0; i < size; ++i) {   
       cin >> vertex;   
       while(vertex != -1) {
       adjList[i] = new vnode(vertex,adjList[i]); // insert at begining
       cin >> vertex;   
           }   
       }
   }
int firstFalse(vector<bool> b)
{   
   int i = 0;   
   while(i < b.size() && b[i])   
       i += 1;   
   return i;
}
bool all(vector<bool> b)
{   
   for(int i = 0; i < b.size(); ++i)   
   if(!b[i])   
       return false;   
       return true;
}
void graph::dfs(vector<bool> &visited)
{   
   int start = firstFalse(visited);   
   int nbr, current = start;   
   stack<int> S;   
   vnodeptr cursor;   
   visited[start] = true;   
   S.push(start);   
   // Supply the remaining code below
}
bool graph::connected(int excluded = -1)
{   
   vector<bool> visited(size,false);   
   if(excluded != -1)   
   visited[excluded] = true;
// Supply the remaining code below
}   

vector<int> graph::get_cutpoints()
{   
   vector<int> cutpts;   
   // Supply the remaining code below
  
}

----------------------

//cut_tester.cpp

#include "graph.h"
using namespace std;

int main()
{   
   graph G;   
   if(!G.connected(-1)) {   
   cout << "Graph is not connected; terminating" << endl;   
   return 1;   
}   
   vector<int> cutpoints = G.get_cutpoints();   
   cout << "Number of cutpoints: " << cutpoints.size() << endl;   
   cout << "Cutpoints: ";   
   for(int i = 0; i < cutpoints.size(); ++i)   
   cout << cutpoints[i] << " ";   
   cout << endl;
    return 0;
}

------------------------------

CHECK YOUR CODE WITH THIS:

cut_input

6
5 3 -1
4 2 -1
4 1 -1
5 0 -1
5 2 1 -1
4 3 0 -1

//cut_correct

Number of cutpoints: 2
Cutpoints: 4 5

Explanation / Answer

void graph::dfs(vector<bool> &visited)
{   
int start = firstFalse(visited);   
int nbr, current = start;   
stack<int> S;   
vnodeptr cursor;   
visited[start] = true;   
S.push(start);   
// Supply the remaining code below
  
while (!S.empty())
{
// Pop a vertex from stack and print it
start = S.top();
S.pop();

// Stack may contain same vertex twice. So
// we need to print the popped item only
// if it is not visited.
if (!visited[start])
{
cout << start << " ";
visited[start] = true;
}

// Get all adjacent vertices of the popped vertex s
// If a adjacent has not been visited, then puah it
// to the stack.
for (auto i = adj[start].begin(); i != adj[start].end(); ++i)
if (!visited[*i])
S.push(*i);
}
}

bool graph::connected(int excluded = -1)
{   
vector<bool> visited(size,false);   
if(excluded != -1)   
visited[excluded] = true;
// Supply the remaining code below

dfs(visited);
  
for (int i = 0; i < size; i++)
if (visited[i] == false)
return false;

return true;

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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