Programar un grafo en Python

¿Qué es un grafo?

A grandes rasgos, un grafo es una estructura de datos utilizada para representar relaciones entre objetos. Consiste en un conjunto de nodos (también llamados vértices) y un conjunto de aristas (también llamadas conexiones o bordes) que conectan estos nodos. Dependiendo del tipo de grafo, las aristas pueden tener diferentes propiedades, como direccionalidad (en grafos dirigidos) o pesos (en grafos ponderados).

Programación del un grafo en Python 

El código del grafo en Python es el siguiente:

class Graph:

    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = {}

    def add_edge(self, vertex1, vertex2, weight=None, directed=False):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.graph[vertex1][vertex2] = weight
        if not directed:
            self.graph[vertex2][vertex1] = weight

    def display(self):
        for vertex, edges in self.graph.items():
            print(f"Vértice {vertex} tiene como conexiones a:")
            for neighbor, weight in edges.items():
                if weight:
                    print(f"  - {neighbor} (peso: {weight})")
                else:
                    print(f"  - {neighbor}")

A continuación te explicamos cada segmento de línea:

Lo primero que tenemos que hacer es crear una clase grafo, donde se tienen 1 instancia y 3 métodos display , add_vertex y add_edge, 

class Graph:         
     def __init__(self):
     def add_vertex(self,vertex): 
     def add_edge(self, vertex1, vertex2, weight=None, directed=False) 
     def display(self)

Para la instancia _init_(self):

#Se crea un atributo "graph" que es un diccionario en el que las claves representan los 
#vértices del grafo y los valores son también diccionarios que representan los vecinos 
#de cada vértice y los pesos de las aristas.

     def __init__(self):
         self.graph = {}

Para el método  def add_vertex(self, vertex):

   # Método para agregar un vértice al grafo.
   # Parámetros:    
   #self: Acceder a los atributos y métodos de la instancia dentro de la clase
   #vertex: El vértice que se desea agregar al grafo
        if vertex not in self.graph:
            # Verifica si el vértice ya existe en el grafo.
            # Si no existe, crea una nueva entrada en el diccionario con el vértice como clave y un diccionario vacío como valor.
            self.graph[vertex] = {}

Para el método  add_edge(self, vertex1, vertex2, weight=None, directed=False):

def add_edge(self, vertex1, vertex2, weight=None, directed=False):
        # Método para agregar una arista al grafo.
        # Parámetros:
        # - vertex1: El primer vértice de la arista.
        # - vertex2: El segundo vértice de la arista.
        # - weight: El peso de la arista (opcional, por defecto es None).
        # - directed: Un indicador booleano que indica si la arista es dirigida o no (opcional, por defecto es False).
        self.add_vertex(vertex1)  # Agrega el vértice 1 al grafo si aún no está presente.
        self.add_vertex(vertex2)  # Agrega el vértice 2 al grafo si aún no está presente.
        # Agrega la arista desde el vértice 1 al vértice 2 en el diccionario del grafo.
        self.graph[vertex1][vertex2] = weight
        if not directed:
            # Si la arista no es dirigida, también se agrega la arista desde el vértice 2 al vértice 1.
            self.graph[vertex2][vertex1] = weight

Para el método  display(self):

def display(self):
        # Método para mostrar el grafo.
        for vertex, edges in self.graph.items():
            # Itera sobre cada vértice en el grafo.
            # vertex es el vértice actual y edges es un diccionario de sus vecinos (vértices adyacentes).
            print(f"Vértice {vertex} tiene como conexiones a:")
            for neighbor, weight in edges.items():
                # Itera sobre cada vecino del vértice actual.
                # neighbor es el vértice vecino y weight es el peso de la arista entre el vértice actual y su vecino.
                if weight:
                    # Si hay un peso definido para la arista, se muestra.
                    print(f"  - {neighbor} (peso: {weight})")
                else:
                    # Si no hay peso definido, se muestra el vecino sin peso.
                    print(f"  - {neighbor}")

Ejemplo de Implementación del Grafo. 

Ahora intentaremos implementar el siguiente gafo haciendo uso de la clase, mencionada anteriormente:  

El código seria el siguiente:

# Crear una instancia de la clase Graph
g = Graph()

# Agregar vértices
vertices = ['A', 'B', 'C', 'D', 'E', 'F']

for vertex in vertices:
    g.add_vertex(vertex)

# Agregar aristas ponderadas

g.add_edge('A', 'B', weight=5)
g.add_edge('A', 'C', weight=2)
g.add_edge('B', 'C', weight=1)
g.add_edge('B', 'D', weight=4)
g.add_edge('C', 'D', weight=3)
g.add_edge('C', 'E', weight=6)
g.add_edge('D', 'E', weight=7)
g.add_edge('E', 'F', weight=8)

# Mostrar el grafo
g.display()

Resultado: