C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected - Computer Programming

Latest

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

Tuesday, September 26, 2017

C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected

Write a C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected

Program:
#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); // function 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
}

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 << "\nBridges in first graph \n";
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 << "\nBridges in second graph \n";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.bridge();

cout << "\nBridges in third graph \n";
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;
}

Output:
Bridges in first graph


3 4

No comments:

Post a Comment