Graph Cutpoints C++ complete empty functions dfs(), connected(), and get_cutpoints()

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

Graph.h

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

#ifndef GRPH

#define GRPH

#include

#include

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 &visited);

vector get_cutpoints();

private:

int size;

vector adjList;

};

#endif

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

Graph.cpp

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

#include

#include "graph.h"

#include

#include

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;

}

}

}

//returns the first index i where b[i] == false

// if no such vertex exists, returns b.size()

int firstFalse(vector b)

{

int i = 0;

while(i < b.size() && b[i])

i += 1;

return i;

}

// returns true if all entries in b are true

bool all(vector b)

{

for(int i = 0; i < b.size(); ++i)

if(!b[i])

return false;

return true;

}

void graph::dfs(vector &visited)

{

int start = firstFalse(visited);

int nbr, current = start;

stack S;

vnodeptr cursor;

visited[start] = true;

S.push(start);

// Supply the remaining code below

}

// if excluded is -1, return true if G is connected

// otherwise, return true if G-excluded is connected

bool graph::connected(int excluded = -1)

{

vector visited(size,false);

if(excluded != -1)

visited[excluded] = true;

// Supply the remaining code below

}

vector graph::get_cutpoints()

{

vector cutpts;

// Supply the remaining code below

}

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

cut_tester.cpp

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

#include

#include "graph.h"

using namespace std;

int main()

{

graph G;

if(!G.connected(-1)) {

cout << "Graph is not connected; terminating" << endl;

return 1;

}

vector 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;

}