边集数组 - 元素码农

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

↑

# 边集数组

边集数组（Edge Set）是一种用于表示图的数据结构，它直接存储图的所有边的信息。每条边包含起点、终点（对于有向图）或两个顶点（对于无向图），以及可能的权重信息。这种结构特别适合于需要频繁处理边的算法，如最小生成树算法。

## 基本概念

1. 无向图的边集数组：
   - 每条边存储两个顶点
   - 顶点的顺序无关紧要
   - 可以包含权重信息

2. 有向图的边集数组：
   - 每条边存储起点和终点
   - 顶点的顺序表示方向
   - 可以包含权重信息

3. 边的表示：
   - (u, v)表示无向边
   - u->v表示有向边
   - (u, v, w)表示带权边

## 图示演示

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

边集表示：
[(0,1), (0,2), (1,3), (2,3)]

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

边集表示：
[(0,1), (0,2), (1,3), (3,2)]

带权图示例：
    0 -2- 1
    |     |
    3 -4- 5

边集表示：
[(0,1,2), (0,3,3), (1,5,1), (3,5,4)]
```

## 代码实现

### 基本实现

```python
class Edge:
    def __init__(self, src, dest, weight=1):
        self.src = src
        self.dest = dest
        self.weight = weight
    
    def __str__(self):
        return f"({self.src}->{self.dest}, weight:{self.weight})"

class Graph:
    def __init__(self, vertices, directed=False):
        self.V = vertices
        self.directed = directed
        self.edges = []
    
    def add_edge(self, src, dest, weight=1):
        """添加边"""
        if 0 <= src < self.V and 0 <= dest < self.V:
            self.edges.append(Edge(src, dest, weight))
            if not self.directed:
                self.edges.append(Edge(dest, src, weight))
    
    def get_edges(self):
        """获取所有边"""
        return self.edges
    
    def print_graph(self):
        """打印图的边集"""
        for edge in self.edges:
            print(edge)

# 使用示例
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 WeightedGraph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_edge(self, src, dest, weight):
        """添加带权边"""
        if 0 <= src < self.V and 0 <= dest < self.V:
            self.edges.append(Edge(src, dest, weight))
    
    def get_edge_weight(self, src, dest):
        """获取边的权重"""
        for edge in self.edges:
            if edge.src == src and edge.dest == dest:
                return edge.weight
        return float('inf')
    
    def sort_edges(self):
        """按权重排序边"""
        self.edges.sort(key=lambda x: x.weight)

# 使用示例
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("排序前的边:")
for edge in wg.edges:
    print(edge)

wg.sort_edges()
print("\n按权重排序后的边:")
for edge in wg.edges:
    print(edge)
```

### Kruskal算法实现

```python
class DisjointSet:
    def __init__(self, vertices):
        self.parent = list(range(vertices))
        self.rank = [0] * vertices
    
    def find(self, item):
        """查找集合的代表元素"""
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]
    
    def union(self, x, y):
        """合并两个集合"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1

class KruskalMST:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_edge(self, src, dest, weight):
        self.edges.append(Edge(src, dest, weight))
    
    def find_mst(self):
        """使用Kruskal算法找最小生成树"""
        # 按权重排序边
        self.edges.sort(key=lambda x: x.weight)
        
        # 初始化并查集
        ds = DisjointSet(self.V)
        mst = []
        
        for edge in self.edges:
            # 如果加入这条边不会形成环
            if ds.find(edge.src) != ds.find(edge.dest):
                mst.append(edge)
                ds.union(edge.src, edge.dest)
        
        return mst

# 使用示例
mst = KruskalMST(4)
mst.add_edge(0, 1, 10)
mst.add_edge(0, 2, 6)
mst.add_edge(0, 3, 5)
mst.add_edge(1, 3, 15)
mst.add_edge(2, 3, 4)

result = mst.find_mst()
print("最小生成树的边:")
for edge in result:
    print(edge)
```

## 性能分析

### 空间复杂度

- O(E)，其中E是边的数量
- 适合边数较少的稀疏图
- 不适合边数较多的稠密图

### 时间复杂度

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

2. 常见算法中的应用：
   - 最小生成树（Kruskal）：O(E log E)
   - 最短路径：O(VE)
   - 图的遍历：O(E)

## 优缺点

### 优点

1. 实现简单
2. 适合稀疏图
3. 方便对边进行操作
4. 适合需要频繁处理边的算法

### 缺点

1. 查找特定边效率低
2. 获取顶点的邻接边需要遍历
3. 不适合需要频繁查询顶点信息的场景

## 应用场景

1. 最小生成树算法
2. 网络规划
3. 图的连通性分析
4. 边的权重处理

## 实际应用示例

### 1. 网络连接规划

```python
class NetworkPlanner:
    def __init__(self, locations):
        self.V = locations
        self.edges = []
    
    def add_connection(self, src, dest, cost):
        """添加两个位置之间的连接成本"""
        self.edges.append(Edge(src, dest, cost))
    
    def plan_network(self):
        """使用Kruskal算法规划最小成本网络"""
        # 按成本排序所有可能的连接
        self.edges.sort(key=lambda x: x.weight)
        
        # 使用并查集检测环
        ds = DisjointSet(self.V)
        network = []
        total_cost = 0
        
        for edge in self.edges:
            if ds.find(edge.src) != ds.find(edge.dest):
                network.append(edge)
                total_cost += edge.weight
                ds.union(edge.src, edge.dest)
        
        return network, total_cost

# 使用示例
planner = NetworkPlanner(5)

# 添加可能的连接和成本
connections = [
    (0, 1, 10),  # A-B: 10
    (0, 2, 15),  # A-C: 15
    (1, 2, 5),   # B-C: 5
    (1, 3, 12),  # B-D: 12
    (2, 3, 8),   # C-D: 8
    (2, 4, 20),  # C-E: 20
    (3, 4, 7),   # D-E: 7
]

for src, dest, cost in connections:
    planner.add_connection(src, dest, cost)

network, total_cost = planner.plan_network()

print("最优网络连接方案:")
for edge in network:
    print(f"连接 {edge.src} 到 {edge.dest}, 成本: {edge.weight}")
print(f"总成本: {total_cost}")
```

### 2. 路径分析

```python
class PathAnalyzer:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_path(self, src, dest, distance):
        """添加路径"""
        self.edges.append(Edge(src, dest, distance))
    
    def find_all_paths(self, start, end):
        """找出所有可能的路径"""
        def dfs(current, path, visited):
            if current == end:
                paths.append(path[:])
                return
            
            for edge in self.edges:
                if edge.src == current and edge.dest not in visited:
                    visited.add(edge.dest)
                    path.append(edge)
                    dfs(edge.dest, path, visited)
                    path.pop()
                    visited.remove(edge.dest)
        
        paths = []
        visited = {start}
        dfs(start, [], visited)
        return paths
    
    def find_shortest_path(self, start, end):
        """使用Dijkstra算法找最短路径"""
        import heapq
        
        # 初始化距离和前驱节点
        dist = [float('inf')] * self.V
        prev = [None] * self.V
        dist[start] = 0
        
        # 优先队列
        pq = [(0, start)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            if u == end:
                break
            
            if d > dist[u]:
                continue
            
            # 检查所有出边
            for edge in self.edges:
                if edge.src == u:
                    v = edge.dest
                    alt = dist[u] + edge.weight
                    
                    if alt < dist[v]:
                        dist[v] = alt
                        prev[v] = u
                        heapq.heappush(pq, (alt, v))
        
        # 构建路径
        if dist[end] == float('inf'):
            return None, float('inf')
        
        path = []
        current = end
        while current is not None:
            path.append(current)
            current = prev[current]
        
        return path[::-1], dist[end]

# 使用示例
analyzer = PathAnalyzer(6)

# 添加路径
paths = [
    (0, 1, 5),  # A-B: 5km
    (0, 2, 2),  # A-C: 2km
    (1, 3, 4),  # B-D: 4km
    (2, 3, 7),  # C-D: 7km
    (2, 4, 3),  # C-E: 3km
    (3, 5, 1),  # D-F: 1km
    (4, 5, 5)   # E-F: 5km
]

for src, dest, dist in paths:
    analyzer.add_path(src, dest, dist)

# 找出所有可能的路径
start, end = 0, 5  # A到F
all_paths = analyzer.find_all_paths(start, end)

print("所有可能的路径:")
for path in all_paths:
    total_dist = sum(edge.weight for edge in path)