如何用Python从边列表中提取对应顶点集合的边？

编写Python代码，接收edges和sets作为输入，遍历sets中的每个顶点集合，提取出两个顶点均属于该集合的边，最终输出sets_of_edges。

输入输出示例 #

输入 #

edges = [ [1,2] , [2,3] , [3,4] , [4,5] , [5,2] , [4,6] , [6,7] , [7,6] , [7,8] ]
sets = [ [2,3,4,5] , [6,7] ]

输出 #

sets_of_edges = [ [ [2,3] , [3,4] , [4,5] , [5,2] ] , [ [6,7] , [7,6] ] ]

Python实现代码 #

def extract_target_edges(edges, vertex_sets):
    sets_of_edges = []
    for vertex_group in vertex_sets:
        # 转成集合提升成员判断效率
        vertex_set = set(vertex_group)
        # 筛选两端顶点都在当前集合内的边
        matched_edges = [edge for edge in edges if edge[0] in vertex_set and edge[1] in vertex_set]
        sets_of_edges.append(matched_edges)
    return sets_of_edges

# 测试示例
edges = [ [1,2] , [2,3] , [3,4] , [4,5] , [5,2] , [4,6] , [6,7] , [7,6] , [7,8] ]
sets = [ [2,3,4,5] , [6,7] ]
sets_of_edges = extract_target_edges(edges, sets)
print(sets_of_edges)

代码说明 #

• 将每个顶点列表转为set类型，利用集合O(1)时间复杂度的成员判断特性，提升筛选效率。
• 通过列表推导式遍历所有边，快速筛选出符合条件的边并分组存入结果列表。
• 函数返回的结果直接对应需求中的sets_of_edges格式。

内容的提问来源于stack exchange，提问作者user18692484