Java Coding Test Course, Kevin Bacon's Six Degrees of Separation

Hello! In this post, we will explore the ‘Six Degrees of Kevin Bacon’ using Java. This law, derived from social network theory, suggests that any two people can be connected in six steps or less. We will transform this into an algorithm problem and implement it.

Problem Description

The problem we need to solve is as follows. Based on the given friendships represented as a graph, we need to find the shortest path between two specific people. By calculating the “Kevin Bacon Index” according to how connected these people are, we will discover who is connected to whom.

Problem Definition

When given a list of friendships, write an algorithm to calculate the ‘Kevin Bacon Index’ for all people and find the person with the lowest index to print.

Input Format

The first line contains the number of people N (1 ≤ N ≤ 1000).
The next line contains the number of friendships M (0 ≤ M ≤ 100,000).
Then, M lines follow with two numbers A, B (1 ≤ A, B ≤ N) representing friendships. This means A and B are friends.

Output Format

Calculate the Kevin Bacon Index for all people and print the number of the person with the lowest value. If two people have the same Kevin Bacon Index, print the one with the smaller number.

Problem Solving Process

To solve this problem, we will follow the steps below:

Step 1: Graph Implementation

Friendships can be represented in the form of a graph. Each person is a vertex, and the friendships between two people are represented as edges. Here, we will implement the graph using an adjacency list.


import java.util.*;

public class KevinBaconGame {
    static List> graph;
    static int[] distance;

    public static void main(String[] args) {
        // Here, we will handle input and initialize the graph.
    }
}

Step 2: Implementing BFS Algorithm

We will use BFS to calculate the Kevin Bacon Index. BFS is very effective in finding the shortest path. By running BFS from each person, we can calculate the shortest paths to all friends.


    static int bfs(int start) {
        Queue queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        queue.offer(start);
        visited[start] = true;
        distance[start] = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        int totalDistance = 0;
        for (int d : distance) {
            totalDistance += d;
        }
        return totalDistance;
    }

Step 3: Result Calculation and Output

Run BFS for all people, calculate the Kevin Bacon Index, and finally find the person with the lowest index. During this process, store and compare the person number and index.


    for (int i = 1; i <= N; i++) {
        int baconIndex = bfs(i);
        // Here, we will add logic to store the Kevin Bacon Index.
    }
    // Final result output part.

View Full Code


import java.util.*;

public class KevinBaconGame {
    static List> graph;
    static int[] distance;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        
        graph = new ArrayList<>();
        distance = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            graph.get(A).add(B);
            graph.get(B).add(A);
        }

        int minBaconIndex = Integer.MAX_VALUE;
        int resultPerson = 0;

        for (int i = 1; i <= N; i++) {
            int baconIndex = bfs(i);
            if (baconIndex < minBaconIndex) {
                minBaconIndex = baconIndex;
                resultPerson = i;
            }
        }

        System.out.println(resultPerson);
    }

    static int bfs(int start) {
        Queue queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        queue.offer(start);
        visited[start] = true;
        distance[start] = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        int totalDistance = 0;
        for (int d : distance) {
            totalDistance += d;
        }
        return totalDistance;
    }
}

Conclusion

In this post, we implemented an algorithm to check the relationships among friends based on Kevin Bacon's Six Degrees theory and to find the closest person using the Kevin Bacon Index. We learned how to effectively calculate the shortest path using BFS and navigate through the friendship graph. To gain deeper insights into solving coding test problems using Java, I recommend attempting similar algorithmic problems multiple times.

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