KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
I have the following problem on my homework: Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph (We are allowed to get help from others on this assignment, so this isn't cheating.) I think that I could do a BFS and find if this edge is a edge between two layers and if so whether this edge was the smallest across those layers. But what could I say when this edge is not a tree edge of the BFS tree?
Tags (comma-separated)
Save Edits
Cancel