CODEWITHSUNDEEP
algorithmgraphcomputer-science
user2754673
user2754673

Reputation: 459

Strongly connected Graph

I have a strongly connected graph. I want to remove an edge and check if still remains strongly connected. As i'm taking N = Total number of nodes in the graph to be 10 and most of the graphs that i'm interested in has above 25 edges its hard to check using one at a time removing edge.

How to solve this problem ? Thanks.

Upvotes: 1

Views: 417

Answers (2)

j_random_hacker
j_random_hacker

Reputation: 51316

[EDIT: DFS is faster than Dijkstra for just checking connectivity, thanks to Jørgen Fogh]

If the edge you're removing is uv, check (e.g. using DFS) whether there remains a path u->...->v. If so, the graph is still strongly connected if it was before. If not, then it's clearly no longer strongly connected.

The idea is that any path between two vertices x and y that previously used the edge uv can be edited to use the new path u->...->v. Simply replacing the edge uv with this new path might cause some vertices to be visited more than once -- but in this case, the path contains one or more directed cycles which can be removed, until the remaining path visits each vertex at most once.

Upvotes: 1

whrow
whrow

Reputation: 206

If the edge you remove is (u -> v), the graph will remain connected if you can find a path from u to v. You can use any path finding algorithm to check this.

Another option is to run a connectivity check algorithm from scratch every time; it doesn't really matter how you do this because the graph is very small.

For a larger graph, there are special data structures that have been designed for this problem. It's called "Dynamic connectivity": https://en.wikipedia.org/wiki/Dynamic_connectivity

Upvotes: 6

Related Questions