邻接矩阵 - 元素码农

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

↑

# 邻接矩阵

邻接矩阵（Adjacency Matrix）是一种用于表示图的数据结构，它使用一个二维数组来存储图中顶点之间的连接关系。对于一个有n个顶点的图，邻接矩阵是一个n×n的矩阵，其中元素M[i][j]表示从顶点i到顶点j的边的信息。

## 基本概念

1. 无向图的邻接矩阵：
   - 对称矩阵（M[i][j] = M[j][i]）
   - M[i][j] = 1 表示顶点i和j之间有边
   - M[i][j] = 0 表示顶点i和j之间没有边

2. 有向图的邻接矩阵：
   - 不一定是对称矩阵
   - M[i][j] = 1 表示从顶点i到j有边
   - M[i][j] = 0 表示从顶点i到j没有边

3. 带权图的邻接矩阵：
   - M[i][j] = weight 表示边的权重
   - M[i][j] = ∞ 表示没有边

## 图示演示

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

对应的邻接矩阵：
    0  1  2  3
0   0  1  1  0
1   1  0  0  1
2   1  0  0  1
3   0  1  1  0

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

对应的邻接矩阵：
    0  1  2  3
0   0  1  1  0
1   0  0  0  1
2   0  0  0  0
3   0  0  1  0
```

## 代码实现

### 基本实现

```python
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, v1, v2):
        """添加无向图的边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            self.graph[v1][v2] = 1
            self.graph[v2][v1] = 1  # 无向图需要对称
    
    def remove_edge(self, v1, v2):
        """删除无向图的边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            self.graph[v1][v2] = 0
            self.graph[v2][v1] = 0
    
    def print_graph(self):
        """打印邻接矩阵"""
        for row in self.graph:
            print(row)

# 使用示例
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 = [[0] * vertices 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][to_v] = 1
    
    def remove_edge(self, from_v, to_v):
        """删除有向边"""
        if 0 <= from_v < self.V and 0 <= to_v < self.V:
            self.graph[from_v][to_v] = 0
    
    def has_path(self, from_v, to_v):
        """检查两点之间是否有路径"""
        return bool(self.graph[from_v][to_v])
    
    def get_out_degree(self, vertex):
        """获取顶点的出度"""
        return sum(self.graph[vertex])
    
    def get_in_degree(self, vertex):
        """获取顶点的入度"""
        return sum(row[vertex] for row in self.graph)

# 使用示例
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:
    def __init__(self, vertices):
        self.V = vertices
        # 使用float('inf')表示没有边
        self.graph = [[float('inf')] * vertices for _ in range(vertices)]
        # 设置对角线为0
        for i in range(vertices):
            self.graph[i][i] = 0
    
    def add_edge(self, v1, v2, weight):
        """添加带权边"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            self.graph[v1][v2] = weight
            self.graph[v2][v1] = weight  # 无向图需要对称
    
    def get_weight(self, v1, v2):
        """获取边的权重"""
        if 0 <= v1 < self.V and 0 <= v2 < self.V:
            return self.graph[v1][v2]
        return float('inf')
    
    def get_neighbors(self, vertex):
        """获取顶点的所有邻居"""
        neighbors = []
        for i in range(self.V):
            if self.graph[vertex][i] != float('inf'):
                neighbors.append((i, self.graph[vertex][i]))
        return neighbors

# 使用示例
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 neighbor, weight in wg.get_neighbors(2):
    print(f"到顶点{neighbor}的权重: {weight}")
```

## 性能分析

### 空间复杂度

- O(V²)，其中V是顶点数
- 对于稀疏图来说空间利用率低
- 对于稠密图较为合适

### 时间复杂度

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

2. 常见算法中的应用：
   - 图的遍历：O(V²)
   - 最短路径：O(V³)
   - 传递闭包：O(V³)

## 优缺点

### 优点

1. 实现简单直观
2. 基本操作效率高
3. 适合稠密图
4. 方便进行矩阵运算

### 缺点

1. 空间复杂度高
2. 对于稀疏图浪费空间
3. 添加/删除顶点需要调整矩阵大小

## 应用场景

1. 稠密图的表示
2. 需要快速判断两点间是否有边
3. 图的矩阵运算
4. 最短路径算法

## 实际应用示例

### 1. 社交网络分析

```python
class SocialNetwork:
    def __init__(self, users):
        self.users = users
        self.network = [[0] * users for _ in range(users)]
    
    def add_connection(self, user1, user2):
        """添加好友关系"""
        self.network[user1][user2] = 1
        self.network[user2][user1] = 1
    
    def remove_connection(self, user1, user2):
        """删除好友关系"""
        self.network[user1][user2] = 0
        self.network[user2][user1] = 0
    
    def get_friends(self, user):
        """获取用户的直接好友"""
        return [i for i in range(self.users) if self.network[user][i] == 1]
    
    def get_friends_of_friends(self, user):
        """获取二度好友"""
        friends = set(self.get_friends(user))
        friends_of_friends = set()
        
        for friend in friends:
            friends_of_friends.update(self.get_friends(friend))
        
        # 移除自己和直接好友
        friends_of_friends.discard(user)
        friends_of_friends.difference_update(friends)
        
        return list(friends_of_friends)

# 使用示例
social_net = SocialNetwork(5)
social_net.add_connection(0, 1)  # 用户0和1是好友
social_net.add_connection(1, 2)  # 用户1和2是好友
social_net.add_connection(2, 3)  # 用户2和3是好友
social_net.add_connection(3, 4)  # 用户3和4是好友

user = 0
print(f"用户{user}的直接好友: {social_net.get_friends(user)}")
print(f"用户{user}的二度好友: {social_net.get_friends_of_friends(user)}")
```

### 2. 地图路由

```python
class RouteMap:
    def __init__(self, locations):
        self.locations = locations
        self.distances = [[float('inf')] * locations for _ in range(locations)]
        # 设置对角线为0
        for i in range(locations):
            self.distances[i][i] = 0
    
    def add_route(self, loc1, loc2, distance):
        """添加两地之间的路线"""
        self.distances[loc1][loc2] = distance
        self.distances[loc2][loc1] = distance
    
    def find_shortest_path(self, start, end):
        """使用Floyd-Warshall算法找最短路径"""
        # 复制距离矩阵
        dist = [row[:] for row in self.distances]
        next_hop = [[None] * self.locations for _ in range(self.locations)]
        
        # 初始化next_hop矩阵
        for i in range(self.locations):
            for j in range(self.locations):
                if i != j and dist[i][j] != float('inf'):
                    next_hop[i][j] = j
        
        # Floyd-Warshall算法
        for k in range(self.locations):
            for i in range(self.locations):
                for j in range(self.locations):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_hop[i][j] = next_hop[i][k]
        
        # 构建路径
        if dist[start][end] == float('inf'):
            return None, float('inf')
        
        path = [start]
        current = start
        while current != end:
            current = next_hop[current][end]
            path.append(current)
        
        return path, dist[start][end]

# 使用示例
route_map = RouteMap(5)
# 添加路线（位置编号和距离）
route_map.add_route(0, 1, 5)   # A-B: 5km
route_map.add_route(1, 2, 3)   # B-C: 3km
route_map.add_route(2, 3, 4)   # C-D: 4km
route_map.add_route(3, 4, 2)   # D-E: 2km
route_map.add_route(0, 2, 7)   # A-C: 7km

start, end = 0, 4  # 从A到E
path, distance = route_map.find_shortest_path(start, end)
print(f"最短路径: {path}")
print(f"总距离: {distance}km")
```

## 总结

邻接矩阵是一种重要的图表示方法，它的主要特点是：

1. 实现简单，操作直观
2. 基本操作效率高
3. 适合稠密图
4. 便于进行矩阵运算

在实际应用中，需要根据具体场景选择合适的图表示方法：