当前位置：文江博客话题详情

在元组列表中删除中间对

发布于 2025-02-11 19:41:12 字数 289 浏览 2 评论 0原文

给定一个元素列表，例如

[（0,1），（0,2），（0,3），（1,4），（1,5），（2,6），（6,7），（6,7），（ [7,8）]

这形成了一种树，其中0个有3个孩子，1个有2个孩子，依此类推。我们还看到0 - ＆GT; 2 - ＆GT; 6-＆GT; 7 - ＆GT; 8创建了这个曲折的分支。我如何删除所有这些笔直的分支，以便以这样的输出结尾：

[（0,1），（0,8），（0,3），（1,4），（1,5），

如果他们是1和孩子之间的节点，然后如果该节点没有孩子的孩子，就直接与孩子链接。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

嘴硬脾气大 2025-02-18 19:41:12

我将使用Python代码回答。

这个想法是首先创建一个邻接列表，其中每个节点键都有一个词典，上面有一个带有节点子的键的列表。

然后使用后订单遍历，其中每个恰好一个孩子的节点都会从链中取出。

最后，将邻接列表转换回边缘列表。

代码：

from collections import defaultdict

# create adjacency list as dict(int, List<int>)
def create_graph(edges):
    adj = defaultdict(list)
    for a, b in edges:
        adj[a].append(b)
    return adj
    
# Perform depth-first traversal to remove nodes
# that have exactly one child
def remove_lonely_nodes(adj, nodeid):
    adj[nodeid] = [remove_lonely_nodes(adj, child) for child in adj[nodeid]]
    if len(adj[nodeid]) == 1:  # skip nodeid
        return adj[nodeid][0]
    return nodeid

def getedges(adj, nodeid):
    return [
        (nodeid, childid) for childid in adj[nodeid]
    ] + [
       edge for id in adj[nodeid] 
            for edge in getedges(adj, id)
    ]

示例运行

edges = [(0,1), (0,2), (0,3), (1,4), (1,5), (2,6), (6,7), (7,8)]
adj = create_graph(edges)
remove_lonely_nodes(adj, 0)  # we assume 0 is the root
edges = getedges(adj, 0)
print(edges)  # [(0, 1), (0, 8), (0, 3), (1, 4), (1, 5)]

I'll answer this with Python code.

The idea is to first create an adjacency list, where for each node key, a dictionary has a list with keys of the node's children.

Then use a post-order traversal, where every node that has exactly one child is taken out of the chain.

Finally, convert that adjacency list back to a list of edges.

code:

from collections import defaultdict

# create adjacency list as dict(int, List<int>)
def create_graph(edges):
    adj = defaultdict(list)
    for a, b in edges:
        adj[a].append(b)
    return adj
    
# Perform depth-first traversal to remove nodes
# that have exactly one child
def remove_lonely_nodes(adj, nodeid):
    adj[nodeid] = [remove_lonely_nodes(adj, child) for child in adj[nodeid]]
    if len(adj[nodeid]) == 1:  # skip nodeid
        return adj[nodeid][0]
    return nodeid

def getedges(adj, nodeid):
    return [
        (nodeid, childid) for childid in adj[nodeid]
    ] + [
       edge for id in adj[nodeid] 
            for edge in getedges(adj, id)
    ]

Example run

edges = [(0,1), (0,2), (0,3), (1,4), (1,5), (2,6), (6,7), (7,8)]
adj = create_graph(edges)
remove_lonely_nodes(adj, 0)  # we assume 0 is the root
edges = getedges(adj, 0)
print(edges)  # [(0, 1), (0, 8), (0, 3), (1, 4), (1, 5)]

回复收藏 0 原文

~没有更多了~