python - 在没有循环的情况下删除 O(1) 中双嵌套字典中的键及其值？

Question

我正在学习 python 中的图数据结构，其中一个问题是基于无向图和有向图。它要求您在 O(deg(v)) 时间内删除一个顶点，并在 O(1) 时间内删除一条边。我设法删除了顶点，但在删除顶点后，需要删除从/到该顶点的边。 delete_edge fxn 是我遇到的问题，因为这是一个嵌套字典，我发现很难删除边缘。

这是无向原始图:

 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:

def incident_edges(self, v, outgoing=True):   
#Return all (outgoing) edges incident to vertex v in the graph.
#If graph is directed, optional parameter used to request incoming edges.

self._validate_vertex(v)
adj = self._outgoing if outgoing else self._incoming
for edge in adj[v].values():
  yield edge

这是我写的用于在 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) 的嵌套字典中导航。不知道该怎么办!请有经验的 friend 帮忙!

当前输出:

    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

谢谢!

PS:如果有什么遗漏，您可能需要更多引用，请告诉我!再次感谢!

Answer 1

将您的图形表示邻接列表 ( https://en.wikipedia.org/wiki/Adjacency_list ) 转换为邻接矩阵 ( https://en.wikipedia.org/wiki/Adjacency_matrix )？

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

但是，邻接表到邻接矩阵的转换是在O(|E|)中完成的(其中E是你的一组边缘)，但我认为您的练习中没有考虑到它。