Lösche Schlüssel und seine Werte in einem doppelt verschachtelten Wörterbuch in O (1) ohne Schleife?

Question

Ich lerne über Graph-Datenstrukturen in Python, und eine der Fragen wurde auf beiden ungerichteten & gerichteten Graphen basiert. Sie fordert Sie auf, einen Eckpunkt in der Zeit O (Grad (v)) zu löschen und eine Kante in der Zeit O (1) zu löschen. Ich habe es geschafft, den Scheitelpunkt zu löschen, aber nach dem Löschen des Scheitelpunktes müssen die Kanten von/zu diesem Scheitelpunkt gelöscht werden. Die delete_edge fxn ist, was ich habe ein Problem mit, weil dies ein verschachteltes Wörterbuch ist, finde ich es schwierig, die Kante zu löschen.

Hier ist der Undirected Original-Graph:

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)} 

Dies ist die fxn ist es, alle inzidenten Kanten für einen gegebenen Knoten zu finden:

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 

Dies ist der fxn i schrieb einen Scheitelpunkt in O entfernen (deg (v)) Zeit:

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 

Dies ist, wie weit ich mit dem remove_edge fxn bekam:

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)]]) 

Aber es funktioniert nicht! Ich kann nicht in der Lage sein, in einem verschachtelten Diktat in O (1) zu navigieren. Nicht sicher, was zu tun ist! Jeder mit mehr Erfahrung bitte helfen!

Stromausgang:

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 

Erwartete Ausgabe:

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 

Dank!

PS: wenn etwas fehlt, dass Sie für mehr Referenz benötigen, lassen Sie es mich bitte wissen! Danke noch einmal!

Answer 1

Konvertieren Sie Ihre Grafikdarstellung Adjacency List (https://en.wikipedia.org/wiki/Adjacency_list) in eine Adjacency matrix (https://en.wikipedia.org/wiki/Adjacency_matrix)?

Es scheint mir viel besser in Ihrem Anwendungsfall, denn wenn Sie dies tun, können Sie einen Knoten und seine Kanten in 2 Operationen löschen, die "löschen Sie die Zeile für Ihren Knoten" und "löschen Sie die entsprechende Spalte dein Knoten ". Was kann in O(1) getan werden.

Die Umwandlung einer Adjacency List in eine Adjacency Matrix erfolgt jedoch in O(|E|) (wo E ist Ihre Menge von Kanten), aber ich denke nicht, dass es in Ihrer Übung berücksichtigt wird.