Last semester in an Algorithm class, I was given a question that goes like:
A graph G = (V, E) contains two verticies s and t (of course, these are not the only two). Assuming the graph is connected, there exists a path from s to t. Now, If there exists an edge along a path from s to t such that if it were deleted would disconnect s and t, devise a method for finding the edge.
If you are familiar with Depth-First Search and Breadth-First Search, you are able to use them. If not, maybe try to explain in your own words if you have a clue.
My answer to this question was to delete an edge, check s-t connectivity. If there still exists a path, replace the deleted edge and delete the next edge in the adjacency list. This of course was horribly inefficient, but its all I could find after 30 minutes of dead-end ideas. I did get partial credit, though :mrgreen:.
Thanks if you can help!
-Daon
A graph G = (V, E) contains two verticies s and t (of course, these are not the only two). Assuming the graph is connected, there exists a path from s to t. Now, If there exists an edge along a path from s to t such that if it were deleted would disconnect s and t, devise a method for finding the edge.
If you are familiar with Depth-First Search and Breadth-First Search, you are able to use them. If not, maybe try to explain in your own words if you have a clue.
My answer to this question was to delete an edge, check s-t connectivity. If there still exists a path, replace the deleted edge and delete the next edge in the adjacency list. This of course was horribly inefficient, but its all I could find after 30 minutes of dead-end ideas. I did get partial credit, though :mrgreen:.
Thanks if you can help!
-Daon