COMP2521 Week 5 - Graphs & Social Networks

📊 Graph Basics 📊 图论基础

A graph is a collection of vertices (nodes) connected by edges (links). 图是由顶点（节点）通过边（链接）连接而成的集合。

Key Components:关键组成部分：

Vertices (V): The entities (e.g., people in a social network)顶点 (V)：实体（如社交网络中的人）
Edges (E): Connections between vertices (e.g., friendships)边 (E)：顶点之间的连接（如好友关系）

Graph Representation 图的表示

Friendbook uses:Friendbook 使用：

Adjacency List: Array of linked lists邻接表：链表数组
Map ADT: Maps names (strings) to vertex IDs (integers)Map ADT：将名字（字符串）映射到顶点 ID（整数）
Undirected Graph: Friendships go both ways无向图：好友关系是双向的

Friendbook Structure: names[0] = "Harry" → adj[0] → [1] → [2] → NULL (Harry's friends: Ron, Hermione) names[1] = "Ron" → adj[1] → [0] → [2] → NULL (Ron's friends: Harry, Hermione) names[2] = "Hermione" → adj[2] → [0] → [1] → NULL (Hermione's friends: Harry, Ron) Map: "Harry" → 0, "Ron" → 1, "Hermione" → 2

🛠️ Lab 05 Tasks 🛠️ 实验 05 任务

TASK 1 FbFriend — Add Friendship FbFriend — 添加好友

Add a bidirectional friendship between two people. Must maintain sorted order in adjacency lists.在两个人之间添加双向好友关系。必须保持邻接表的升序。

⚠️ Key Points:关键点：

Check if already friends (use inAdjList)检查是否已是好友（使用 inAdjList）
Insert into BOTH adjacency lists (bidirectional!)插入到两个邻接表中（双向！）
Maintain ascending order in linked list保持链表升序

bool FbFriend(Fb fb, char *name1, char *name2) {
    int id1 = nameToId(fb, name1);
    int id2 = nameToId(fb, name2);

    if (inAdjList(fb->adj[id1], id2)) return false;

    // Insert id2 into id1's list (sorted)
    // ... insertion code ...

    // Insert id1 into id2's list (sorted) - MUST DO BOTH!
    // ... insertion code ...

    return true;
}

TASK 2 FbNumFriends — Count Friends FbNumFriends — 统计好友数

Traverse the adjacency list and count nodes.遍历邻接表并统计节点数。

int FbNumFriends(Fb fb, char *name) {
    int id = nameToId(fb, name);
    struct adjNode *curr = fb->adj[id];
    int count = 0;
    while (curr != NULL) {  // Note: curr != NULL, not curr->next
        count++;
        curr = curr->next;
    }
    return count;
}

TASK 3 FbMutualFriends — Find Common Friends FbMutualFriends — 找共同好友

Find people who are friends with BOTH person1 AND person2.找出同时是 person1 和 person2 好友的人。

List FbMutualFriends(Fb fb, char *name1, char *name2) {
    int id1 = nameToId(fb, name1);
    int id2 = nameToId(fb, name2);
    List l = ListNew();

    struct adjNode *curr = fb->adj[id1];
    while (curr != NULL) {
        if (inAdjList(fb->adj[id2], curr->v)) {
            ListAppend(l, fb->names[curr->v]);  // Convert ID to name!
        }
        curr = curr->next;
    }
    return l;
}

TASK 4 FbUnfriend — Remove Friendship FbUnfriend — 删除好友

Remove a bidirectional friendship. Use two pointers (prev, curr) to delete from linked list.删除双向好友关系。使用双指针（prev, curr）从链表中删除。

⚠️ Common Mistakes:常见错误：

Forgetting to delete from BOTH lists忘记从两个列表中删除
Not handling head node deletion specially没有特殊处理头节点删除
Forgetting to free(curr)忘记 free(curr)

// Delete from linked list
struct adjNode *curr = fb->adj[id];
struct adjNode *prev = NULL;

while (curr != NULL && curr->v != targetId) {
    prev = curr;
    curr = curr->next;
}

if (prev == NULL) {
    fb->adj[id] = curr->next;  // Delete head
} else {
    prev->next = curr->next;   // Delete middle/tail
}
free(curr);

TASK 5 FbFriendRecs1 — Friend Recommendations FbFriendRecs1 — 好友推荐

Recommend friends based on number of mutual friends. Sort by count (descending).基于共同好友数推荐好友。按数量排序（降序）。

Algorithm:算法：

Count mutual friends for each "friend of friend"统计每个"朋友的朋友"的共同好友数
Exclude: self + already friends排除：自己 + 已是好友
Sort by count (Selection Sort or qsort)按数量排序（选择排序或 qsort）
Fill recs array and return count填入 recs 数组并返回数量

⏱️ Time Complexity ⏱️ 时间复杂度

Function函数	Worst Case最坏情况	Explanation解释
FbFriend	O(n)	nameToId O(log n) + inAdjList O(n) + insert O(n)nameToId O(log n) + inAdjList O(n) + 插入 O(n)
FbNumFriends	O(n)	Traverse adjacency list (max n-1 friends)遍历邻接表（最多 n-1 个好友）
FbMutualFriends	O(n²)	For each friend O(n), check inAdjList O(n)对每个好友 O(n)，检查 inAdjList O(n)
FbUnfriend	O(n)	Find and delete from both lists O(n) each从两个列表中查找并删除各 O(n)
FbFriendRecs1	O(n²)	Count mutual O(n²) + Selection Sort O(n²)统计共同好友 O(n²) + 选择排序 O(n²)

💡 Key Insights 💡 关键洞察

Bidirectional Operations双向操作

Friendship is undirected — always modify BOTH adjacency lists!好友关系是无向的 — 始终修改两个邻接表！

Linked List Operations链表操作

Insert sorted: Handle 3 cases — empty, insert head, insert middle/tail有序插入：处理 3 种情况 — 空、插头、插中间/尾
Delete: Use prev + curr pointers, handle head specially删除：使用 prev + curr 指针，特殊处理头节点

ID ↔ Name ConversionID ↔ 名字转换

Name → ID: nameToId(fb, name) using Map (O(log n))名字 → ID：使用 Map 调用 nameToId(fb, name) (O(log n))
ID → Name: fb->names[id] (O(1))ID → 名字：fb->names[id] (O(1))