Ch9-Graph algorithms for coding test

1. Graph and Tree data structure
2. Disjoint sets
3. Spanning Tree
4. Topology Sort

Q1. Team building

Q2. City zoning

Q3. Curriculum

1. Graph and Tree data structure

This table is summary of graph and tree

There are two way to implement graph.

• Adjacency matrix : use 2-dimension array.
• Adjacency list : use list.

If the question mention about each objects are connected, you need to think firstly graph algorithm. For example, it’s like “Each cities are connected”. Tree data structure is used when implementing Dijkstra algorithm and Min heap or Max heap in priority queue.

2. Disjoint sets

Disjoint set is the set without common element. For example, sets {1,2} and sets {3,4} are disjoint relationship. but sets {1,2} and sets {1,3} aren’t disjoint relationship because of 1.

Disjoint sets data structure is data structure to manage data of element which is divided by subset of disjoint sets. There are two operator that is union and find. Union operator merge two sets to one set. Find operator is to find a set including specific element in sets. Stack and Queue is composed of push and pop operator. Disjoint set data structure also composed of Union and find operator.

2.1 Disjoint sets data structure

Tree structure is used when implementing disjoint sets data structure. The process is like this.

1. Check the union operation and two connected nodes A,B
2. Find the root node of A, B.
3. Set the root node A as parent node of B. Root node B point out root node A
4. Repeat the process until to finish every union operator.

For example, There are 6 elements and it composed sets { 1, 2, 3, 4, 5, 6 }. And there are 4 union operation.

( union 1,4 ), ( union 2,3 ), (union 2,4 ), (union 5,6 )

These union means ‘1 and 4 are same set’, ‘2 and 3 are same set’, ‘2 and 4 are same set’, ‘5 and 6 are same set’. Graph could present these operators. Each elements will be node and union operators will be edges.

We could know the relationship of each nodes. There are two sets { 1, 2, 3, 4 } and {5, 6} because edges which are union operator shows the relationship of nodes. So this graph could be divided like following figure.

Let’s check more specific process of disjoint sets algorithm.

step1. Initialize parent node table.

step2. Check the union operator ‘union 1,4’. Set the root node 1 as parent node of node 4 because this is tree data structure and 1 is greater than 4.

step3. Check the union operator ‘union 2,3’. Set the root node 2as parent node of node 3 because this is tree data structure and 2 is greater than 3.

step4. Check the union operator ‘union 2,4’. Current root nodes of node 4 is node 1. Set the root node 1 as parent node of node 2.

step5. Check the union operator ‘union 5,6’. Set the root node 5 as parent node of node 6 because this is tree data structure and 5 is greater than 6.

The point of this algorithm is it always has ‘parent table’. It couldn’t directly calculate and every time check the root nodes in parent table. For example, Parent node of node 3 is node 2 in step5. but parent node of node 2 is node 1 so, in the final step, parent node of node 3 is node 1.

In this figure, To find root of node 3, move to parent node 2 and then again move to node 1. There are no more parent node when check node 1 so node is root of node 3. In other words, it could use recursive function to find parent node in disjoint sets. The code is like this

# Find sets include specific element
def find_parent(parent, x):
    # If it isn't root node, call the recursive function until to find root node
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# Merge sets include two elements
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# Input the number of nodes and edges( union operators )
v, e = map(int, input().split() )
# Initialize parent table
parent = [0] * ( v+1 )

# Initialize parent table as themself
for i in range(1, v+1 ):
   parent[i] = i

# Perform union operato
for i in range(e):
    a, b = map(int, input().split() )
    union_parent(parent, a, b)

# print sets 
print('Root node of current node: ', end=' ')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')
print()

# print parent table
print('Parent table: ', end=' ')
for i in range(1, v+1):
    print(parent[i], end=' ')


"""

6 4
1 4
2 3
2 4
5 6
Root node of current node:  1 1 1 1 5 5 
Parent table:  1 1 2 1 5 5 

"""
 

The root node of current node is ( 1, 1, 1, 1, 5, 5 ). Root nodes make the same sets to same elements so the original elements are divide by { 1, 2, 3, 4 } and {5, 6}. The ‘find_parent’ method is not efficient because it check every nodes so we could optimize this method by using ‘Path compression’. Path compression call the ‘find_parent’ method as recursive function and update parent node.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

2.2 Cycle detection by using disjoint sets.

Disjoint sets is used when detecting cycle in directed cycle. Additionally, if no directed cycle, DFS algorithm finds a topological order in graph.

The union operator could be present by edge in graph so cycle detection is checking the edges and merge sets include two nodes.

1. Check the each edges and root nodes of two nodes.
2. If root nodes aren’t same, use union operator to two nodes.
3. If root node are same, Cycle is occurred in graph.
4. Repeat these process.

step1. Initialize parent table.

step2. Check edges (1,2). Root node of node 1 and node 2 are 1, 2. Update parent node of node 2 as 1.

step3. Check edges (1,3). Root node of node 1 and node 3 are 1, 3. Update parent node of node 3 as 1

step4. Check edges (2,3). Node 2 and node 3 already has root node which is node 1. It means cycle is occurred in graph.

This cycle detection algorithm check every edges and it call union method or find method to each edges. This algorithm only use to directed cycle.

# Find sets include specific element
def find_parent(parent, x):
    # Call the recursive funtion until find root node
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x] )
    return parent[x]

# Merge sets include two elements
def union_parent(paretn, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# Input the number of edges and nodes.
v, e = map(int, input().split() )
parent = [0] * (v+1)

# Initialize parent table
for i in range(1, v+1):
    parent[i] = i

# Cycle detection
cycle = False 

for i in range(e):
    a,b = map(int, input().split() )
    # If cycle is occurred, stop the process
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # If cycle is occurred, use union operator
    else:
        union_parent(parent, a, b)

if cycle:
    print('Cycle is occurred.')
else:
    print('Cycle is not occurred.')

"""

3 3
1 2
1 3
2 3
Cycle is occurred.


"""

3. Spanning Tree

Spanning tree is the graph include every nodes and cycle is not exist. There are many spanning tree in left graph and right graph is one of them.

3.1 Kruskal algorithm

Kruskal algorithm is to find minimum cost spanning tree in every cases. The process is like this

1. Sort edge datas in ascending order by cost
2. If cycle is not occurred, add to minimum spanning tree.
3. If cycle is occurred, don’t add to minimum spanning tree.
4. Repeat these process.

Let’s find minimum spanning tree.

Minimum spanning tree is tree data structure so it has feature the number of edges is ‘number of node — 1’.

Get ConfidenceCoding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

step 1. Sort every edge information of graph. There is 9 edges in the graph. Put this edges to list and sort every edges.

step 2. Choose shortest distance edge. Add (3,4) to sets. In other word, use union method to node 3 , node 4.

step 3. Choose shortest distance edge which is (4,7). Cycle is not occurred and use union method to node 4, node 7.

step 4. Choose shortest distance edge which is (4,6). Cycle is not occurred and use union method to node 4, node 6.

step 5. Choose shortest distance edge which is (6,7). Cycle is occurred so don’t call union method.

step 6. Choose shortest distance edge which is (1,2). Cycle is not occurred and use union method to node 1, node 2.

step 7. Choose shortest distance edge which is (2,6). Cycle is not occurred and use union method to node 2, node 6.

step 8. Choose shortest distance edge which is (2,3). Cycle is occurred so don’t call union method.

step 9. Choose shortest distance edge which is (5,6). Cycle is not occurred and use union method to node 5, node 6.

step 10. Choose shortest distance edge which is (1,5). Cycle is occurred so don’t call union method.

We found minimum spanning tree. total cost is sum of edge distance so total cost is 159 in this case.

# Find sets including specific element
def find_parent(parent, x):
    # If it is not root node, call recursive function
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# Merge sets include two element
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# Input thenumber of nodes and edges
v, e = map(int, input().split() )
# Initialize parent table
parent = [0] * (v+1)

# Variable to include edges and cost
edges = []
result = 0

# Initialize parent table as themself
for i in range(1, v+1):
    parent[i] = i

# Input every edges
for _ in range(e):
   a, b, cost = map(int, input().split() )
   # set the first element as cost
   edges.append((cost, a, b))

# Sort edges
edges.sort()

# Check every edges
for edge in edges:
    cost, a, b = edge
    # Add set if cycle is not occurred.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

"""

7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25


159

"""

4. Topology Sort

Topology sort arranges nodes in the way that preserve in the order of nodes. ‘Indegree’ is main idea of topology sort algorithm. Indegree is the number of incoming directed edge to a vertex in a directed graph. The process is like these.

1. Input node that indegree is 0 to queue
2. Put out the element from queue and remove starting edge from graph.
3. Input updated node that indegree is 0 to queue
4. Repeat process

This algorithm repeat the process that put out the element from queue until queue is empty. Furthermore, If queue is empty before put out specific element, cycle is occurred. Basically, Most of question mention cycle is not occurred and following example is also same case in this chapter.

step0. Input node that indegree is 0 to queue. Current node 1 of indegree is only 0. Input node 1 to queue. Gray color represent inserted queue.

step1. Put out node 1 from queue and remove edge connected with node 1. After then, indegree of node 2 and node 5 is 0 and insert node 2 and 5 to queue. Completed node and edges are represented by dotted line.

step2. Put out node 2 from queue and remove edge connected with node 2. After then, indegree of node 3 is updated to 0. Insert node 3 to queue.

step3. Put out node 5 from queue and remove edge connected with node 5. After then, indegree of node 6is updated to 0. Insert node 6to queue.

step4. Put out node 3 from queue and remove edge connected with node 3. There is no updated node. pass to next step

step 5. Put out node 6 from queue and remove edge connected with node 6. After then, indegree of node 4 is updated to 0. Insert node 4to queue.

step 6. Put out node 4 from queue and remove edge connected with node 4. After then, indegree of node 7 is updated to 0. Insert node 7 to queue.

step 7. Put out node 7 from queue and remove edge connected with node 7. There is no updated node. End the process.

The result of topology sort is printing node in order of the exit. It can be multiple results. If there are two element put to queue in a step, the result can be two. For example, the results can be ‘ 1-2-5-3-6-4-7 ’or ‘1-5-2-3-6-4-7’ in this graph.

from collections import deque

# input nodes and edges
v, e = map(int, input().split())
# Initialize indegree to 0
indegree = [0] * (v+1)
# Initialize connected graph
graph = [ [] for i in range(v+1) ]

# Input every information of directed graph
for _ in range(e):
    a, b = map(int, input().split())
    # Move from vertex a to vertex b
    graph[a].append(b)
    indegree[b] += 1

# Topology sort
def topology_sort():
    result = [] 
    q = deque()

    # Input node that indegree is 0 to queue at starting point
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    # Repeat the process
    while q:
        now = q.popleft()
        result.append(now)
        # Minus 1 to indegree of connected nodes
        for i in graph[now]:
            indegree[i] -= 1
            # Put updated node to queue
            if indegree[i] == 0:
                q.append(i)
    
    # Print the result
    for i in result:
        print( i, end= ' ')

topology_sort()

"""

7 8 
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4


1 2 5 3 6 4 7 


"""

Q1. Team building

Each students have number from 0 to N and there is N + 1 team. Teacher can use ‘Team merge’ operator and ‘Check same team’ operator.

1. ‘Team merge’ operator merge two teams to one team
2. ‘Check same team’ operator check two students are in same team.

Teacher can use operators N times. Make the program print the result about ‘Check same team’ operator.

Solution

This question is disjoint set problem. The range of N and M is maximum 100,000. So it is used path compression.

# Find sets include specific element
def find_parent(parent, x):
    # Call the recursive function , if it is not root node.
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# Merge set inclue two elements
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split() )
# Initialize parent table
parent = [0] * ( n+1 )

# Initialize parent node as themself
for i in range(0, n+1):
    parent[i] = i

# Check operators
for i in range(m):
    oper, a, b = map(int, input().split() )
    # Union operator
    if oper == 0:
        union_parent(parent, a, b)
    # Find operator
    elif oper == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('No')

"""

7 8
0 1 3
1 1 7
No
0 7 6
1 7 1
No
0 3 7
0 4 2
0 1 1
1 1 1
YES

"""

Q2. City zoning

City is composed of N number of house and M number of roads. Mayor plan to divide city as two. The road is always exist between two house and the house exist at least one in a city. Make the program find the case which has minimum load.

Solution

The idea of this question is it need two minimum spanning tree in graph. Firstly, Find the minimum spanning tree by using kruskal algorithm and remove longest distance edge.

# Find the set include specific element
def find_parent(parent, x):
    # Call recursive function if it is not root node
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# Merge sets include two element
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# Input the number of nodes and edges
v, e = map(int, input().split() )
parent = [0] * (v+1)

edges= []
result = 0

# Initialize parent table as themself
for i in range(1, v+1):
    parent[i] = i

# Input every edge information
for _ in range(e):
    a, b, cost = map(int, input().split() )
    # Set first element as cost to sort in the order of cost.
    edges.append((cost, a, b))

# Sort edges
edges.sort()
# Longest distance
last = 0

# Check every edges
for edge in edges:
    cost, a, b = edge
    # Include set if cycle is not occurred
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        last = cost

print( result - last )

"""


7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

8


"""
  

Q3. Curriculum

Peter take online CS lecture. There is N number of lecture and every lecture has number from 1 to N. Some lecture is a prerequisite course. For example, N = 3 and number 1 and number 2 are prerequisite lecture of number 3. Number 1 and 2 doesn’t have prerequisite lecture and lecture time is like these.

• Number 1 lecture : 30 hours
• Number 2 lecture : 20 hours
• Number 3 lecture : 40 hours

Minimum hour for taking number 1 lecture is 30 hours, number 2 lecture is 20 hours and number 3 lecture is 70 hours. Make the program return the minimum hours when given N.

Solution

This question is topology sort question. When check connected node to each nodes, it can find answer by updating table that store long time lecture if it find longer time than current lecture to connected nodes. So use topology sort algorithm and update result table after checking edge information every time.

Minimum hour is in the ‘result’ list which is result table. In the first step, each lecture time is in the ‘time’ list. Copy the values by using ‘deepcopy()’ method and store copied value to ‘result’. It can be problem when simply copy the values in list so it need to use ‘deepcopy()’ method.

from collections import deque
import copy

# Input the number of nodes
v = int(input())

# Initialize indegree to every node as 0
indegree = [0] * ( v+1 )
# Initialize connected list to store edges information
graph = [ [] for i in range(v+1) ]
# Initialize lecture time as 0
time = [0] * (v+1)

# Input every edge information
for i in range(1, v+1):
    data = list(map(int, input().split() ))
    time[i] = data[0]
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

# Topology function
def topology_sort():
    result = copy.deepcopy(time)
    q = deque()
    
    # Insert node indegree is 0 to queue
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)

    # Repeat until queue will be empty
    while q:
        # Put out element from queue
        now = q.popleft()
        # Minus 1 from indegree of connected node with current element
        for i in graph[now]:
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            # Put in updated queue indegree is 0
            if indegree[i] == 0:
                q.append(i)

    # Print result
    for i in range(1, v+1):
        print(result[i])


topology_sort()

"""

5 
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1


10
20
14
18
17


"""

Summary

• Disjoint sets : Find the root node. Set parent node and child node point out parent node.
• Cycle detection by using disjoint sets : Check the each edges and root nodes. If root nodes aren’t same, use union operator
• Spanning Tree : The graph include every nodes and cycle is not exist
• Kruskal algorithm : Choose shortest distance edge. If cycle is not occurred and use union method.
• Topology Sort : Input node that indegree is 0 to queue.