## Lecture 17. Spanning Trees
- Krushal
- Prim
---
### Spanning tree
- A **spanning tree** of a graph consists of all nodes of the graph and some of the edges of the graph so that there is a path between any two nodes.
- Spanning trees are connected and acyclic.
- Usually there are several ways to construct a spanning tree.
---
#### Spanning tree
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
---
#### Spanning tree
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/ZiXuqVVR.png" class="element-left content-img" />
---
#### Spanning tree
<img src="https://cdn.ucode.vn/uploads/1/upload/ZiXuqVVR.png" class="element-left content-img" />
- The **weight** of a spanning tree is the **sum of its edge weights**.
- For example, the weight of the above spanning tree is $3+5+9+3+2 = 22$.
---
#### Spanning tree
- A **minimum spanning tree** is a spanning tree whose weight is as small as possible.
- The weight of a minimum spanning tree for the example graph is $20$, and such a tree can be constructed as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/pLfexVsj.png" class="element-left content-img" />
---
#### Spanning tree
- A **maximum spanning** tree is a spanning tree whose weight is as large as possible.
- The weight of a maximum spanning tree for the example graph is 32:
<img src="https://cdn.ucode.vn/uploads/1/upload/XyKLFTem.png" class="element-left content-img" />
---
#### Spanning tree
- A graph may have several minimum and maximum spanning trees
- Several greedy methods can be used to construct minimum and maximum spanning trees.
- In this chapter, we discuss two algorithms that process the edges of the graph ordered by their weights.
- We focus on finding **minimum spanning trees**, but the same algorithms can find maximum spanning trees by processing the edges in reverse order.
---
### Kruskal’s algorithm
- The initial spanning tree only contains the nodes of the graph (no edges).
- Then the algorithm goes through the edges ordered by their weights, and always adds an edge to the tree if it does not create a cycle.
---
#### Kruskal’s algorithm
- The algorithm maintains the **components** of the tree.
- Initially, each node of the graph belongs to a separate component.
- Always when an edge is added to the tree, two components are joined.
- Finally, all nodes belong to the same component, and a minimum spanning tree has been found.
---
#### Kruskal’s algorithm
- Example: the graph and sorted edge list:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/wDjoZlAr.png" class="element-left content-img" />
---
#### Kruskal’s algorithm
- The algorithm goes through the list and adds each edge to the tree if it joins two separate components.
- Initially, each node is in its own component:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/iAiPnCmr.png" class="element-left content-img" />
---
#### Kruskal’s algorithm
- The first edge to be added to the tree is the edge $5–6$ that creates a component $\{5,6\}$ by joining the components $\{5\}$ and $\{6\}$:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/alWRXaBp.png" class="element-left content-img" />
---
#### Kruskal’s algorithm
- After this, the edges $1–2$, $3–6$ and $1–5$ are added in a similar way:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/qOUcdmOC.png" class="element-left content-img" />
---
#### Kruskal’s algorithm
- The next edge in the list is the edge $2–3$, but it will not be included in the tree, because nodes $2$ and $3$ are already in the same component.
- For the same reason, the edge $2–5$ will not be included in the tree.
- Finally, the edge $4–6$ will be included in the tree:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/cjuACpXI.png" class="element-left content-img" />
---
#### Kruskal’s algorithm: implementation
- It is convenient to use the **edge list** representation of the graph.
- The first phase of the algorithm sorts the edges in the list in $O(m \log m)$ time.
- The second phase of the algorithm builds the minimum spanning tree as follows:
```python=
for (a,b) in edges:
if not same(a,b):
unite(a,b)
```
Note:
the function same determines if a and b are in the same component, and the function unite joins the components that contain a and b.
---
#### Kruskal’s algorithm: implementation
- The function `same(a, b)` determines if $a$ and $b$ are in the same component.
- The function `unite(a, b)` joins the components that contain $a$ and $b$.
- How to efficiently implement the functions `same` and `unite`.
- One solution for `same`: graph traversal and check if we can get from node $a$ to node $b$ $\rightarrow$ $O(n + m)$, and loop for every edge $\rightarrow$ **slow**.
- **Union-find** structure that implements both functions in $O(\log n)$ time.
---
### Union-find structure
- A union-find structure maintains a collection of **disjoint sets**.
- Two $O(\log n)$ time operations are supported:
- The **unite** operation joins two sets
- The **find** operation finds the **representative** of the set that contains a given element
<img src="https://cdn.ucode.vn/uploads/1/upload/WUlZLIFg.png" class="element-left content-img" />
---
### Union-find structure
- In a union-find structure, one element in each set is the **representative** of the set, and there is a chain from any other element of the set to the representative.
- Assume that the sets are $\{1,4,7\}$, $\{5\}$ and $\{2,3,6,8\}$, the representatives of the sets are $4$, $5$ and $2$
<img src="https://cdn.ucode.vn/uploads/1/upload/WUlZLIFg.png" class="element-left content-img" />
---
### Union-find structure
- We can find the representative of any element by **following the chain** that begins at the element.
- Two sets can be **joined** by connecting the representative of one set to the representative of the other set.
<img src="https://cdn.ucode.vn/uploads/1/upload/PMVYJiKT.png" class="element-left content-img" />
---
#### Union-find structure
- The efficiency of the union-find structure depends on how the sets are joined
- A simple strategy: always connect the representative of the **smaller** set to the representative of the **larger** set
- The length of any chain will be $O(\log n)$
<img src="https://cdn.ucode.vn/uploads/1/upload/PMVYJiKT.png" class="element-left content-img" />
---
#### Kruskal’s algorithm: implementation
```python=
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
# Search function
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
# Applying Kruskal algorithm
def kruskal(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < len(self.graph) - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
for u, v, weight in result:
print("%d - %d: %d" % (u, v, weight))
```
---
#### Kruskal’s algorithm: implementation
```python=
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal()
# 1 - 2: 2
# 2 - 5: 2
# 2 - 3: 3
# 3 - 4: 3
# 0 - 1: 4
```
---
### Prim’s algorithm
- The algorithm first adds an arbitrary node to the tree.
- After this, the algorithm always chooses a **minimum-weight** edge that adds a new node to the tree.
- Finally, all nodes have been added to the tree and a minimum spanning tree has been found.
---
#### Prim’s algorithm
- Resembles Dijkstra’s algorithm:
- Dijkstra’s algorithm always selects an edge whose distance from the starting node is minimum
- Prim’s algorithm simply selects the minimum weight edge that adds a new node to the tree.
---
#### Prim’s algorithm
- Let us consider how Prim’s algorithm works in the following graph:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
---
#### Prim’s algorithm
- Initially, there are no edges between the nodes:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/iAiPnCmr.png" class="element-left content-img" />
---
#### Prim’s algorithm
- An arbitrary node can be the starting node, so let us choose node $1$. First, we add node 2 that is connected by an edge of weight $3$:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/pkUubZdO.png" class="element-left content-img" />
---
#### Prim’s algorithm
- After this, there are two edges with weight 5, so we can add either node 3 or node 5 to the tree. Let us add node 3 first:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/WPboneXV.png" class="element-left content-img" />
---
#### Prim’s algorithm
- The process continues until all nodes have been included in the tree:
<img src="https://cdn.ucode.vn/uploads/1/upload/xfBYAqeL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/TKTmEqGH.png" class="element-left content-img" />
---
#### Prim’s algorithm: implementation
- Like Dijkstra’s algorithm, Prim’s algorithm can be efficiently implemented using a **priority queue**.
- The priority queue should contain all nodes that can be connected to the current component using a single edge.
- The time complexity of Prim’s algorithm is $O(n+m\log m)$
---
#### Prim’s algorithm: implementation
```python=
from collections import defaultdict
import heapq
def create_spanning_tree(graph, starting_vertex):
mst = defaultdict(set)
visited = {starting_vertex}
edges = [(cost, starting_vertex, to) for to, cost in graph[starting_vertex].items()]
# print(edges)
heapq.heapify(edges)
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst[frm].add(to)
for to_next, cost in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost, to, to_next))
return mst
```
---
#### Prim’s algorithm: implementation
```python=
example_graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
'C': {'A': 3, 'B': 1, 'F': 5},
'D': {'B': 1, 'E': 1},
'E': {'B': 4, 'D': 1, 'F': 1},
'F': {'C': 5, 'E': 1, 'G': 1},
'G': {'F': 1},
}
print(dict(create_spanning_tree(example_graph, 'A')))
# {'A': {'B'}, 'B': {'D', 'C'}, 'D': {'E'}, 'E': {'F'}, 'F': {'G'}}
```
---
## The end
{"metaMigratedAt":"2023-06-17T19:46:16.105Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 17. Spanning Trees","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":12668,\"del\":29}]"}