0%

Minimum spanning tree

[Update] Minimum spanning tree

Python implementation

Kruskal’s algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class UF:
def __init__(self):
self.uf = {}

def find(self, x: int) -> int:
uf = self.uf
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = self.find(uf[x])
return uf[x]

def union(self, x: int, y: int) -> None:
# x -> y
uf = self.uf
uf[self.find(x)] = self.find(y)


def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> int:
uf, ret = UF(), []

for u, v, w in sorted(edges, key=lambda x: x[2]):
if uf.find(u) != uf.find(v):
ret.append((u, v, w))
uf.union(u, v)

return ret if len(set(map(uf.find, range(n)))) == 1 else []

print(kruskal(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Prim’s algorithm

E * log(V)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sortedcontainers import SortedList
def prim(n: int, edges: List[Tuple[int, int, int]]) -> int:
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w

start = 0
pq, ret, visited = SortedList([(0, start, None)]), [], set()

while pq:
w, u, p = pq.pop(0)
if u in visited: continue

visited.add(u)
ret.append((p, u, w))

for v, w in graph[u].items():
if v in visited: continue
pq.add((w, v, u))

return ret[1:] if len(visited) == n else []

print(prim(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

V * log(V)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from sortedcontainers import SortedList
def prim(n: int, edges: List[Tuple[int, int, int]]) -> int:
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w

start = 0
pq, ret, visited, prev = SortedList([(0, start, None)]), [], set(), {}

while pq:
if len(visited) == n:
break
w, u, p = pq.pop(0)
if u in visited: continue

visited.add(u), ret.append((p, u, w))

for v, w in graph[u].items():
if v in visited: continue
if v in prev and prev[v][1] >= w:
pq.remove((prev[v][1], v, prev[v][0]))
prev[v] = (u, w)
pq.add((w, v, u))

return ret[1:] if len(visited) == n else []

print(prim(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Prime

From Wikipedia

  1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.

  2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).

  3. Repeat the following steps until Q is empty:

    a. Find and remove a vertex v from Q having the minimum possible value of C[v]  
    b. Add v to F and, if E[v] is not the special flag value, also add E[v] to F
    c. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
        1). Set C[w] to the cost of edge vw  
        2). Set E[w] to point to edge vw
    
1
def Prim(edges: )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// V vertexs, E edges
// Time complexity: E * log(V)
//

class Solution {
public:

auto Prim(vector<pair<int, pair<string, string>>>& graph) {

// adjacent list
unordered_map<string, vector<pair<string, int>>> mp_adjacent;
unordered_set<string> vertexs_original, vertexs_included;

// build adjacent list and initialize vertex_original
for (auto& edge : graph) {
string vertex1 = edge.second.first, vertex2 = edge.second.second;
int weight = edge.first;

mp_adjacent[vertex1].push_back(make_pair(vertex2, weight));
mp_adjacent[vertex2].push_back(make_pair(vertex1, weight));

vertexs_original.insert(edge.second.first);
vertexs_original.insert(edge.second.second);

}

vector<pair<int, pair<string, string>>> res;

// start to build tree, edges used as heap to select minimum edge
using MltMap = multimap<int, pair<string, string>>;
MltMap edges;
// map_heap_iter used to index vertex's element in edges
unordered_map<string, MltMap::iterator> mp_heap_iter;
for (auto& vertex : vertexs_original) {
mp_heap_iter[vertex] = edges.insert(MltMap::value_type(INT_MAX, make_pair(vertex, vertex)));
}

// search from start vertex(arbitrarily)
string start = *vertexs_original.begin();
vertexs_included.insert(start);
edges.erase(mp_heap_iter[start]);

for (auto& edge : (mp_adjacent[start])) {
string vertex = edge.first;
int weight = edge.second;
if (vertexs_included.count(vertex) == false && mp_heap_iter[vertex]->first > weight) {
// update edges;
edges.erase(mp_heap_iter[vertex]);
mp_heap_iter[vertex] = edges.insert(MltMap::value_type(weight, make_pair(vertex, start)));
}
}


while (vertexs_original.size() != vertexs_included.size()) {
// select shortest edge into spanning tree
auto edge_selected = edges.begin();
auto vertex1 = edge_selected->second.first, vertex2 = edge_selected->second.second;
int weight_selected = edge_selected->first;
res.push_back(make_pair(weight_selected, make_pair(vertex1, vertex2)));
vertexs_included.insert(vertex1);

// remove the edge from edges(heap)
edges.erase(mp_heap_iter[vertex1]);

// update edges connected to vertex1
for (auto& edge : (mp_adjacent[vertex1])) {
string vertex = edge.first;
int weight = edge.second;
if (vertexs_included.count(vertex) == false && mp_heap_iter[vertex]->first > weight) {
edges.erase(mp_heap_iter[vertex]);
mp_heap_iter[vertex] = edges.insert(MltMap::value_type(weight, make_pair(vertex, vertex1)));
}
}
}

return res;
}
};

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// V vertexs, E edges
// Time complexity: E * log(E)
//

class Solution {
string Find(unordered_map<string, string>& union_found, string vertex) {
while (vertex != union_found[vertex]) {
string des = union_found[vertex];
union_found[vertex] = union_found[des];
vertex = des;
}
return vertex;
}

void Union(unordered_map<string, string>& union_found, string& vertex1, string& vertex2) {
string root1 = Find(union_found, vertex1), root2 = Find(union_found, vertex2);
if (root1 == root2)
return;
union_found[root1] = root2;
}
public:
auto Kruskal(vector<pair<int, pair<string, string>>>& graph) {
sort(graph.begin(), graph.end(), [](const pair<int, pair<string, string>>& lhs, const pair<int, pair<string, string>>& rhs){
return lhs.first < rhs.first;
});

using MpType = unordered_map<string, string>;
MpType union_found;
unordered_set<string> vertexs;
for (auto& edge : graph) {
vertexs.insert(edge.second.first);
vertexs.insert(edge.second.second);
if (union_found.find(edge.second.first) == union_found.end())
union_found.insert(MpType::value_type(edge.second.first, edge.second.first));
if (union_found.find(edge.second.second) == union_found.end())
union_found.insert(MpType::value_type(edge.second.second, edge.second.second));
}

vector<pair<int, pair<string, string>>> res;

// start to build spinning tree
string start = *vertexs.begin();

for (auto& edge : graph) {
string vertex1 = edge.second.first, vertex2 = edge.second.second;
if (Find(union_found, vertex1) == Find(union_found, vertex2))
continue;
res.push_back(edge);
Union(union_found, vertex1, vertex2);
if (res.size() + 1 >= vertexs.size())
break;
}

return res;
}
};