C++ Coding Test Course, Kevin Bacon’s Six Degrees of Separation

Introduction

The Kevin Bacon rule of six degrees states that any person is connected to Kevin Bacon within a maximum of six degrees. This is an intriguing concept that explains relationships in social networks and is a popular topic in various fields. In this article, we will transform this rule into an algorithmic problem and detail the solution process using C++.

The problem we will tackle is “Finding the person who can reach Kevin Bacon the fastest.” Through research, we will calculate the degree of connection to Kevin Bacon for each person when given the friendship relations among several people.

Problem Definition

The objective is to calculate each person’s Kevin Bacon number within a given network and find the person with the lowest number. To do this, we need to input the number of people and their friendship relations.

Problem Description

The input is provided in the following format:

• The first line contains the number of people N (1 ≤ N ≤ 100)
• From the second line onward, each line consists of two integers A, B representing the friendship relation (A and B are friends).

The output should be the number of the person closest to Kevin Bacon. If there are multiple, output the smallest number.

Problem Solving Approach

To solve this problem, we will use graph traversal techniques. We will treat people as vertices and friendships as edges, applying BFS (Breadth-First Search). We will calculate the shortest distance from each person to Kevin Bacon and find the minimum among them.

Algorithm

1. Construct the graph as an adjacency list based on the input.
2. Calculate each person’s Kevin Bacon number using BFS.
3. Compare the calculated Kevin Bacon numbers to find the minimum.

C++ Implementation

Now, let’s implement the C++ code based on the algorithm above.

#include <iostream>
#include <vector>
#include <queue>
#include <limits> 
using namespace std;

int main() {
    int N, M;
    cin >> N >> M; // Number of people N, number of friendship relations M
    vector<vector<int>> graph(N + 1); // Adjacency list

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // Friendship relation A, B
        graph[A].push_back(B);
        graph[B].push_back(A); // Undirected graph
    }

    int min_bacon = numeric_limits<int>::max();
    int answer = 0;

    for (int i = 1; i <= N; i++) {
        vector<int> distance(N + 1, -1); // Initialize distances for each person
        queue<int> q;
        distance[i] = 0; // Distance from self is 0
        q.push(i); // Add self to the queue

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            for (int neighbor : graph[current]) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[current] + 1; // Calculate distance
                    q.push(neighbor); // Add friend to explore
                }
            }
        }

        int bacon_count = 0;
        for (int d : distance) {
            if (d != -1) {
                bacon_count += d; // Sum Kevins Bacon numbers
            }
        }

        if (bacon_count < min_bacon) {
            min_bacon = bacon_count; // Update minimum
            answer = i; // Record person number
        }
    }

    cout << answer << endl; // Output result
    return 0;
}
            

Code Explanation

The above C++ code includes the following key steps:

1. Input Processing: Read N and M, and store friendship relations in an adjacency list format.
2. BFS Implementation: Perform BFS for each person to calculate distances.
3. Result Calculation: Update the Kevin Bacon number based on calculated distances and ultimately find the minimum.

Complexity Analysis

The time complexity of this algorithm is O(N + M). This is because each person explores their friends through BFS, and each edge is explored only once. This is sufficiently efficient for the input range of the given problem.

Conclusion

In this lecture, we explored how to solve an algorithm problem utilizing the Kevin Bacon rule of six degrees in C++. We analyzed relationships within a network using graph traversal techniques like BFS. Such types of problems frequently appear in coding tests, making it crucial to practice varied problems to enhance proficiency.

Finally, the problem-solving process presented here will not only aid in preparation for coding tests but also help address various issues that may arise in actual programming more systematically.