在没有循环的O（1）中删除双嵌套字典中的键及其值？

Question

我正在学习python中的图形数据结构，其中一个问题是基于无向和有向图的。它要求您在O（deg（v））时间内删除顶点，并在O（1）时间内删除边。我已经成功地删除了顶点，但是在删除顶点之后，需要删除顶点之间的边。delete_edge fxn是我遇到的问题，因为这是一个嵌套字典，我发现很难删除edge。在

这是无向原始图：

 C {A: (A,C,2), B: (B,C,5), E: (C,E,7), D: (C,D,6)}
 A {B: (A,B,1), C: (A,C,2), E: (A,E,4), D: (A,D,3)}
 B {A: (A,B,1), C: (B,C,5)}
 E {A: (A,E,4), C: (C,E,7)}
 D {A: (A,D,3), C: (C,D,6)}

这是用于查找给定顶点的所有入射边的fxn：

^{pr2}$

这是我写的在O（deg（v））时间内移除顶点的fxn：

def remove_vertex(self, v):
"""Remove the vertex v and all its incident edges,
and return the vertex been removed.
Parameter v is an instance of Vertex
Algorithm should run in O(deg(v)) time
"""

 for i in self.incident_edges(v):
   self.remove_edge(i)

 del self._outgoing[v]

 return v

这是我使用remove-edge-fxn所达到的效果：

def remove_edge(self, e):
"""remove the edge e from the adjacency map for each
incident vertex, and return the edge removed.
Parameter e is an instance of Edge
Algorithm should run in O(1) time.
""" 
   list(list(self._outgoing.values())[list(self._outgoing.values())[list(self._outgoing.values()).index(e)]])

但这不管用！我似乎无法在O（1）中的嵌套dict中导航。不知道该怎么办！有经验的人请帮忙！在

电流输出：

    Undirected Original Graph:
    D {A: (A,D,3), C: (C,D,6)}
    C {A: (A,C,2), B: (B,C,5), D: (C,D,6), E: (C,E,7)}
    B {A: (A,B,1), C: (B,C,5)}
    A {B: (A,B,1), C: (A,C,2), D: (A,D,3), E: (A,E,4)}
    E {A: (A,E,4), C: (C,E,7)}

    Number of vertices is 5
    Number of edges is 7

    Undirected Graph After deleting Vertex 'D':
    (which consequently deletes its incident edges)
    C {A: (A,C,2), B: (B,C,5), D: (C,D,6), E: (C,E,7)}
    B {A: (A,B,1), C: (B,C,5)}
    A {B: (A,B,1), C: (A,C,2), D: (A,D,3), E: (A,E,4)}
    E {A: (A,E,4), C: (C,E,7)}

    Number of vertices is 4
    Number of edges is 6

预期产量：

    Undirected Original Graph:
    D {A: (A,D,3), C: (C,D,6)}
    C {A: (A,C,2), B: (B,C,5), D: (C,D,6), E: (C,E,7)}
    B {A: (A,B,1), C: (B,C,5)}
    A {B: (A,B,1), C: (A,C,2), D: (A,D,3), E: (A,E,4)}
    E {A: (A,E,4), C: (C,E,7)}

    Number of vertices is 5
    Number of edges is 7

    Undirected Graph After deleting Vertex 'D':
    (which consequently deletes its incident edges)
    C {A: (A,C,2), B: (B,C,5), E: (C,E,7)}
    B {A: (A,B,1), C: (B,C,5)}
    A {B: (A,B,1), C: (A,C,2), E: (A,E,4)}
    E {A: (A,E,4), C: (C,E,7)}

    Number of vertices is 4
    Number of edges is 6

谢谢！在

附言：如果有什么东西遗漏了，你可能需要更多的参考，请告诉我！再次感谢！在

Answer 1

将您的图表示Adjacency List（https://en.wikipedia.org/wiki/Adjacency_list）转换为Adjacency matrix（https://en.wikipedia.org/wiki/Adjacency_matrix）吗？在

在我看来，它更适合您的用例，因为如果您这样做，您可以删除一个节点及其边的两个操作，即“删除与您的节点对应的行”和“删除与您的节点对应的列”。可以在O(1)中完成。在

然而，将Adjacency List转换为Adjacency Matrix是在O(|E|)中完成的（其中E是您的一组边），但我认为在您的练习中没有考虑到这一点。在