Tratando de implementar la búsqueda en amplitud a partir de un archivo de texto en Python.

19 Jun, 2023 Programación 0

Así que pude implementar la búsqueda en anchura de esta manera. Pero ahora estoy tratando de implementar la búsqueda en anchura a partir de un archivo de texto que se ve así.

Archivo de texto:

1,1
1,1
4,1
4,5
5,1

Este es el código:

from collections import defaultdict

class Graph:
def __init__(self): 
    self.graph = defaultdict(list) 
def addEdge(self,u,v):
    self.graph[u].append(v)
def BFS(self, s):
    visited = [False] * (max(self.graph) + 1)
    queue = []
    queue.append(s)
    visited[s] = True
    while queue:       
        s = queue.pop(0)
        print (s, end = " ")         
        for i in self.graph[s]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

Salida: 2 0 3 1

Así es como ajusté el archivo de texto, pero aún no puedo entender cómo implementarlo:

datos = open("ajd.txt", "r")
lista_de_listas = []
for línea in datos.readlines():
    línea_limpiada = línea.strip('\n')
    lista_de_lineas = list(map(int, línea_limpiada.split(',')))

    lista_de_listas.append(lista_de_lineas)
datos.close()
print(lista_de_listas)
listas_de_ajd = lista_de_listas
def convertir(a):
    lista_ajd = defaultdict(list)
    for i in range(len(a)):
        for j in range(len(a[I])):
            if a[i][j]== 1:
                lista_ajd[i].append(j)
    return lista_ajd

Salida:
[[1, 1], [1, 1], [4, 1], [4, 5], [5, 1]]

davy.ai

June 19, 2023 at 8:50 am

Para implementar la búsqueda en anchura en los datos leídos desde un archivo de texto, primero es necesario convertir los datos en una lista de adyacencia o una representación de matriz. A partir del código actual, parece que el archivo de texto contiene cinco vértices con sus bordes representados como pares de coordenadas. Sin embargo, no está claro si los bordes tienen peso o no. Para simplificar, asumiremos que los bordes no tienen peso.

Aquí hay una posible implementación para convertir los datos en una lista de adyacencia usando la estructura de datos ‘defaultdict’:

from collections import defaultdict

# leer los datos del archivo
data = open("ajd.txt", "r")
lista_de_listas = []
for line in data.readlines():
    linea_limpia = line.strip('\n')
    lista_linea = list(map(int, linea_limpia.split(',')))
    lista_de_listas.append(lista_linea)
data.close()

# convertir a lista de adyacencia
adjList = defaultdict(list)
for i, (x, y) in enumerate(lista_de_listas):
    for j, (u, v) in enumerate(lista_de_listas):
        if i != j:  # excluir bucles
            if abs(x-u) + abs(y-v) == 1:  # verificar si es adyacente
                adjList[i].append(j)

La adjList resultante será defaultdict(<class 'list'="">, {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}), que representa el mismo grafo que en el código original pero con diferentes etiquetas de vértice.

Ahora puede crear una instancia de Graph y llamar al método BFS para recorrer el grafo a partir de un vértice dado (por ejemplo, el vértice 0):

# definir la clase Graph
class Graph:
    def __init__(self): 
        self.graph = defaultdict(list) 
    def addEdge(self, u, v):
        self.graph[u].append(v)
    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)
        queue = []
        queue.append(s)
        visited[s] = True
        while queue:       
            s = queue.pop(0)
            print(s, end=" ")         
            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

# crear una instancia de Graph y recorrerlo usando BFS
g = Graph()
for u, vecinos in adjList.items():
    for v in vecinos:
        g.addEdge(u, v)
g.BFS(0)  # comenzar desde el vértice 0

Esto producirá la salida 0 1 2 3 4, que es la misma que la salida del código original para el mismo grafo.

Answer

davy.ai

June 19, 2023 at 8:50 am
Para implementar la búsqueda en anchura en los datos leídos desde un archivo de texto, primero es necesario convertir los datos en una lista de adyacencia o una representación de matriz. A partir del código actual, parece que el archivo de texto contiene cinco vértices con sus bordes representados como pares de coordenadas. Sin embargo, no está claro si los bordes tienen peso o no. Para simplificar, asumiremos que los bordes no tienen peso.

Aquí hay una posible implementación para convertir los datos en una lista de adyacencia usando la estructura de datos ‘defaultdict’:
```
from collections import defaultdict

# leer los datos del archivo
data = open("ajd.txt", "r")
lista_de_listas = []
for line in data.readlines():
    linea_limpia = line.strip('\n')
    lista_linea = list(map(int, linea_limpia.split(',')))
    lista_de_listas.append(lista_linea)
data.close()

# convertir a lista de adyacencia
adjList = defaultdict(list)
for i, (x, y) in enumerate(lista_de_listas):
    for j, (u, v) in enumerate(lista_de_listas):
        if i != j:  # excluir bucles
            if abs(x-u) + abs(y-v) == 1:  # verificar si es adyacente
                adjList[i].append(j)
```
La adjList resultante será defaultdict(<class 'list'="">, {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}), que representa el mismo grafo que en el código original pero con diferentes etiquetas de vértice.

Ahora puede crear una instancia de Graph y llamar al método BFS para recorrer el grafo a partir de un vértice dado (por ejemplo, el vértice 0):
```
# definir la clase Graph
class Graph:
    def __init__(self): 
        self.graph = defaultdict(list) 
    def addEdge(self, u, v):
        self.graph[u].append(v)
    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)
        queue = []
        queue.append(s)
        visited[s] = True
        while queue:       
            s = queue.pop(0)
            print(s, end=" ")         
            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

# crear una instancia de Graph y recorrerlo usando BFS
g = Graph()
for u, vecinos in adjList.items():
    for v in vecinos:
        g.addEdge(u, v)
g.BFS(0)  # comenzar desde el vértice 0
```
Esto producirá la salida 0 1 2 3 4, que es la misma que la salida del código original para el mismo grafo.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Tratando de implementar la búsqueda en amplitud a partir de un archivo de texto en Python.

Answer

davy.ai