Skip to content

Commit cba9592

Browse files
gazeldxgazeldx
committed
1584-min-cost-to-connect-all-points.md Removed heap sort from Kruskal Algorithm. Added Comparison between Prim's Algorithm and Kruskal Algorithm.
1 parent 0b3e9ad commit cba9592

4 files changed

Lines changed: 64 additions & 34 deletions

File tree

‎en/1001-2000/1584-min-cost-to-connect-all-points-2.md‎

Lines changed: 30 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -61,43 +61,59 @@ This page, I will only talk about the solution of **Kruskal's Algorithm**.
6161
- Traverse all edges once, add up the lengths of the edges and return the sum as the result.
6262
- If you are familiar with the **Union-Find** algorithm, it is easy to solve the problem with _Kruskal's algorithm_. However, this problem does not directly give the `edges` information, and we need to calculate it through the vertex information, which is not difficult, but this causes the algorithm to run slower than _Prim's Algorithm_ because there are too many edges. The more edges, the slower _Kruskal's Algorithm_.
6363

64-
## Complexity
65-
`E` is the `edges.length`.
64+
#### Compare to Prim's Algorithm
65+
For this problem, `points` are given, so using `Prim's Algorithm` would be faster and easier to understand.
66+
67+
Because if we use `Kruskal's Algorithm`, we have to convert `points` into `edges`, and we will get a fully dense graph.
6668

67-
`N` is the `points.length`.
69+
The more edges there are, the worse the performance of `Kruskal's Algorithm` will be.
6870

69-
* Time: `O(E * logE)`.
70-
* Space: `O(N * N)`.
71+
For sparse graphs, `Kruskal's Algorithm` is much more efficient than `Prim's Algorithm`.
72+
73+
For problems of `Minimum Spanning Tree` which `edges` are given, we can give priority to using _Kruskal's Algorithm_.
74+
75+
## Complexity
76+
> `V` is the `points.length`.
77+
> `E` is the `edges.length`. In this problem, the `E` is `V * V`.
78+
79+
* Time: `O(E * log(E))`.
80+
* Space: `O(V * V)`.
7181

7282
## Python
83+
The following code can also be implemented by using `heap sort`, but it would be slower.
7384
```python
85+
from collections import deque
86+
7487
class Solution:
7588
def __init__(self):
7689
self.parents = []
7790

7891
def minCostConnectPoints(self, points: List[List[int]]) -> int:
7992
self.parents = list(range(len(points)))
8093
result = 0
81-
edged_points = []
94+
edges = []
8295

8396
for i, point in enumerate(points):
8497
for j in range(i + 1, len(points)):
8598
distance = abs(point[0] - points[j][0]) + \
8699
abs(point[1] - points[j][1])
87-
heapq.heappush(edged_points, (distance, i, j))
100+
edges.append((distance, i, j))
101+
102+
edges.sort()
103+
edges = deque(edges)
104+
105+
while edges:
106+
distance, i, j = edges.popleft()
88107

89-
while edged_points:
90-
distance, i, j = heapq.heappop(edged_points)
91-
92108
if self.is_same_root(i, j):
93109
continue
94-
110+
95111
self.unite(i, j)
96-
112+
97113
result += distance
98114

99115
return result
100-
116+
101117
def unite(self, x, y):
102118
root_x = self.find_root(x)
103119
root_y = self.find_root(y)
@@ -109,7 +125,7 @@ class Solution:
109125

110126
if x == parent:
111127
return x
112-
128+
113129
root = self.find_root(parent)
114130

115131
self.parents[x] = root

‎en/1001-2000/1584-min-cost-to-connect-all-points.md‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -198,9 +198,10 @@ Which way do you prefer? I prefer `way 1` because it's easier to understand.
198198
* `visited` is also not needed, because each `heappop()` means that a point has been `visited`.
199199

200200
## Complexity
201-
`n` is the `points.length`.
202-
* Time: `O(n * n)`. All those solutions' time complexity are `O(n * n)`, because `heapq.heapify()` is `O(n)`.
203-
* Space: `O(n)`.
201+
`V` is the `points.length`.
202+
203+
* Time: `O(V * V)`. All those solutions' time complexity are `O(n * n)`, because `heapq.heapify()` is `O(n)`.
204+
* Space: `O(V)`.
204205

205206
## Python
206207
### Solution 1: Not use 'heap sort'

‎zh/1001-2000/1584-min-cost-to-connect-all-points-2.md‎

Lines changed: 26 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -61,43 +61,55 @@ This page, I will only talk about the solution of **Kruskal's Algorithm**.
6161
- Traverse all edges once, add up the lengths of the edges and return the sum as the result.
6262
- If you are familiar with the **Union-Find** algorithm, it is easy to solve the problem with _Kruskal's algorithm_. However, this problem does not directly give the `edges` information, and we need to calculate it through the vertex information, which is not difficult, but this causes the algorithm to run slower than _Prim's Algorithm_ because there are too many edges. The more edges, the slower _Kruskal's Algorithm_.
6363

64-
## Complexity
65-
`E` is the `edges.length`.
64+
#### Compare to Prim's Algorithm
65+
For this problem, `points` are given, so using `Prim's Algorithm` would be faster and easier to understand.
66+
67+
Because if we use `Kruskal's Algorithm`, we have to convert `points` into `edges`, and we will get a fully dense graph.
68+
69+
For sparse graphs, `Kruskal's Algorithm` is more efficient than `Prim's Algorithm`.
6670

67-
`N` is the `points.length`.
71+
## Complexity
72+
- `V` is the `points.length`.
73+
- `E` is the `edges.length`. In this problem, the `E` is `V * V`.
6874

69-
* Time: `O(E * logE)`.
70-
* Space: `O(N * N)`.
75+
* Time: `O(E * log(E))`.
76+
* Space: `O(V * V)`.
7177

7278
## Python
79+
The following code can also be implemented by using `heap sort`, but it would be slower.
7380
```python
81+
from collections import deque
82+
7483
class Solution:
7584
def __init__(self):
7685
self.parents = []
7786

7887
def minCostConnectPoints(self, points: List[List[int]]) -> int:
7988
self.parents = list(range(len(points)))
8089
result = 0
81-
edged_points = []
90+
edges = []
8291

8392
for i, point in enumerate(points):
8493
for j in range(i + 1, len(points)):
8594
distance = abs(point[0] - points[j][0]) + \
8695
abs(point[1] - points[j][1])
87-
heapq.heappush(edged_points, (distance, i, j))
96+
edges.append((distance, i, j))
97+
98+
edges.sort()
99+
edges = deque(edges)
100+
101+
while edges:
102+
distance, i, j = edges.popleft()
88103

89-
while edged_points:
90-
distance, i, j = heapq.heappop(edged_points)
91-
92104
if self.is_same_root(i, j):
93105
continue
94-
106+
95107
self.unite(i, j)
96-
108+
97109
result += distance
98110

99111
return result
100-
112+
101113
def unite(self, x, y):
102114
root_x = self.find_root(x)
103115
root_y = self.find_root(y)
@@ -109,7 +121,7 @@ class Solution:
109121

110122
if x == parent:
111123
return x
112-
124+
113125
root = self.find_root(parent)
114126

115127
self.parents[x] = root

‎zh/1001-2000/1584-min-cost-to-connect-all-points.md‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -198,9 +198,10 @@ Which way do you prefer? I prefer `way 1` because it's easier to understand.
198198
* `visited` is also not needed, because each `heappop()` means that a point has been `visited`.
199199

200200
## Complexity
201-
`n` is the `points.length`.
202-
* Time: `O(n * n)`. All those solutions' time complexity are `O(n * n)`, because `heapq.heapify()` is `O(n)`.
203-
* Space: `O(n)`.
201+
`V` is the `points.length`.
202+
203+
* Time: `O(V * V)`. All those solutions' time complexity are `O(n * n)`, because `heapq.heapify()` is `O(n)`.
204+
* Space: `O(V)`.
204205

205206
## Python
206207
### Solution 1: Not use 'heap sort'

0 commit comments

Comments
 (0)