[go: up one dir, main page]
Scribd
Upload
16 views22 pages

Lecture 15 Bis

A&D part 4

Uploaded by

minhb2203567
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views22 pages

Lecture 15 Bis

A&D part 4

Uploaded by

minhb2203567
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 22

ALGORITHM

KRUSKAL ALGORITHM

Phạm Nguyên Khang


pnkhang@cit.ctu.edu.vn

CAN THO, 12/4/2023


Idea
Kruskal(G = (V,E)):
• Sort the edges in E by non-decreasing weight.
• MST={}
• for e in E (in sorted order):
• if adding e to MST won’t cause a cycle:
• add e to MST.
• return MST

1
Cycle checking
• How to check if adding (C, F) causes cycle?

2
Cycle checking
• How to check if adding (C, F) causes cycle?

3
Cycle checking
• How to check if adding (C, F) causes cycle?

4
Cycle checking
• How to check if adding (I, G) causes cycle?

5
Cycle checking
• How to check if adding (u, v) causes cycle?
• u and v are in different components => no cycle,
merge two components into one.

• u and v are the same component => cycle, ignore

6
Implementation
• Data structure (Set) which supports three operators:
• makeSet(u): create a component which contains only u
• find(u): find the component containing u
• union(u, v): merge the component that u is in with the
component that v is in.

• Simple implementation: tree


• parent[u]: the parent of node u
• u is root iif parent[u] = u
• A component is represented by the root of the tree

7
Implementation
• Simple implementation: tree!
• parent[u]: the parent of node u

parent[A] = A
parent[B] = A
parent[G] = G
parent[C] = G
parent[I] = C
parent[H] = G
parent[F] = G
parent[D] = D
parent[E] = D

8
Implementation
• find(u): returns the root of the three that u is in.
find(u) {
while(u != parent[u])
u = parent[u];
return u;
}

find(I) returns G
9
Implementation
• union(root_u, root_v): merges two trees
union(root_u, root_v) {
return parent[root_v] = root_u;
}

union(A, G)
10
Implementation
Kruskal(G = (V,E)):
• Sort the edges in E by non-decreasing weight.
• MST={}
• for u in V Kruskal(G = (V,E)):
• parent[u] = u • Sort the edges in E by non-
decreasing weight.
• for e in E (in sorted order): • MST={}
• root_u = find(u) • for e in E (in sorted order):
• root_v = find(v) • if adding e to MST won’t
• if root_u != root_v: cause a cycle:
• add e to MST • add e to MST.
• parent[root_v] = root_u • return MST
• return MST

11
Example

12
Sort edges

13
Connected components

14
For edge in edges

15
For edge in edges

16
For edge in edges

17
For edge in edges

18
For edge in edges

19
Example

20
THANK YOU

21

You might also like