数据结构之朋友关系处理

兴趣爱好圈子：有一群人，每个人都有自己的兴趣爱好。找到两个人之间是否存在共同的兴趣爱好路径，即他们是否通过一些共同的兴趣或朋友相互认识。其中每个人是一个节点，而他们的兴趣爱好是图中的边。例如:A,B,C都爱好汽车模型，A和B是，B和C是，B就可以引荐A和C也成为朋友。

用户关系：假设有一组用户，每个用户都有一个唯一的标识符。用户之间可以建立兴趣爱好朋友关系，这些关系可以是双向的，即如果用户A是用户B的兴趣爱好朋友，那么用户B也是用户A的兴趣爱好朋友。

朋友关系的应用： 这个问题的解决方案可能用于查找两个用户之间是否存在某种兴趣爱好，或者用于推荐朋友，比如找到共同的朋友或朋友的朋友。这样的网络可以用于表示现实生活中的社交媒体平台，如QQ，微信等。

1. 深度优先搜索（DFS）

实现步骤：

1. 标记访问过的节点：在DFS过程中，需要标记已经访问过的节点，防止重复访问，避免陷入死循环。

2. 递归搜索：从一个用户节点开始，递归地访问其相邻的朋友节点，直到找到目标用户或者遍历完整个图。

3. 路径记录： 在搜索的过程中，记录访问的路径，以便后续查询。

在下面的具体代码中，我们设立了5个人，分别用0，1，2，3，4，5表示，0和1是朋友，1和2是朋友，1和3是朋友，3和4是朋友，3和5是朋友，用代码实现0和4是否为朋友，下面是深度优先搜索的数学建模（其中箭头表示可能查找的一种顺序）：

1. 广度优先搜索（BFS）

实现步骤：

1. 队列： 使用队列来保存待访问的节点，保证按照层级顺序进行访问。

2. 标记访问过的节点：在BFS过程中，同样需要标记已经访问过的节点。

3. 路径记录： 在搜索的过程中，记录访问的路径，以便后续查询。

下面是深度优先搜索的数学建模：

下面是广度优先搜索的数学建模（其中箭头表示可能查找的一种顺序）：

用户结构：

表示具有整数 ID （） 和指向链表中下一个用户 （） 的指针的用户。

LinkedList 类：管理用户链表。

提供使用 DFS 添加用户、添加好友关系以及检查两个用户是否为好友的方法。

addUser（int userId）：

将用户添加到链表。

addFriendship（int userId1， int userId2）：

在两个用户之间添加友谊（双向）。

addUserToFriendList（int userId， int friendId）：

将好友添加到用户的好友列表中。

areFriends（int userId1， int userId2）：

启动 DFS 以检查两个用户是否为好友。

areFriendsBFS（int startUserId， int targetUserId）：

启动BFS检查两个用户是否为好友。

深度优先搜索具体代码：

广度优先搜索具体代码：

是朋友的样例

我们设立了5个人，分别用0，1，2，3，4，5表示，0和1是朋友，1和2是朋友，1和3是朋友，3和4是朋友，3和5是朋友，用代码实现0和4是否为朋友

不是朋友的样例

我们设立了5个人，分别用0，1，2，3，4，5表示，0和1是朋友，0和2是朋友，1和2是朋友，3和4是朋友，用代码实现0和4是否为朋友

深度优先搜索 （DFS）

优势：

??? 内存效率：与广度优先搜索相比，它通常需要更少的内存，因为它使用递归并在回溯之前尽可能深入地遍历。

弊端：

??? 完整性：在检查较短的分支之前，它可能会卡在探索较长的分支。

??? 非最优性：DFS 不保证找到最短路径，DFS 找到的解决方案可能不是最佳解决方案。

广度优先搜索 （BFS）

优势：

??? 最优：BFS 保证在未加权图中找到最短路径。

??? 完整性：BFS是完整的;如果存在解决方案，它会找到解决方案。

弊端：

??? 空间复杂度：BFS 会消耗大量内存，尤其是对于宽图或使用邻接矩阵时。

??? 实现复杂性：由于使用了队列，实现 BFS 可能比 DFS 更复杂。

//深度优先搜索（DFS）

#include <iostream>

#include <unordered_set>

using namespace std;

// 定义用户结构体

struct User {

? ? int id;

? ? User* next;

? ? User(int _id) : id(_id), next(nullptr) {}

};

// 定义链表类

class LinkedList {

public:

? ? User* head;

? ? LinkedList() : head(nullptr) {}

? ? // 向链表中添加用户

? ? void addUser(int userId) {

? ? ? ? User* newUser = new User(userId);

? ? ? ? newUser->next = head;

? ? ? ? head = newUser;

? ? }

? ? // 添加朋友关系

? ? void addFriendship(int userId1, int userId2) {

? ? ? ? addUserToFriendList(userId1, userId2);

? ? ? ? addUserToFriendList(userId2, userId1);

? ? }

? ? // 判断用户是否是朋友

? ? bool areFriends(int userId1, int userId2) {

? ? ? ? unordered_set<int> visited;

? ? ? ? return areFriendsDFS(userId1, userId2, visited);

? ? }

private:

? ? // 将用户添加到朋友列表

? ? void addUserToFriendList(int userId, int friendId) {

? ? ? ? User* curr = head;

? ? ? ? while (curr != nullptr && curr->id != userId) {

? ? ? ? ? ? curr = curr->next;

? ? ? ? }

? ? ? ? if (curr != nullptr) {

? ? ? ? ? ? User* newFriend = new User(friendId);

? ? ? ? ? ? newFriend->next = curr->next;

? ? ? ? ? ? curr->next = newFriend;

? ? ? ? }

? ? }

? ? // 深度优先搜索判断用户是否是朋友

? ? bool areFriendsDFS(int currUserId, int targetUserId, unordered_set<int>& visited) {

? ? ? ? visited.insert(currUserId);

? ? ? ? User* curr = head;

? ? ? ? while (curr != nullptr && curr->id != currUserId) {

? ? ? ? ? ? curr = curr->next;

? ? ? ? }

? ? ? ? if (curr != nullptr) {

? ? ? ? ? ? User* friendCurr = curr->next;

? ? ? ? ? ? while (friendCurr != nullptr) {

? ? ? ? ? ? ? ? if (friendCurr->id == targetUserId) {

? ? ? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (visited.find(friendCurr->id) == visited.end()) {

? ? ? ? ? ? ? ? ? ? if (areFriendsDFS(friendCurr->id, targetUserId, visited)) {

? ? ? ? ? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? friendCurr = friendCurr->next;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return false;

? ? }

};

int main() {

? ? LinkedList userList;

? ? // 添加用户

? ? for (int i = 0; i < 5; ++i) {

? ? ? ? userList.addUser(i);

? ? }

? ? // 添加朋友关系

// ? ?userList.addFriendship(0, 1);

// ? ?userList.addFriendship(1, 2);

// ? ?userList.addFriendship(1, 3);

// ? ?userList.addFriendship(3, 4);

// ? ?userList.addFriendship(3, 5);

? ? userList.addFriendship(0, 1);

? ? userList.addFriendship(0, 2);

? ? userList.addFriendship(1, 2);

? ? userList.addFriendship(3, 4);

? ? // 判断用户关系

? ? int userId1 = 0;

? ? int userId2 = 4;

? ? cout<<"深度优先搜索的结果："<<endl;

? ? if (userList.areFriends(userId1, userId2)) {

? ? ? ? cout << "用户" << userId1 << "和用户" << userId2 << "是朋友。" << endl;

? ? } else {

? ? ? ? cout << "用户" << userId1 << "和用户" << userId2 << "不是朋友。" << endl;

? ? }

? ? return 0;

}

//广度优先搜索（BFS）

#include <iostream>

#include <unordered_set>

#include <queue>

using namespace std;

// 定义用户结构体

struct User {

? ? int id;

? ? User* next;

? ? User(int _id) : id(_id), next(nullptr) {}

};

// 定义链表类

class LinkedList {

public:

? ? User* head;

? ? LinkedList() : head(nullptr) {}

? ? // 向链表中添加用户

? ? void addUser(int userId) {

? ? ? ? User* newUser = new User(userId);

? ? ? ? newUser->next = head;

? ? ? ? head = newUser;

? ? }

? ? // 添加朋友关系

? ? void addFriendship(int userId1, int userId2) {

? ? ? ? addUserToFriendList(userId1, userId2);

? ? ? ? addUserToFriendList(userId2, userId1);

? ? }

? ? // 判断用户是否是朋友

? ? bool areFriends(int userId1, int userId2) {

? ? ? ? return areFriendsBFS(userId1, userId2);

? ? }

private:

? ? // 将用户添加到朋友列表

? ? void addUserToFriendList(int userId, int friendId) {

? ? ? ? User* curr = head;

? ? ? ? while (curr != nullptr && curr->id != userId) {

? ? ? ? ? ? curr = curr->next;

? ? ? ? }

? ? ? ? if (curr != nullptr) {

? ? ? ? ? ? User* newFriend = new User(friendId);

? ? ? ? ? ? newFriend->next = curr->next;

? ? ? ? ? ? curr->next = newFriend;

? ? ? ? }

? ? }

? ? // 广度优先搜索判断用户是否是朋友

? ? bool areFriendsBFS(int startUserId, int targetUserId) {

? ? ? ? unordered_set<int> visited;

? ? ? ? queue<int> bfsQueue;

? ? ? ? bfsQueue.push(startUserId);

? ? ? ? visited.insert(startUserId);

? ? ? ? while (!bfsQueue.empty()) {

? ? ? ? ? ? int currUserId = bfsQueue.front();

? ? ? ? ? ? bfsQueue.pop();

? ? ? ? ? ? User* curr = head;

? ? ? ? ? ? while (curr != nullptr && curr->id != currUserId) {

? ? ? ? ? ? ? ? curr = curr->next;

? ? ? ? ? ? }

? ? ? ? ? ? if (curr != nullptr) {

? ? ? ? ? ? ? ? User* friendCurr = curr->next;

? ? ? ? ? ? ? ? while (friendCurr != nullptr) {

? ? ? ? ? ? ? ? ? ? int friendId = friendCurr->id;

? ? ? ? ? ? ? ? ? ? if (friendId == targetUserId) {

? ? ? ? ? ? ? ? ? ? ? ? return true;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? if (visited.find(friendId) == visited.end()) {

? ? ? ? ? ? ? ? ? ? ? ? bfsQueue.push(friendId);

? ? ? ? ? ? ? ? ? ? ? ? visited.insert(friendId);

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? friendCurr = friendCurr->next;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return false;

? ? }

};

int main() {

? ? LinkedList userList;

? ? // 添加用户

? ? for (int i = 0; i < 5; ++i) {

? ? ? ? userList.addUser(i);

? ? }

? ? // 添加朋友关系

// ? ?userList.addFriendship(0, 1);

// ? ?userList.addFriendship(1, 2);

// ? ?userList.addFriendship(1, 3);

// ? ?userList.addFriendship(3, 4);

// ? ?userList.addFriendship(3, 5);

? ? userList.addFriendship(0, 1);

? ? userList.addFriendship(0, 2);

? ? userList.addFriendship(1, 2);

? ? userList.addFriendship(3, 4);

? ? // 判断用户关系

? ? int userId1 = 0;

? ? int userId2 = 4;

? ? cout<<"广度优先搜索的结果："<<endl;

? ? if (userList.areFriends(userId1, userId2)) {

? ? ? ? cout << "用户" << userId1 << "和用户" << userId2 << "是朋友。" << endl;

? ? } else {

? ? ? ? cout << "用户" << userId1 << "和用户" << userId2 << "不是朋友。" << endl;

? ? }

? ? return 0;

}