从图嵌套字典中删除指定的顶点 python

Question

Helle，我有一个图 G，在 python 中表示如下：

G=defaultdict(list,
            {'0': ['4', '5'],
             '4': ['0', '7', '5', 'root'],
             '5': ['0', '2', '7', '4', '6', 'root'],
             '1': ['7'],
             '7': ['1', '4', '5', '6'],
             '2': ['5', '6'],
             '6': ['2', '7', '5', 'root'],
             'root': ['4', '5', '6']})

我需要从图 G 中有效地删除输入指定的一组顶点，尤其是当图非常大时。我试图浏览要删除的每个顶点的所有字典。还有其他更高效的方法吗？

Answer 1

LOOP R over vertices to be removed
    FIND R in dictionary
    LOOP A over vertices linked to V
        FIND A in dictionary
        REMOVE V from vertices linked to A
    REMOVE V from dictionary

以上取决于字典查找的性能。它应该是一个高效的二进制搜索。您还应该实现简单的循环算法并测量两者的性能。

LOOP A over vertices in dictionary
    LOOP R over vertices to be removed
        IF A = R
            REMOVE A
        ELSE
            LOOP R2 over vertices to be removed
                LOOP A2 over vertices linked to A
                    IF A2 = R2
                        REMOVE A2

从图嵌套字典中删除指定的顶点 python

Remove specified vertices from a graph nested dict python

python

python-3.x

graph-theory

compiler-optimization