We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #107: Minimal network
Project Euler #107: Minimal network
Sort by
recency
|
12 Discussions
|
Please Login in order to post a comment
Both Kruskal and Prim algorithm work fine because they have the same time complexity O(E.log(V)).
Warning: for any Minimum Spanning Tree problems, use graph as list of [u,v,w] instead of adjacency list (hash table). MST requires graph sorting in ascending order of weights, so it's a suicide to use adjacency list. For example: use graph = [[1,2,16], [1, 3, 12]] instead of graph = {1: {2: 16}, 1: {3: 12}}
My Python Kruskal implementation here
Thanks! You help me understand why people always use graph as list in MST
Prim is the best suited as graph has too many edges. However Kruskal is also fine ;) 100 points are 100 points, no matter how you get it :P
Kruskal's Algorithm is also worked for me. but we need to implement Disjoint sets with Union by rank and path compression
Yes I know. but Prim should be ideally and morally used in case of more edges than vertices.
For me, optimised Prim's with min priority queue worked.
Wrong answer on test cases 5 and 6 with two different implementations of the Prim's algorithm using Java 8: https://github.com/veniva/algo-minimal-network
why are comments blocked on problem 106?