Python coding test course, Six Degrees of Kevin Bacon

Hello! Today we will learn about one of the frequently asked algorithm problems in coding tests called the “Kevin Bacon’s Six Degrees of Separation.” This problem can be solved by utilizing various concepts from graph theory and offers a great opportunity to practice basic search algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS).

1. Problem Description

Kevin Bacon’s Six Degrees of Separation is a famous social network theory stating that there is a connection through relationships between any two people within six steps. This is a problem to implement this theory in code.

The problem is as follows:

Given N users and the relationships between them,
calculate the Kevin Bacon score for each user,
and output the user with the lowest score.
The score is the sum of the shortest distances to that user.

2. Input Format

The first line contains the number of users N (1 ≤ N ≤ 100) and the number of relationships M (0 ≤ M ≤ 4,900).

The next M lines contain two integers a and b, indicating that users a and b are friends with each other.

3. Output Format

Print the number of the user with the lowest Kevin Bacon score. In case of a tie, print the user with the smallest number.

4. Problem Solving Process

To solve this problem, follow these steps:

4.1. Graph Creation

First, create a graph representing each user’s friendships in the form of an adjacency list. This graph can be represented using a dictionary or list.

graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

4.2. Implement BFS or DFS

For each user, calculate the shortest distance to other users using BFS or DFS. Since BFS guarantees the shortest path, it is more suitable for this problem.

def bfs(start, graph):
    queue = [start]
    visited = {start: 0}
    
    while queue:
        current = queue.pop(0)
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)
    return sum(visited.values())

4.3. Score Calculation

Calculate the Kevin Bacon score for all users. Use the BFS results to store the scores and find the lowest score.

min_score = float('inf')
user_with_min_score = -1
for user in range(1, N + 1):
    score = bfs(user, graph)
    if score < min_score:
        min_score = score
        user_with_min_score = user
    elif score == min_score:
        user_with_min_score = min(user_with_min_score, user)

5. Full Code

Now, let's write the full code that integrates the above processes.

from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = {start: 0}
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)
    return sum(visited.values())

def find_kevin_bacon(graph, n):
    min_score = float('inf')
    user_with_min_score = -1
    
    for user in range(1, n + 1):
        score = bfs(user, graph)
        if score < min_score:
            min_score = score
            user_with_min_score = user
        elif score == min_score:
            user_with_min_score = min(user_with_min_score, user)
    
    return user_with_min_score

# Input
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# Output result
result = find_kevin_bacon(graph, N)
print(result)

6. Code Explanation

The code takes input values for N and M, constructs a graph based on friendships, and then calculates the Kevin Bacon score for each user using BFS. Finally, it outputs the number of the user with the lowest score. This problem provides a great practice for understanding graph theory and the BFS algorithm.

7. Performance Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices (users) and E is the number of edges (relationships). Assuming N is 100, the worst-case scenario could have 4900 relationships, resulting in approximately 495,000 searches during 100 BFS calls. This is within a range that can be sufficiently handled within the given time.

8. Conclusion

This problem utilizing Kevin Bacon's Six Degrees of Separation provides a good opportunity to solidify the fundamentals of graph theory and learn how to apply BFS. Practicing various variations of this problem can further enhance your algorithmic thinking. We wish you continued success in preparing for coding tests through diverse problem-solving!

Thank you!