En esta ocación vamos a trabajar con un grafo dirigido. Recordemos que un grafo G se define por G = (V,E) donde V es un conjunto no vacío de vértices o nodos y E un conjunto de aristas o arcos. Estos arcos serán un subconjunto de pares ordenados que sirgen del producto carteciando de VxV, lo cual quiere decir que establecen una relación entre un vértice y otro (incluso puede ser el mismo). Al ser pares ordenados, establecen un orden, e indican la dirección de qué arista a qué arista existe la conección. Es por ello que llamamos a estos gráfos dirigidos. Ahora bien, en un grafo de estas características, a pesar de que todas las aristas se encuentran conectados de alguna forma, no todos pueden ser visitados si partimos de un punto arbitrario A. Para poder detemrinar si todas las aristas pueden ser visitadas, vamos a usar un algoritmo de búsqueda primero a lo ancho. El nodo que no fue visitado será registrado y eliminado del grafo. A continuación mostraremos este algoritmo junto con su aplicación a un grafo con las características ántes descritas.

Primero definimos el grafo, y el punto de partida junto al punto de llegada. 

arcos = [("A","B"),("A","E"),("A","D"),("D","C"),("B","C"),\
        ("E","C"),("F","D")]
inicial = ["A"]
terminal = ("C",)

Como vemos, los nodos no necesitan ser definidos, al estar implícitos en los arcos. Sin embargo en ciertos grafos será necesario, dado a que no todos los nodos necesitan estar conectados por algún arco, en el caso de un grafo no conexto. Ahora el algoritmo DFS necesita tres listas.

openl = []
closedl = []
visitados = []

Finalmente se realiza la búsqueda:

while inicial:
    openl.append(inicial.pop(0))
    while openl:
        elem = openl.pop(0)
        closedl.append(elem)
        print("New closed:")
        print(closedl)
        for tup in arcos:
            if tup[0] == elem:
                if tup[1] not in closedl and tup[1] not in openl:
                    openl.append(tup[1])
                    print(openl)
        print("---------------------")
    visitados = visitados + closedl
novisitados = list(set(nodos) - set(visitados))
print("Nodos no visitados")
print(novisitados)

A continuación agregamos el código completo para que puedan usar este procedimiento en su propia computadora. Necesitará dos librerías, matplotlib y networkx, que pueden descargar usando pip. El código está en Python3. Esperamos les ha servido este breve artículo. 


# -*- coding:utf-8 -*- import networkx as nx import matplotlib.pyplot as plot arcos = [("A","B"),("A","E"),("A","D"),("D","C"),("B","C"),\ ("E","C"),("F","D")] inicial = ["A"] terminal = ("C",) nodos = [] # Calculando nodos a usar for t in arcos: nodos.append(t[0]) nodos.append(t[1]) nodos=list(set(nodos)) print(nodos) # Dibujar gráfico original G = nx.DiGraph() G.add_edges_from(arcos) pos = nx.spring_layout(G) nx.draw(G) plot.show() openl = [] closedl = [] visitados = [] # Se va a hacer un recorrido a lo ancho con lo que se visitarán # desde el nodo/s orígen todos los nodos del gráfico. Se # almacenarán en una lista llamda visitados while inicial: openl.append(inicial.pop(0)) while openl: elem = openl.pop(0) closedl.append(elem) print("New closed:") print(closedl) for tup in arcos: if tup[0] == elem: if tup[1] not in closedl and tup[1] not in openl: openl.append(tup[1]) print(openl) print("---------------------") visitados = visitados + closedl novisitados = list(set(nodos) - set(visitados)) print("Nodos no visitados") print(novisitados) for t in arcos: for n in novisitados: if n in t: arcos.remove(t) G = nx.DiGraph() G.add_edges_from(arcos) nx.draw(G) plot.show()

 

Share This