1 朋友关系处理
兴趣爱好圈子：有一群人，每个人都有自己的兴趣爱好。找到两个人之间是否存在共同的兴趣爱好路径，即他们是否通过一些共同的兴趣或朋友相互认识。其中每个人是一个节点，而他们的兴趣爱好是图中的边。例如:A,B,C都爱好汽车模型，A和B是，B和C是，B就可以引荐A和C也成为朋友。
用户关系：假设有一组用户，每个用户都有一个唯一的标识符。用户之间可以建立兴趣爱好朋友关系，这些关系可以是双向的，即如果用户A是用户B的兴趣爱好朋友，那么用户B也是用户A的兴趣爱好朋友。
朋友关系的应用： 这个问题的解决方案可能用于查找两个用户之间是否存在某种兴趣爱好，或者用于推荐朋友，比如找到共同的朋友或朋友的朋友。这样的网络可以用于表示现实生活中的社交媒体平台，如QQ，微信等。
2 核心代码
用户结构：
表示具有整数 ID （） 和指向链表中下一个用户 （） 的指针的用户。
深度优先搜索具体代码：
广度优先搜索具体代码：
4 测试样例
是朋友的样例
我们设立了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是否为朋友
5 算法优缺点
深度优先搜索 （DFS）
优势：
内存效率：与广度优先搜索相比，它通常需要更少的内存，因为它使用递归并在回溯之前尽可能深入地遍历。
弊端：
完整性：在检查较短的分支之前，它可能会卡在探索较长的分支。
非最优性：DFS 不保证找到最短路径，DFS 找到的解决方案可能不是最佳解决方案。
广度优先搜索 （BFS）
优势：
最优：BFS 保证在未加权图中找到最短路径。
完整性：BFS是完整的;如果存在解决方案，它会找到解决方案。
弊端：
空间复杂度：BFS 会消耗大量内存，尤其是对于宽图或使用邻接矩阵时。
实现复杂性：由于使用了队列，实现 BFS 可能比 DFS 更复杂。
6 附件之源代码
//深度优先搜索（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;
}
