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.
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}}
Project Euler #107: Minimal network
You are viewing a single comment's thread. Return to all comments →
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