Agregar y eliminar vértices en la representación de la lista de adyacencia del gráfico

Requisitos previos: lista enlazada , estructura de datos de gráfico

En este artículo, se analiza la adición y eliminación de un vértice en una representación de lista de adyacencia determinada.

Sea el gráfico dirigido :

El gráfico se puede representar en la representación de la lista de adyacencia como:

Es una representación de lista enlazada donde la cabeza de la lista enlazada es un vértice en el gráfico y todos los Nodes conectados son los vértices a los que está conectado el primer vértice. Por ejemplo, del gráfico, está claro que el vértice 0 está conectado al vértice 4 , 3 y 1 . Lo mismo se representa en la representación de lista de adyacencia (o lista enlazada).

Acercarse:

La idea es representar el gráfico como una lista de listas enlazadas donde la cabeza de la lista enlazada es el vértice y todas las listas enlazadas conectadas son los vértices a los que está conectada.
• Agregar un vértice en el gráfico: para agregar un vértice en el gráfico, la lista de adyacencia se puede iterar hasta el lugar donde se requiere la inserción y el nuevo Node se puede crear utilizando la implementación de la lista vinculada. Por ejemplo, si es necesario agregar 5 entre el vértice 2 y el vértice 3 de modo que el vértice 3 apunte al vértice 5 y el vértice 5 apunte al vértice 2, entonces se crea un nuevo borde entre el vértice 5 y el vértice 3 y se crea un nuevo borde a partir de vértice 5 y vértice 2. Después de agregar el vértice, la lista de adyacencia cambia a:
  
• Eliminación de un vértice en el gráfico : para eliminar un vértice en el gráfico, itere a través de la lista de cada vértice si hay un borde presente o no. Si el borde está presente, elimine el vértice de la misma manera que se realiza la eliminación en una lista vinculada. Por ejemplo, la lista de adyacencia se traduce en la siguiente lista si se elimina el vértice 4 de la lista:
  

  A continuación se muestra la implementación del enfoque anterior:

  # Python implementation of the above approach # Implementing Linked List representation class AdjNode(object):     def __init__(self, data):         self.vertex = data         self.next = None    # Adjacency List representation class AdjList(object):        def __init__(self, vertices):         self.v = vertices         self.graph =[None]*self.v    # Function to add an edge from a source vertex  # to a destination vertex     def addedge(self, source, destination):         node = AdjNode(destination)         node.next = self.graph         self.graph= node    # Function to call the above function.     def addvertex(self, vk, source, destination):         graph.addedge(source, vk)          graph.addedge(vk, destination)    # Function to print the graph     def print_graph(self):         for i in range(self.v):             print(i, end ="")             temp = self.graph[i]             while temp:                print("->", temp.vertex, end ="")                temp = temp.next             print("\n")    # Function to delete a vertex     def delvertex(self, k):    # Iterating through all the vertices of the graph         for i in range(self.v):             temp = self.graph[i]             if i == k:                 while temp:                     self.graph[i]= temp.next                     temp = self.graph[i]                                    # Delete the vertex              # using linked list concept                     if temp:                 if temp.vertex == k:                     self.graph[i]= temp.next                     temp = None             while temp:                 if temp.vertex == k:                     break                 prev = temp                 temp = temp.next                if temp == None:                 continue                prev.next = temp.next             temp = None           # Driver code if __name__ == "__main__":        V = 6     graph = AdjList(V)      graph.addedge(0, 1)     graph.addedge(0, 3)     graph.addedge(0, 4)     graph.addedge(1, 2)     graph.addedge(3, 2)     graph.addedge(4, 3)    print("Initial adjacency list") graph.print_graph()     # Add vertex graph.addvertex(5, 3, 2) print("Adjacency list after adding vertex") graph.print_graph()     # Delete vertex graph.delvertex(4) print("Adjacency list after deleting vertex") graph.print_graph()

  Producción:

  Initial adjacency list
  0-> 4-> 3-> 1
  
  1-> 2
  
  2
  
  3-> 2
  
  4-> 3
  
  5
  
  Adjacency list after adding vertex
  0-> 4-> 3-> 1
  
  1-> 2
  
  2
  
  3-> 5-> 2
  
  4-> 3
  
  5-> 2
  
  Adjacency list after deleting vertex
  0-> 3-> 1
  
  1-> 2
  
  2
  
  3-> 5-> 2
  
  4
  
  5-> 2