Given vertex v of graph G = (V,E), we define G-v = (V-{v},E\'),where E\'= { e E
ID: 3818361 • Letter: G
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
// graph.h
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);
// if excluded is -1, return true if G is connected otherwise, return true if G-excluded is connected
vector<int> get_cutpoints();
private:
void dfs(vector<bool> &visited);
int size;
vector<vnodeptr> adjList;};
//graph.cpp
#include <iostream>#include <cassert>#include "graph.h"using namespace std;
mazegraph::graph(){int j;cin >> size;adjList.resize(size,NULL);for(int i = 0; i < size; ++i) {
cin >> j;while(0 <= j && j < size) {adjList[i] = new Node(j,adjList[i]);cin >> j;}}}
int firstFalse(vector<bool> b)
// returns the first index i where b[i] == false// if no such vertex exists, returns b.size()
{int i = 0;while(i < b.size() && b[i])
i += 1;return i;}
bool all(vector<bool> b)
// returns true if all entries in b are true
{for(int i = 0; i < b.size(); ++i)
if(!b[i])return false;return true;}
bool graph::connected(int excluded = -1){vector<bool> visited(size,false);if(excluded != -1)
visited[excluded] = true;
// Supply missing code below
bool graph::connected(int excluded = -1){vector<bool> visited(size,false);if(excluded != -1)
visited[excluded] = true;
// Supply missing code below
}
vector<int> graph::get_cutpoints(){vector<int> cutpts;
// Supply missing code below
}
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 missing code below
}
Explanation / Answer
// A C++ program to find bridges in a given undirected graph
#include<iostream>
#include <list>
#define NIL -1
using namespace std;
// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
void bridgeUtil(int v, bool visited[], int disc[], int low[],
int parent[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
void bridge(); // prints all bridges
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); // Note: the graph is undirected
}
// A recursive function that finds and prints bridges using
// DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
void Graph::bridgeUtil(int u, bool visited[], int disc[],
int low[], int parent[])
{
// A static variable is used for simplicity, we can
// avoid use of static variable by passing a pointer.
static int time = 0;
// Mark the current node as visited
visited[u] = true;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// Go through all vertices aadjacent to this
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i; // v is current adjacent of u
// If v is not visited yet, then recur for it
if (!visited[v])
{
parent[v] = u;
bridgeUtil(v, visited, disc, low, parent);
// Check if the subtree rooted with v has a
// connection to one of the ancestors of u
low[u] = min(low[u], low[v]);
// If the lowest vertex reachable from subtree
// under v is below u in DFS tree, then u-v
// is a bridge
if (low[v] > disc[u])
cout << u <<" " << v << endl;
}
// Update low value of u for parent function calls.
else if (v != parent[u])
low[u] = min(low[u], disc[v]);
}
}
// DFS based function to find all bridges. It uses recursive
// function bridgeUtil()
void Graph::bridge()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
int *disc = new int[V];
int *low = new int[V];
int *parent = new int[V];
// Initialize parent and visited arrays
for (int i = 0; i < V; i++)
{
parent[i] = NIL;
visited[i] = false;
}
// Call the recursive helper function to find Bridges
// in DFS tree rooted with vertex 'i'
for (int i = 0; i < V; i++)
if (visited[i] == false)
bridgeUtil(i, visited, disc, low, parent);
}
// Driver program to test above function
int main()
{
// Create graphs given in above diagrams
cout << " Bridges in first graph ";
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
g1.bridge();
cout << " Bridges in second graph ";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.bridge();
cout << " Bridges in third graph ";
Graph g3(7);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.addEdge(2, 0);
g3.addEdge(1, 3);
g3.addEdge(1, 4);
g3.addEdge(1, 6);
g3.addEdge(3, 5);
g3.addEdge(4, 5);
g3.bridge();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.