Skip to content

Made changes to the efficient bridge-finding algorithm #119

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 3 commits into from
May 31, 2016
Merged

Made changes to the efficient bridge-finding algorithm #119

merged 3 commits into from
May 31, 2016

Conversation

jonathanxia
Copy link
Contributor

This time only three files were changed. This is almost the same as pull request #92.

Changes to the efficient bridge-finding algorithm:

  1. Added a description of the algorithm
  2. Made some changes to the algorithm. Removed the visited[] and parent[] arrays, and used -1 to indicate non-visited.
  3. Also changed the algorithm a bit, so that when a cycle is hit, the DFS can directly change the values of low[]
  4. Also edited the tracing, defining a trace() function and then placing it after each visit (makes more sense that way).
  5. I changed the example graph in data.js. I thought it would be a bit more instructive to show that a bridge isn't necessarily incident to a vertex with degree 1, as was (kind of) suggested by the previous example.

@jonathanxia
Updated the desc.json file in bridges
61099e2 
Added a description of the efficient bridges algorithm in the desc.json
file.
@jonathanxia
Changed the efficient bridge-finding algorithm
e53fce7 
Got rid of the unnecessary visited and parent array to make it more
space efficient. I also used the idea that the low array is the lowest
numbered vertex that can be reached, so a depth first search can
initiate at a connected component by passing the vertex itself in as its
parent.
@jonathanxia
Changed the data.js file
0178af4 
I changed the graph; thought it was a bit more instructive to see that a
bridge isn't necessarily an edge that has degree 1.
@duaraghav8 duaraghav8 merged commit 1b257d8 into algorithm-visualizer:gh-pages May 31, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@jonathanxia @duaraghav8