邻接表 - 元素码农

发布时间: 2025-03-21 18:54

↑

# 邻接表

邻接表（Adjacency List）是一种用于表示图的数据结构，它使用一个数组（或链表）来存储图中所有顶点，每个顶点的相邻顶点则用一个链表来存储。这种结构特别适合表示稀疏图（边数远小于顶点数的平方）。

## 基本概念

1. 无向图的邻接表：
   - 每个顶点存储其所有相邻顶点
   - 每条边在两个顶点的链表中都有记录

2. 有向图的邻接表：
   - 每个顶点只存储其出边指向的顶点
   - 每条边只在起点顶点的链表中记录

3. 带权图的邻接表：
   - 链表节点同时存储顶点和边的权重
   - 可以方便地获取边的权重信息

## 图示演示

```
无向图示例：
    0 -- 1
    |    |
    2 -- 3

对应的邻接表：
0 -> 1 -> 2
1 -> 0 -> 3
2 -> 0 -> 3
3 -> 1 -> 2

有向图示例：
    0 -> 1
    |    |
    v    v
    2 <- 3

对应的邻接表：
0 -> 1 -> 2
1 -> 3
2
3 -> 2
```

## 代码实现

### 基本实现

```python
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
    
    def add_edge(self, v1, v2):
        """添加无向图的边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            self.graph[v1].append(v2)
            self.graph[v2].append(v1)  # 无向图需要添加两次
    
    def remove_edge(self, v1, v2):
        """删除无向图的边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            if v2 in self.graph[v1]:
                self.graph[v1].remove(v2)
            if v1 in self.graph[v2]:
                self.graph[v2].remove(v1)
    
    def print_graph(self):
        """打印邻接表"""
        for i in range(self.V):
            print(f"{i} ->", end=" ")
            print(" -> ".join(map(str, self.graph[i])))

# 使用示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print("邻接表表示:")
g.print_graph()
```

### 有向图实现

```python
class DirectedGraph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
    
    def add_edge(self, from_v, to_v):
        """添加有向边"""
        if 0 <= from_v < self.V and 0 <= to_v < self.V:
            self.graph[from_v].append(to_v)
    
    def remove_edge(self, from_v, to_v):
        """删除有向边"""
        if 0 <= from_v < self.V and 0 <= to_v < self.V:
            if to_v in self.graph[from_v]:
                self.graph[from_v].remove(to_v)
    
    def has_path(self, from_v, to_v):
        """检查两点之间是否有直接路径"""
        return to_v in self.graph[from_v]
    
    def get_out_degree(self, vertex):
        """获取顶点的出度"""
        return len(self.graph[vertex])
    
    def get_in_degree(self, vertex):
        """获取顶点的入度"""
        count = 0
        for v in range(self.V):
            if vertex in self.graph[v]:
                count += 1
        return count

# 使用示例
dg = DirectedGraph(4)
dg.add_edge(0, 1)
dg.add_edge(0, 2)
dg.add_edge(1, 3)
dg.add_edge(3, 2)

print(f"顶点0的出度: {dg.get_out_degree(0)}")
print(f"顶点2的入度: {dg.get_in_degree(2)}")
```

### 带权图实现

```python
class WeightedGraph:
    class Edge:
        def __init__(self, vertex, weight):
            self.vertex = vertex
            self.weight = weight
        
        def __str__(self):
            return f"({self.vertex}, {self.weight})"
    
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
    
    def add_edge(self, v1, v2, weight):
        """添加带权边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            self.graph[v1].append(self.Edge(v2, weight))
            self.graph[v2].append(self.Edge(v1, weight))  # 无向图
    
    def get_weight(self, v1, v2):
        """获取边的权重"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            for edge in self.graph[v1]:
                if edge.vertex == v2:
                    return edge.weight
        return float('inf')
    
    def get_neighbors(self, vertex):
        """获取顶点的所有邻居及权重"""
        return [(edge.vertex, edge.weight) for edge in self.graph[vertex]]

# 使用示例
wg = WeightedGraph(4)
wg.add_edge(0, 1, 4)
wg.add_edge(0, 2, 2)
wg.add_edge(1, 2, 1)
wg.add_edge(2, 3, 3)

print("顶点2的邻居及权重:")
for vertex, weight in wg.get_neighbors(2):
    print(f"到顶点{vertex}的权重: {weight}")
```

## 性能分析

### 空间复杂度

- O(V + E)，其中V是顶点数，E是边数
- 对于稀疏图非常高效
- 对于稠密图不如邻接矩阵

### 时间复杂度

1. 基本操作：
   - 添加边：O(1)
   - 删除边：O(degree(v))
   - 查找边：O(degree(v))
   - 获取顶点的所有邻居：O(1)

2. 常见算法中的应用：
   - 图的遍历：O(V + E)
   - 最短路径：O((V + E)log V)（使用优先队列）
   - 拓扑排序：O(V + E)

## 优缺点

### 优点

1. 空间效率高，特别适合稀疏图
2. 容易找到顶点的所有邻居
3. 添加顶点操作简单
4. 适合图的遍历操作

### 缺点

1. 查找特定边的效率较低
2. 删除边操作较慢
3. 对于稠密图，空间占用可能超过邻接矩阵

## 应用场景

1. 社交网络
2. 网络路由
3. 地图导航
4. 推荐系统

## 实际应用示例

### 1. 社交网络好友推荐

```python
class SocialNetwork:
    def __init__(self):
        self.users = {}
    
    def add_user(self, user_id, name):
        """添加用户"""
        if user_id not in self.users:
            self.users[user_id] = {
                'name': name,
                'friends': set()
            }
    
    def add_friendship(self, user1, user2):
        """添加好友关系"""
        if user1 in self.users and user2 in self.users:
            self.users[user1]['friends'].add(user2)
            self.users[user2]['friends'].add(user1)
    
    def get_friends(self, user_id):
        """获取用户的直接好友"""
        if user_id in self.users:
            return self.users[user_id]['friends']
        return set()
    
    def recommend_friends(self, user_id, max_recommendations=5):
        """推荐好友"""
        if user_id not in self.users:
            return []
        
        # 获取用户的好友集合
        direct_friends = self.get_friends(user_id)
        
        # 统计二度好友
        friend_scores = {}
        for friend in direct_friends:
            for friend_of_friend in self.get_friends(friend):
                if friend_of_friend != user_id and \
                   friend_of_friend not in direct_friends:
                    friend_scores[friend_of_friend] = \
                        friend_scores.get(friend_of_friend, 0) + 1
        
        # 排序并返回推荐结果
        recommendations = sorted(
            friend_scores.items(),
            key=lambda x: (-x[1], self.users[x[0]]['name'])
        )
        
        return [
            {
                'user_id': user_id,
                'name': self.users[user_id]['name'],
                'common_friends': score
            }
            for user_id, score in recommendations[:max_recommendations]
        ]

# 使用示例
network = SocialNetwork()

# 添加用户
users = [
    (1, "Alice"), (2, "Bob"), (3, "Charlie"),
    (4, "David"), (5, "Eve"), (6, "Frank")
]
for user_id, name in users:
    network.add_user(user_id, name)

# 添加好友关系
friendships = [
    (1, 2), (1, 3), (2, 3), (2, 4),
    (3, 4), (4, 5), (5, 6)
]
for user1, user2 in friendships:
    network.add_friendship(user1, user2)

# 为用户1推荐好友
user_id = 1
print(f"为用户{user_id}推荐好友:")
for rec in network.recommend_friends(user_id):
    print(f"{rec['name']} (共同好友: {rec['common_friends']})")
```

### 2. 路由网络分析

```python
class NetworkRouter:
    def __init__(self):
        self.routers = {}
        self.connections = {}
    
    def add_router(self, router_id, name):
        """添加路由器"""
        self.routers[router_id] = name
        self.connections[router_id] = {}
    
    def add_connection(self, router1, router2, bandwidth, latency):
        """添加连接"""
        if router1 in self.routers and router2 in self.routers:
            self.connections[router1][router2] = {
                'bandwidth': bandwidth,
                'latency': latency
            }
            self.connections[router2][router1] = {
                'bandwidth': bandwidth,
                'latency': latency
            }
    
    def find_best_path(self, source, destination):
        """使用Dijkstra算法找到最佳路径"""
        import heapq
        
        if source not in self.routers or \
           destination not in self.routers:
            return None
        
        # 初始化距离和前驱节点
        distances = {router: float('inf') for router in self.routers}
        distances[source] = 0
        previous = {router: None for router in self.routers}
        
        # 优先队列
        pq = [(0, source)]
        
        while pq:
            current_distance, current_router = heapq.heappop(pq)
            
            # 到达目标
            if current_router == destination:
                break
            
            # 已经找到更短的路径
            if current_distance > distances[current_router]:
                continue
            
            # 检查所有相邻路由器
            for neighbor, info in self.connections[current_router].items():
                distance = current_distance + info['latency']
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current_router
                    heapq.heappush(pq, (distance, neighbor))
        
        # 构建路径
        if distances[destination] == float('inf'):
            return None
        
        path = []
        current = destination