Swift 5中递归构建社交关系图及好友关系排序实现求助

Hey there! Let's tackle your problem step by step. We'll cover building the social graph with all direct/indirect connections, then sorting your friends list by the rules you specified.

First, Let's Fix the Data Parsing #

First, let's make sure we can correctly load your JSON data into an array of User structs. Here's how to do that (assuming your JSON is stored as a string or loaded from a file):

let jsonData = """
[
  { "id": 1, "name": "Me", "friends": [25, 24, 16, 8, 13, 12, 7, 15] },
  { "id": 2, "name": "Anne Emerson", "friends": [3, 21, 4, 20, 24, 5, 7, 12, 18] },
  { "id": 3, "name": "Ashley Hopper", "friends": [2, 22, 10, 20, 25, 11] },
  { "id": 4, "name": "Alba Gates", "friends": [2, 17, 21, 11, 7, 13] },
  { "id": 5, "name": "Louise Pennington", "friends": [2, 23, 22, 15, 20, 24] },
  { "id": 6, "name": "Shields Gilliam", "friends": [26] },
  { "id": 7, "name": "Freida Evans", "friends": [1, 4, 2, 9, 18, 17] },
  { "id": 8, "name": "Noel Serrano", "friends": [1, 24, 18, 9, 16, 11, 23] }
]
""".data(using: .utf8)!

do {
    let users = try JSONDecoder().decode([User].self, from: jsonData)
    // We'll use this users array for the rest of the logic
} catch {
    print("Failed to parse JSON: \(error)")
}

Building the Social Graph with BFS (Better Than Recursion for Distance Tracking) #

Recursion can work, but Breadth-First Search (BFS) is more straightforward here because it naturally tracks the edge distance from you to each user, and avoids infinite loops by keeping track of visited users.

We'll need:

• A dictionary to map user IDs to their created Vertex objects
• A set to track visited users (to avoid duplicate processing)
• A queue to manage the BFS traversal

Assuming your graph object has the methods you mentioned, here's the implementation:

// First, define a helper type to track user data + distance from "Me"
struct TraversalNode {
    let user: User
    let distance: Int
    let parentVertex: Vertex // The vertex of the user who led us to this one
}

// Assume we have our parsed users array, and a graph instance
let users = try JSONDecoder().decode([User].self, from: jsonData)
var idToUser = [Int: User]()
users.forEach { idToUser[$0.id] = $0 }

var idToVertex = [Int: Vertex]()
var visited = Set<Int>()
var idToDistance = [Int: Int]()
let meUser = idToUser[1]!

// Step 1: Create your own vertex
let meVertex = graph.createVertex(data: meUser.name)
idToVertex[1] = meVertex
visited.insert(1)
idToDistance[1] = 0 // Your distance to yourself is 0

// Step 2: Initialize BFS queue with your direct friends
var queue = [TraversalNode]()
meUser.friends.forEach { friendId in
    if let friendUser = idToUser[friendId] {
        let friendVertex = graph.createVertex(data: friendUser.name)
        idToVertex[friendId] = friendVertex
        // Connect you to your direct friend
        graph.add(.undirected, from: meVertex, to: friendVertex, weight: 1)
        visited.insert(friendId)
        idToDistance[friendId] = 1
        queue.append(TraversalNode(user: friendUser, distance: 1, parentVertex: friendVertex))
    }
}

// Step 3: Process the queue to traverse all indirect connections
while !queue.isEmpty {
    let currentNode = queue.removeFirst()
    let currentUser = currentNode.user
    let currentVertex = currentNode.parentVertex
    
    for friendId in currentUser.friends {
        guard !visited.contains(friendId) else { continue }
        
        if let friendUser = idToUser[friendId] {
            let friendVertex = graph.createVertex(data: friendUser.name)
            idToVertex[friendId] = friendVertex
            // Connect current user to their friend
            graph.add(.undirected, from: currentVertex, to: friendVertex, weight: 1)
            visited.insert(friendId)
            idToDistance[friendId] = currentNode.distance + 1
            // Add to queue with incremented distance
            queue.append(TraversalNode(user: friendUser, distance: currentNode.distance + 1, parentVertex: friendVertex))
        }
    }
}

Note on Your Original Code #

Your nested loop had a critical mistake: you used index from enumerated() to filter users by ID, but that index is just the position in the array, not the user's actual ID. You should have used i (the friend ID) instead:

// Your original code had this wrong line:
// let getUserByID = datas.users.filter{ $0.id == index}
// It should be:
let getUserByID = datas.users.filter{ $0.id == i }

Calculating Mutual Friends & Sorting the List #

Now we need to generate a sorted list of all connected users (excluding yourself) with edge distance and mutual friend count.

First, let's create a helper function to calculate mutual friends between two users:

func mutualFriendsCount(between user1: User, and user2: User) -> Int {
    let user1Friends = Set(user1.friends)
    let user2Friends = Set(user2.friends)
    return user1Friends.intersection(user2Friends).count
}

Then, we'll collect all connected users, compute their distance and mutuals, then sort:

// Collect all users except yourself
var friendList = [(user: User, distance: Int, mutuals: Int)]()
for (userId, user) in idToUser {
    guard userId != 1 else { continue }
    guard let distance = idToDistance[userId] else { continue } // Only include connected users
    let mutuals = mutualFriendsCount(between: meUser, and: user)
    friendList.append((user: user, distance: distance, mutuals: mutuals))
}

// Sort the list: first by distance ascending, then by mutuals descending
let sortedFriendList = friendList.sorted {
    if $0.distance != $1.distance {
        return $0.distance < $1.distance
    } else {
        return $0.mutuals > $1.mutuals
    }
}

// Print the sorted list like your example
for entry in sortedFriendList {
    if entry.mutuals > 0 {
        print("\(entry.user.name) - edge distance: \(entry.distance), Mutual friends: \(entry.mutuals)")
    } else {
        print("\(entry.user.name) - edge Distance: \(entry.distance)")
    }
}

Putting It All Together #

Combine all the code blocks, and you'll have a complete solution that builds the graph, traverses all connected users, and outputs the sorted friend list as requested.

内容的提问来源于stack exchange，提问作者Hussein