Posted on by Kalkicode
Code Graph

# Check if removing a given edge disconnects a graph

The problem you're addressing is about determining whether removing a given edge from a graph will cause the graph to become disconnected. A disconnected graph is one where there is no path between at least two vertices. Your goal is to create a program that checks whether removing a specific edge disconnects the graph.

## Problem Statement and Example

Given a graph with vertices and edges, you need to determine if removing a particular edge will result in the graph becoming disconnected. For example, consider the following graph:

``````Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Edges: (0,1), (0,3), (0,4), (1,2), (1,5), (2,3), (2,6), (3,4), (3,9), (6,7), (6,8), (9,10), (9,11), (10,11)``````

You're required to check whether removing a specific edge disconnects the graph. The program should print whether removing the edge will result in the graph being disconnected or not.

## Idea to Solve

To solve this problem, you need to perform a Depth-First Search (DFS) to traverse the graph and determine if all vertices can still be visited after removing the given edge. You can do this by temporarily removing the edge, checking if the graph remains connected, and then adding the edge back.

## Pseudocode

``````function dfs(visited, start)
mark start as visited
for each neighbor of start
if neighbor is not visited
dfs(visited, neighbor)

function removeNodeEdge(u, v)
if edge (u, v) doesn't exist
return false
remove edge (u, v)
remove edge (v, u)
return true

function disconnectByEdge(u, v)
initialize visited array
mark all vertices as not visited
perform dfs(visited, 0)
if all vertices are visited
if removeNodeEdge(u, v) is true
perform dfs(visited, 0)
if all vertices are visited
print "Remove edge [u-v] not disconnecting this graph"
else
print "Remove edge [u-v] disconnecting this graph"
else
print "No edge between vertices [u-v]"
else

## Algorithm Explanation

1. The `dfs` function marks vertices as visited using Depth-First Search.
2. The `removeNodeEdge` function removes a given edge between vertices `u` and `v`.
3. The `disconnectByEdge` function performs the following steps:
• Initialize the visited array.
• Perform DFS starting from vertex 0.
• If all vertices are visited, check if removing the edge (u, v) disconnects the graph.
• If removing the edge disconnects the graph, print accordingly.
• If removing the edge doesn't disconnect the graph, add the edge back and print accordingly.
• If some vertices are not visited, print "Graph is already disconnected".

## Code Solution

``````import java.util.ArrayList;
/*
Java Program
Check if removing a given edge disconnects a graph
*/
public class Graph
{
// Number of vertices in graph
public int vertices;
// Use to collect edges information
public ArrayList < ArrayList < Integer >> adjacencylist;
public Graph(int vertices)
{
this.vertices = vertices;
this.adjacencylist = new ArrayList < ArrayList < Integer >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
System.out.print(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adjacencylist.get(i).size(); j++)
{
}
}
}
public void dfs(boolean[] visited, int start)
{
if (start < 0 || start >= this.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;

int i = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i++;
}
}

public int edgePosition(int u, int v)
{

int i = 0;
{
{
return i;
}
i++;
}
return -1;
}

public boolean removeNodeEdge(int u, int v)
{

if(u < 0 || v < 0 || u > this.vertices
|| v > this.vertices )
{
return false;
}
int a = edgePosition(u,v);
int b = edgePosition(v,u);

if(a==-1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges

return true;

}
public void unsetVisit(boolean[] visited)
{
for (int i = 0; i < this.vertices; ++i)
{
visited[i] = false;
}
}
public boolean isAllVerticesVisit(boolean[] visited)
{
for (int i = 0; i < this.vertices; ++i)
{
if(visited[i]==false)
{
return false;
}
}
return true;
}
public void disconnectByEdge(int u, int v)
{

boolean[] visited = new boolean[this.vertices];

unsetVisit(visited);

dfs(visited, 0);

if(isAllVerticesVisit(visited)==true)
{

if(removeNodeEdge(u,v)==true)
{

unsetVisit(visited);

dfs(visited, 0);

if(isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect

System.out.print("\n Remove edge ["+u+"-"+v+"] not disconnecting this graph ");
}
else
{

System.out.print("\n Remove edge ["+u+"-"+v+"] disconnecting this graph ");
}

}
else
{
// When edges are not exist
System.out.print("\n No edge between vertices ["+u+"-"+v+"]");
}
}
else
{
// When graph is already disconnected?
}

}
public static void main(String[] args)
{
Graph graph = new Graph(12);
// Display graph element
graph.printGraph();

// Test case
graph.disconnectByEdge(4,7);
graph.disconnectByEdge(3,9);
graph.disconnectByEdge(1,2);
graph.disconnectByEdge(6,2);
graph.disconnectByEdge(10,11);

}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````// Include header file
#include <iostream>
#include <vector>

using namespace std;
/*
C++ Program
Check if removing a given edge disconnects a graph
*/
class Graph
{
public:
// Number of vertices in graph
int vertices;
// Use to collect edges information
vector < vector < int > > adjacencylist;
Graph(int vertices)
{
this->vertices = vertices;
for (int i = 0; i < this->vertices; ++i)
{
this->adjacencylist.push_back( vector < int > ());
}
}
{
if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
{
return;
}
}
// Display graph nodes and edges
void printGraph()
{
cout << "\n Graph Adjacency List ";
for (int i = 0; i < this->vertices; ++i)
{
cout << " \n [" << i << "] :";
// iterate edges of i node
for (int j = 0; j < this->adjacencylist.at(i).size(); j++)
{
cout << "  " << this->adjacencylist.at(i).at(j);
}
}
}
void dfs(bool visited[], int start)
{
if (start < 0 || start >= this->vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;
int i = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i++;
}
}
int edgePosition(int u, int v)
{
int i = 0;
{
{
return i;
}
i++;
}
return -1;
}
bool removeNodeEdge(int u, int v)
{
if (u < 0 || v < 0 || u > this->vertices || v > this->vertices)
{
return false;
}
int a = this->edgePosition(u, v);
int b = this->edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
void unsetVisit(bool visited[])
{
for (int i = 0; i < this->vertices; ++i)
{
visited[i] = false;
}
}
bool isAllVerticesVisit(bool visited[])
{
for (int i = 0; i < this->vertices; ++i)
{
if (visited[i] == false)
{
return false;
}
}
return true;
}
void disconnectByEdge(int u, int v)
{
bool visited[this->vertices];
this->unsetVisit(visited);
this->dfs(visited, 0);
if (this->isAllVerticesVisit(visited) == true)
{
if (this->removeNodeEdge(u, v) == true)
{
this->unsetVisit(visited);
this->dfs(visited, 0);
if (this->isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
cout << "\n Remove edge [" << u << "-"
<< v << "] not disconnecting this graph ";
}
else
{
cout << "\n Remove edge [" << u << "-"
<< v << "] disconnecting this graph ";
}
}
else
{
// When edges are not exist
cout << "\n No edge between vertices [" << u << "-"
<< v << "]";
}
}
else
{
// When graph is already disconnected?
cout << "\n Graph is already disconnected";
}
}
};
int main()
{
Graph *graph = new Graph(12);
// Display graph element
graph->printGraph();
// Test case
graph->disconnectByEdge(4, 7);
graph->disconnectByEdge(3, 9);
graph->disconnectByEdge(1, 2);
graph->disconnectByEdge(6, 2);
graph->disconnectByEdge(10, 11);
return 0;
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Check if removing a given edge disconnects a graph
*/
public class Graph
{
// Number of vertices in graph
public int vertices;
// Use to collect edges information
public List < List < int >> adjacencylist;
public Graph(int vertices)
{
this.vertices = vertices;
this.adjacencylist = new List < List < int >> (vertices);
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
Console.Write(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adjacencylist[i].Count; j++)
{
}
}
}
public void dfs(Boolean[] visited, int start)
{
if (start < 0 || start >= this.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;
int i = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i++;
}
}
public int edgePosition(int u, int v)
{
int i = 0;
{
{
return i;
}
i++;
}
return -1;
}
public Boolean removeNodeEdge(int u, int v)
{
if (u < 0 || v < 0 || u > this.vertices || v > this.vertices)
{
return false;
}
int a = this.edgePosition(u, v);
int b = this.edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
public void unsetVisit(Boolean[] visited)
{
for (int i = 0; i < this.vertices; ++i)
{
visited[i] = false;
}
}
public Boolean isAllVerticesVisit(Boolean[] visited)
{
for (int i = 0; i < this.vertices; ++i)
{
if (visited[i] == false)
{
return false;
}
}
return true;
}
public void disconnectByEdge(int u, int v)
{
Boolean[] visited = new Boolean[this.vertices];
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited) == true)
{
if (this.removeNodeEdge(u, v) == true)
{
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
Console.Write("\n Remove edge [" + u + "-" +
v + "] not disconnecting this graph ");
}
else
{
Console.Write("\n Remove edge [" + u + "-" +
v + "] disconnecting this graph ");
}
}
else
{
// When edges are not exist
Console.Write("\n No edge between vertices [" + u +
"-" + v + "]");
}
}
else
{
// When graph is already disconnected?
}
}
public static void Main(String[] args)
{
Graph graph = new Graph(12);
// Display graph element
graph.printGraph();
// Test case
graph.disconnectByEdge(4, 7);
graph.disconnectByEdge(3, 9);
graph.disconnectByEdge(1, 2);
graph.disconnectByEdge(6, 2);
graph.disconnectByEdge(10, 11);
}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````package main
import "fmt"
/*
Go Program
Check if removing a given edge disconnects a graph
*/
type Graph struct {
// Number of vertices in graph
vertices int
// Use to collect edges information
}
func getGraph(vertices int) * Graph {
var me *Graph = &Graph {}
me.vertices = vertices

return me
}
func(this Graph) addEdge(u, v int) {
if u < 0 || u >= this.vertices || v < 0 || v >= this.vertices {
return
}
}
// Display graph nodes and edges
func(this Graph) printGraph() {
for i := 0 ; i < this.vertices ; i++ {
fmt.Print(" \n [", i, "] :")
// iterate edges of i node
for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
}
}
}
func(this Graph) dfs(visited[] bool, start int) {
if start < 0 || start >= this.vertices {
// In case given invalid node
return
}
// Mark a current visited node
visited[start] = true
var i int = 0
// Execute edges of given start vertices
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i++
}
}
func(this Graph) edgePosition(u, v int) int {
var i int = 0
return i
}
i++
}
return -1
}
func(this Graph) removeNodeEdge(u, v int) bool {
if u < 0 || v < 0 || u > this.vertices || v > this.vertices {
return false
}
var a int = this.edgePosition(u, v)
var b int = this.edgePosition(v, u)
if a == -1 || b == -1 {
// Given edge are not exist between given nodes
return false
}
// Remove edges

return true
}
func(this Graph) unsetVisit(visited[] bool) {
for i := 0 ; i < this.vertices ; i++ {
visited[i] = false
}
}
func(this Graph) isAllVerticesVisit(visited[] bool) bool {
for i := 0 ; i < this.vertices ; i++ {
if visited[i] == false {
return false
}
}
return true
}
func(this Graph) disconnectByEdge(u, v int) {
var visited = make([]bool,this.vertices)
this.unsetVisit(visited)
this.dfs(visited, 0)
if this.isAllVerticesVisit(visited) == true {
if this.removeNodeEdge(u, v) == true {
this.unsetVisit(visited)
this.dfs(visited, 0)
if this.isAllVerticesVisit(visited) {
// not a bridge edge
// graph are not disconnect
fmt.Print("\n Remove edge [", u, "-", v, "] not disconnecting this graph ")
} else {
fmt.Print("\n Remove edge [", u, "-", v, "] disconnecting this graph ")
}
} else {
// When edges are not exist
fmt.Print("\n No edge between vertices [", u, "-", v, "]")
}
} else {
// When graph is already disconnected?
}
}
func main() {
var graph * Graph = getGraph(12)
// Display graph element
graph.printGraph()
// Test case
graph.disconnectByEdge(4, 7)
graph.disconnectByEdge(3, 9)
graph.disconnectByEdge(1, 2)
graph.disconnectByEdge(6, 2)
graph.disconnectByEdge(10, 11)
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````<?php
/*
Php Program
Check if removing a given edge disconnects a graph
*/
class Graph
{
// Number of vertices in graph
public \$vertices;
// Use to collect edges information
public	function __construct(\$vertices)
{
\$this->vertices = \$vertices;
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
}
}
{
if (\$u < 0 || \$u >= \$this->vertices ||
\$v < 0 || \$v >= \$this->vertices)
{
return;
}
}
// Display graph nodes and edges
public	function printGraph()
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
echo(" \n [".\$i.
"] :");
// iterate edges of i node
for (\$j = 0; \$j < count(\$this->adjacencylist[\$i]); \$j++)
{
}
}
}
public	function dfs(&\$visited, \$start)
{
if (\$start < 0 || \$start >= \$this->vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
\$visited[\$start] = true;
\$i = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
\$i++;
}
}
public	function edgePosition(\$u, \$v)
{
\$i = 0;
{
{
return \$i;
}
\$i++;
}
return -1;
}
public	function removeNodeEdge(\$u, \$v)
{
if (\$u < 0 || \$v < 0 ||
\$u > \$this->vertices || \$v > \$this->vertices)
{
return false;
}
\$a = \$this->edgePosition(\$u, \$v);
\$b = \$this->edgePosition(\$v, \$u);
if (\$a == -1 || \$b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
public	function unsetVisit(&\$visited)
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
\$visited[\$i] = false;
}
}
public	function isAllVerticesVisit(\$visited)
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
if (\$visited[\$i] == false)
{
return false;
}
}
return true;
}
public	function disconnectByEdge(\$u, \$v)
{
\$visited = array_fill(0, \$this->vertices, false);
\$this->unsetVisit(\$visited);
\$this->dfs(\$visited, 0);
if (\$this->isAllVerticesVisit(\$visited) == true)
{
if (\$this->removeNodeEdge(\$u, \$v) == true)
{
\$this->unsetVisit(\$visited);
\$this->dfs(\$visited, 0);
if (\$this->isAllVerticesVisit(\$visited))
{
// not a bridge edge
// graph are not disconnect
echo("\n Remove edge [".\$u.
"-".\$v.
"] not disconnecting this graph ");
}
else
{
echo("\n Remove edge [".\$u.
"-".\$v.
"] disconnecting this graph ");
}
}
else
{
// When edges are not exist
echo("\n No edge between vertices [".\$u.
"-".\$v.
"]");
}
}
else
{
// When graph is already disconnected?
}
}
}

function main()
{
\$graph = new Graph(12);
// Display graph element
\$graph->printGraph();
// Test case
\$graph->disconnectByEdge(4, 7);
\$graph->disconnectByEdge(3, 9);
\$graph->disconnectByEdge(1, 2);
\$graph->disconnectByEdge(6, 2);
\$graph->disconnectByEdge(10, 11);
}
main();``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````/*
Node JS Program
Check if removing a given edge disconnects a graph
*/
class Graph
{
constructor(vertices)
{
this.vertices = vertices;
for (var i = 0; i < this.vertices; ++i)
{
}
}
{
if (u < 0 || u >= this.vertices ||
v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
printGraph()
{
for (var i = 0; i < this.vertices; ++i)
{
process.stdout.write(" \n [" + i + "] :");
// iterate edges of i node
for (var j = 0; j < this.adjacencylist[i].length; j++)
{
}
}
}
dfs(visited, start)
{
if (start < 0 || start >= this.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;
var i = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i++;
}
}
edgePosition(u, v)
{
var i = 0;
{
{
return i;
}
i++;
}
return -1;
}
removeNodeEdge(u, v)
{
if (u < 0 || v < 0 ||
u > this.vertices || v > this.vertices)
{
return false;
}
var a = this.edgePosition(u, v);
var b = this.edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
unsetVisit(visited)
{
for (var i = 0; i < this.vertices; ++i)
{
visited[i] = false;
}
}
isAllVerticesVisit(visited)
{
for (var i = 0; i < this.vertices; ++i)
{
if (visited[i] == false)
{
return false;
}
}
return true;
}
disconnectByEdge(u, v)
{
var visited = Array(this.vertices).fill(false);
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited) == true)
{
if (this.removeNodeEdge(u, v) == true)
{
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
process.stdout.write("\n Remove edge [" +
u + "-" + v + "] not disconnecting this graph ");
}
else
{
process.stdout.write("\n Remove edge [" +
u + "-" + v + "] disconnecting this graph ");
}
}
else
{
// When edges are not exist
process.stdout.write("\n No edge between vertices [" +
u + "-" + v + "]");
}
}
else
{
// When graph is already disconnected?
}
}
}

function main()
{
var graph = new Graph(12);
// Display graph element
graph.printGraph();
// Test case
graph.disconnectByEdge(4, 7);
graph.disconnectByEdge(3, 9);
graph.disconnectByEdge(1, 2);
graph.disconnectByEdge(6, 2);
graph.disconnectByEdge(10, 11);
}
main();``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````#    Python 3 Program
#    Check if removing a given edge disconnects a graph
class Graph :
#  Number of vertices in graph
#  Use to collect edges information
def __init__(self, vertices) :
self.vertices = vertices
i = 0
while (i < self.vertices) :
i += 1

if (u < 0 or u >= self.vertices or
v < 0 or v >= self.vertices) :
return

#  Display graph nodes and edges
def printGraph(self) :
print("\n Graph Adjacency List ", end = "")
i = 0
while (i < self.vertices) :
print(" \n [", i ,"] :", end = "")
j = 0
#  iterate edges of i node
print("  ", self.adjacencylist[i][j], end = "")
j += 1

i += 1

def dfs(self, visited, start) :
if (start < 0 or start >= self.vertices) :
#  In case given invalid node
return

#  Mark a current visited node
visited[start] = True
i = 0
#  Execute edges of given start vertices
#  When edge node not visiting, then perform DFS operation

#  Visit to next node
i += 1

def edgePosition(self, u, v) :
i = 0
return i

i += 1

return -1

def removeNodeEdge(self, u, v) :
if (u < 0 or v < 0 or u > self.vertices or v > self.vertices) :
return False

a = self.edgePosition(u, v)
b = self.edgePosition(v, u)
if (a == -1 or b == -1) :
#  Given edge are not exist between given nodes
return False

#  Remove edges
return True

def unsetVisit(self, visited) :
i = 0
while (i < self.vertices) :
visited[i] = False
i += 1

def isAllVerticesVisit(self, visited) :
i = 0
while (i < self.vertices) :
if (visited[i] == False) :
return False

i += 1

return True

def disconnectByEdge(self, u, v) :
visited = [False] * (self.vertices)
self.unsetVisit(visited)
self.dfs(visited, 0)
if (self.isAllVerticesVisit(visited) == True) :
if (self.removeNodeEdge(u, v) == True) :
self.unsetVisit(visited)
self.dfs(visited, 0)
if (self.isAllVerticesVisit(visited)) :
#  not a bridge edge
#  graph are not disconnect
print("\n Remove edge [", u ,
"-", v ,"] not disconnecting this graph ", end = "")
else :
print("\n Remove edge [",
u ,"-", v ,"] disconnecting this graph ", end = "")

else :
#  When edges are not exist
print("\n No edge between vertices [",
u ,"-", v ,"]", end = "")

else :
#  When graph is already disconnected?
print("\n Graph is already disconnected", end = "")

def main() :
graph = Graph(12)
#  Display graph element
graph.printGraph()
#  Test case
graph.disconnectByEdge(4, 7)
graph.disconnectByEdge(3, 9)
graph.disconnectByEdge(1, 2)
graph.disconnectByEdge(6, 2)
graph.disconnectByEdge(10, 11)

if __name__ == "__main__": main()``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   3   4
[ 1 ] :   0   2   5
[ 2 ] :   1   3   6
[ 3 ] :   0   2   4   9
[ 4 ] :   0   3
[ 5 ] :   1
[ 6 ] :   2   7   8
[ 7 ] :   6
[ 8 ] :   6
[ 9 ] :   3   10   11
[ 10 ] :   9   11
[ 11 ] :   9   10
No edge between vertices [ 4 - 7 ]
Remove edge [ 3 - 9 ] disconnecting this graph
Remove edge [ 1 - 2 ] not disconnecting this graph
Remove edge [ 6 - 2 ] disconnecting this graph
Remove edge [ 10 - 11 ] not disconnecting this graph``````
``````#    Ruby Program
#    Check if removing a given edge disconnects a graph
class Graph
# Define the accessor and reader of class Graph
#  Number of vertices in graph
#  Use to collect edges information
def initialize(vertices)
self.vertices = vertices
i = 0
while (i < self.vertices)
i += 1
end

end

if (u < 0 || u >= self.vertices ||
v < 0 || v >= self.vertices)
return
end

end

#  Display graph nodes and edges
def printGraph()
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
#  iterate edges of i node
j += 1
end

i += 1
end

end

def dfs(visited, start)
if (start < 0 || start >= self.vertices)
#  In case given invalid node
return
end

#  Mark a current visited node
visited[start] = true
i = 0
#  Execute edges of given start vertices
#  When edge node not visiting, then perform DFS operation
end

#  Visit to next node
i += 1
end

end

def edgePosition(u, v)
i = 0
return i
end

i += 1
end

return -1
end

def removeNodeEdge(u, v)
if (u < 0 || v < 0 ||
u > self.vertices || v > self.vertices)
return false
end

a = self.edgePosition(u, v)
b = self.edgePosition(v, u)
if (a == -1 || b == -1)
#  Given edge are not exist between given nodes
return false
end

#  Remove edges
return true
end

def unsetVisit(visited)
i = 0
while (i < self.vertices)
visited[i] = false
i += 1
end

end

def isAllVerticesVisit(visited)
i = 0
while (i < self.vertices)
if (visited[i] == false)
return false
end

i += 1
end

return true
end

def disconnectByEdge(u, v)
visited = Array.new(self.vertices) {false}
self.unsetVisit(visited)
self.dfs(visited, 0)
if (self.isAllVerticesVisit(visited) == true)
if (self.removeNodeEdge(u, v) == true)
self.unsetVisit(visited)
self.dfs(visited, 0)
if (self.isAllVerticesVisit(visited))
#  not a bridge edge
#  graph are not disconnect
print("\n Remove edge [",
u ,"-", v ,"] not disconnecting this graph ")
else

print("\n Remove edge [",
u ,"-", v ,"] disconnecting this graph ")
end

else

#  When edges are not exist
print("\n No edge between vertices [",
u ,"-", v ,"]")
end

else

#  When graph is already disconnected?
end

end

end

def main()
graph = Graph.new(12)
#  Display graph element
graph.printGraph()
#  Test case
graph.disconnectByEdge(4, 7)
graph.disconnectByEdge(3, 9)
graph.disconnectByEdge(1, 2)
graph.disconnectByEdge(6, 2)
graph.disconnectByEdge(10, 11)
end

main()``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph ``````
``````import scala.collection.mutable._;
/*
Scala Program
Check if removing a given edge disconnects a graph
*/
class Graph(
// Number of vertices in graph
var vertices: Int,
// Use to collect edges information
{
def this(vertices: Int)
{
this(vertices,new ArrayBuffer[ArrayBuffer[Int]](vertices));
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
def addEdge(u: Int, v: Int): Unit = {
if (u < 0 || u >= this.vertices ||
v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
def printGraph(): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
def dfs(visited: Array[Boolean], start: Int): Unit = {
if (start < 0 || start >= this.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited(start) = true;
var i: Int = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i += 1;
}
}
def edgePosition(u: Int, v: Int): Int = {
var i: Int = 0;
{
{
return i;
}
i += 1;
}
return -1;
}
def removeNodeEdge(u: Int, v: Int): Boolean = {
if (u < 0 || v < 0 || u > this.vertices || v > this.vertices)
{
return false;
}
var a: Int = edgePosition(u, v);
var b: Int = edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
def unsetVisit(visited: Array[Boolean]): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
visited(i) = false;
i += 1;
}
}
def isAllVerticesVisit(visited: Array[Boolean]): Boolean = {
var i: Int = 0;
while (i < this.vertices)
{
if (visited(i) == false)
{
return false;
}
i += 1;
}
return true;
}
def disconnectByEdge(u: Int, v: Int): Unit = {
var visited: Array[Boolean] =
Array.fill[Boolean](this.vertices)(false);
unsetVisit(visited);
dfs(visited, 0);
if (isAllVerticesVisit(visited) == true)
{
if (removeNodeEdge(u, v) == true)
{
unsetVisit(visited);
dfs(visited, 0);
if (isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
print("\n Remove edge [" + u +
"-" + v + "] not disconnecting this graph ");
}
else
{
print("\n Remove edge [" + u +
"-" + v + "] disconnecting this graph ");
}
}
else
{
// When edges are not exist
print("\n No edge between vertices [" +
u + "-" + v + "]");
}
}
else
{
// When graph is already disconnected?
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var graph: Graph = new Graph(12);
// Display graph element
graph.printGraph();
// Test case
graph.disconnectByEdge(4, 7);
graph.disconnectByEdge(3, 9);
graph.disconnectByEdge(1, 2);
graph.disconnectByEdge(6, 2);
graph.disconnectByEdge(10, 11);
}
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````
``````import Foundation;
/*
Swift 4 Program
Check if removing a given edge disconnects a graph
*/
class Graph
{
// Number of vertices in graph
var vertices: Int;
// Use to collect edges information
init(_ vertices: Int)
{
self.vertices = vertices;
var i: Int = 0;
while (i < self.vertices)
{
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int)
{
if (u < 0 || u >= self.vertices ||
v < 0 || v >= self.vertices)
{
return;
}
}
// Display graph nodes and edges
func printGraph()
{
print("\n Graph Adjacency List ", terminator: "");
var i: Int = 0;
while (i < self.vertices)
{
print(" \n [", i ,"] :", terminator: "");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
func dfs(_ visited: inout[Bool], _ start: Int)
{
if (start < 0 || start >= self.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;
var i: Int = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i += 1;
}
}
func edgePosition(_ u: Int, _ v: Int) -> Int
{
var i: Int = 0;
{
{
return i;
}
i += 1;
}
return -1;
}
func removeNodeEdge(_ u: Int, _ v: Int) -> Bool
{
if (u < 0 || v < 0 || u > self.vertices || v > self.vertices)
{
return false;
}
let a: Int = self.edgePosition(u, v);
let b: Int = self.edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
func unsetVisit(_ visited: inout[Bool])
{
var i: Int = 0;
while (i < self.vertices)
{
visited[i] = false;
i += 1;
}
}
func isAllVerticesVisit(_ visited: [Bool]) -> Bool
{
var i: Int = 0;
while (i < self.vertices)
{
if (visited[i] == false)
{
return false;
}
i += 1;
}
return true;
}
func disconnectByEdge(_ u: Int, _ v: Int)
{
var visited: [Bool] = Array(repeating: false, count: self.vertices);
self.dfs(&visited, 0);
if (self.isAllVerticesVisit(visited) == true)
{
if (self.removeNodeEdge(u, v) == true)
{
self.unsetVisit(&visited);
self.dfs(&visited, 0);
if (self.isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
print("\n Remove edge [", u ,
"-", v ,"] not disconnecting this graph ",
terminator: "");
}
else
{
print("\n Remove edge [",
u ,"-", v ,"] disconnecting this graph ",
terminator: "");
}
}
else
{
// When edges are not exist
print("\n No edge between vertices [",
u ,"-", v ,"]", terminator: "");
}
}
else
{
// When graph is already disconnected?
print("\n Graph is already disconnected", terminator: "");
}
}
}
func main()
{
let graph: Graph = Graph(12);
// Display graph element
graph.printGraph();
// Test case
graph.disconnectByEdge(4, 7);
graph.disconnectByEdge(3, 9);
graph.disconnectByEdge(1, 2);
graph.disconnectByEdge(6, 2);
graph.disconnectByEdge(10, 11);
}
main();``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   3   4
[ 1 ] :   0   2   5
[ 2 ] :   1   3   6
[ 3 ] :   0   2   4   9
[ 4 ] :   0   3
[ 5 ] :   1
[ 6 ] :   2   7   8
[ 7 ] :   6
[ 8 ] :   6
[ 9 ] :   3   10   11
[ 10 ] :   9   11
[ 11 ] :   9   10
No edge between vertices [ 4 - 7 ]
Remove edge [ 3 - 9 ] disconnecting this graph
Remove edge [ 1 - 2 ] not disconnecting this graph
Remove edge [ 6 - 2 ] disconnecting this graph
Remove edge [ 10 - 11 ] not disconnecting this graph``````
``````/*
Kotlin Program
Check if removing a given edge disconnects a graph
*/
class Graph
{
// Number of vertices in graph
var vertices: Int;
// Use to collect edges information
var adjacencylist: MutableList < MutableList < Int >>;
constructor(vertices: Int)
{
this.vertices = vertices;
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
fun addEdge(u: Int, v: Int): Unit
{
if (u < 0 || u >= this.vertices ||
v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
fun printGraph(): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
fun dfs(visited: Array < Boolean > , start: Int): Unit
{
if (start < 0 || start >= this.vertices)
{
// In case given invalid node
return;
}
// Mark a current visited node
visited[start] = true;
var i: Int = 0;
// Execute edges of given start vertices
{
{
// When edge node not visiting, then perform DFS operation
}
// Visit to next node
i += 1;
}
}
fun edgePosition(u: Int, v: Int): Int
{
var i: Int = 0;
{
{
return i;
}
i += 1;
}
return -1;
}
fun removeNodeEdge(u: Int, v: Int): Boolean
{
if (u < 0 || v < 0 ||
u > this.vertices || v > this.vertices)
{
return false;
}
val a: Int = this.edgePosition(u, v);
val b: Int = this.edgePosition(v, u);
if (a == -1 || b == -1)
{
// Given edge are not exist between given nodes
return false;
}
// Remove edges
return true;
}
fun unsetVisit(visited: Array < Boolean > ): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
visited[i] = false;
i += 1;
}
}
fun isAllVerticesVisit(visited: Array < Boolean > ): Boolean
{
var i: Int = 0;
while (i < this.vertices)
{
if (visited[i] == false)
{
return false;
}
i += 1;
}
return true;
}
fun disconnectByEdge(u: Int, v: Int): Unit
{
val visited: Array < Boolean > = Array(this.vertices)
{
false
};
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited) == true)
{
if (this.removeNodeEdge(u, v) == true)
{
this.unsetVisit(visited);
this.dfs(visited, 0);
if (this.isAllVerticesVisit(visited))
{
// not a bridge edge
// graph are not disconnect
print("\n Remove edge [" + u +
"-" + v + "] not disconnecting this graph ");
}
else
{
print("\n Remove edge [" + u
+ "-" + v + "] disconnecting this graph ");
}
}
else
{
// When edges are not exist
print("\n No edge between vertices [" + u +
"-" + v + "]");
}
}
else
{
// When graph is already disconnected?
}
}
}
fun main(args: Array < String > ): Unit
{
val graph: Graph = Graph(12);
// Display graph element
graph.printGraph();
// Test case
graph.disconnectByEdge(4, 7);
graph.disconnectByEdge(3, 9);
graph.disconnectByEdge(1, 2);
graph.disconnectByEdge(6, 2);
graph.disconnectByEdge(10, 11);
}``````

#### input

`````` Graph Adjacency List
[0] :  1  3  4
[1] :  0  2  5
[2] :  1  3  6
[3] :  0  2  4  9
[4] :  0  3
[5] :  1
[6] :  2  7  8
[7] :  6
[8] :  6
[9] :  3  10  11
[10] :  9  11
[11] :  9  10
No edge between vertices [4-7]
Remove edge [3-9] disconnecting this graph
Remove edge [1-2] not disconnecting this graph
Remove edge [6-2] disconnecting this graph
Remove edge [10-11] not disconnecting this graph``````

## Resultant Output Explanation

It checks whether removing a given edge disconnects the graph and prints the results for the provided test cases.

## Time Complexity

The time complexity of the algorithm depends on the number of vertices and edges in the graph. The DFS traversal has a time complexity of O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The edge removal and addition operations have constant time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post