<jupyter_start><jupyter_text>Breadth first search La búsqueda por expansión o breadth-first search es uno de los algoritmos más simples para realizar búsquedas en un grafo.Dada una gráfica G = {V, A} y un vértice fuente s, el algoritmo de búsqueda por expansión (amplitud o anchura) explora de manera sistemática todas las aristas de G para descubrir cada vértice que es accesible desde s.<jupyter_code>%pylab inline
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

import random
import numpy as np
MAXV = 0
class Node:
    # edge v
    to = 0
    # weight or cost from the edge (if it exists)
    cost = 0
    # Next edge-node
    nxt = None
    # BFS
    # previus edge-node
    prev = None
    # color: 0-blank, 1-gray, 2-black
    color = 0
    # distance
    distance = -1
class Graph:
    # edge adjacent
    edges = []
    # Extern grade from each node
    grade = []
    # nodes number
    num_nodes = 0
    # edges number
    num_edges = 0
    # directed or not
    directed = False
def start_graph (objGraph):
    i = 0
    objGraph.num_nodes = 0
    objGraph.num_edges = 0
    while i<=MAXV:
        objGraph.grade.append(0)
        objGraph.edges.append(None)
        i += 1
def insert_edge(objGraph, intU, intV, cost, isDirected):
    item = Node()
    item.cost = cost
    item.to = intV;
    item.nxt = objGraph.edges[intU]
    objGraph.edges[intU] = item
    objGraph.grade[intU] += 1
    if isDirected == False and intV != intU:
        insert_edge(objGraph, intV, intU, cost, True)
    else:
        objGraph.num_edges += 1
def create_graph (objGraph, hasCost, intMatrix):
    global nodes_numbers
    i = 0;
    u = v = cost = 0
    number_edges = objGraph.num_edges
    count_nodes_numbers = 0
    while i < number_edges:
        #print("Insert edge (u, v)")
        #u = int(input('u: '))
        u = nodes_numbers[count_nodes_numbers]
        count_nodes_numbers += 1
        #v = int(input('v: '))
        v = nodes_numbers[count_nodes_numbers]
        count_nodes_numbers += 1
        if hasCost == True :
            print("Insert cost or weight from edge:")
            cost = int(input('Cost / weight: '))
        else:
            cost = 1
        # insert cost on the adjacent matrix
        intMatrix[(v-1)][(u-1)] = cost;
        if objGraph.directed == False:
            intMatrix[(u-1)][v-1] = cost;
        # insert edge on the adjacent list
        insert_edge(objGraph, u, v, cost, objGraph.directed);
        i += 1
def print_graph(objGraph, intMatrix):
    i = 1
    item = None
    print("\nADJACENT LIST:")
    string = ""
    while i <= objGraph.num_nodes:
        string += str(i) + "\t"
        item = objGraph.edges[i]
        while item != None:
            string += str(item.to) + ": " + str(item.cost) + "\t"
            item = item.nxt;
        string += "\n"
        i += 1
    print(string)
    #print("ADJACENT MATRIX:")
    #print (intMatrix)
    #print()
# color: 0-blank, 1-gray, 2-black
def breadth_first_search(objGraph, intNodeS):
    global times
    objGraph.edges[intNodeS].color = 1
    objGraph.edges[intNodeS].distance = 0
    objGraph.edges[intNodeS].prev = None
    queue = []
    queue.append(intNodeS)
    while len(queue) != 0:
        times += 1
        u = queue.pop(0)
        v = objGraph.edges[u]
        while v != None:
            times += 1
            if objGraph.edges[v.to] != None:
                if objGraph.edges[v.to].color == 0:
                    objGraph.edges[v.to].color = 1
                    objGraph.edges[v.to].distance = objGraph.edges[u].distance + 1
                    objGraph.edges[v.to].prev = u
                    queue.append(v.to)
            v = v.nxt
        objGraph.edges[u].color = 2
def print_graph_color(objGraph):
    i = 1
    item = None
    print("\nBREADTH FIRST SEARCH:")
    string = ""
    while i <= objGraph.num_nodes:
        color = "blank" if objGraph.edges[i].color == 0 else "gray" if objGraph.edges[i].color == 1 else "black"
        cont = 0
        tabs = ""
        while cont<objGraph.edges[i].distance:
            tabs+="\t"
            cont += 1
        string += tabs + str(i) + ": " + color + "-" +  str(objGraph.edges[i].distance) + "\t"
        string += "\n"
        i += 1
    print(string)
def main():
    global matrix, MAXV, n_n, n_e, g_c, g_d
    op = directed = cost = i = j = 0
    print("\n####### GRAPH STRUCTURE #######\n")
    directed = g_d
    cost = g_c
    hasCost = True if cost == 1 else False
    num_nodes = n_n
    MAXV = num_nodes
    obj_graph.edges = []
    obj_graph.grade = []
    start_graph(obj_graph)
    obj_graph.num_nodes = num_nodes
    obj_graph.directed = True if directed == 1 else False
    matrix = np.zeros((obj_graph.num_nodes, obj_graph.num_nodes))
    obj_graph.num_edges = n_e
    
    create_graph(obj_graph, hasCost, matrix)
    print_graph(obj_graph, matrix)
    breadth_first_search(obj_graph, 3)
    print_graph_color(obj_graph)
TAM = 20
times = 0
obj_graph = Graph()
matrix = None
# graph directed (1) no directed (2)
g_d = 2
# graph with cost (1) without cost (2)
g_c = 2
# number of nodes
n_n = TAM
# edges (u, v)
#nodes_numbers = [1, 2, 2, 3, 3, 4, 4, 6, 4, 5, 6, 5, 6, 7, 5, 7, 7, 8, 5, 8]
nodes_numbers = [1,5,1,2,1,7,1,6,1,11,1,9,1,12,2,7,2,6,2,5,2,19,2,3,2,9,2,12,3,4,5,18,5,6,5,8,5,7,5,20,6,13,6,9,6,12,7,8,7,10,8,10,8,13,8,18,9,11,9,12,10,13,10,12,11,12,11,17,11,15,12,17,12,15,13,14,13,16,13,18,14,16,14,18,15,17,16,18]
#nodes_numbers = []
#for i in range(0, TAM):
#    nodes_numbers.append(random.randint(1, TAM))
print(nodes_numbers)
# number of edges
n_e = len(nodes_numbers)/2
main()
def main_graph(n_n, n_e, g_c, g_d):
    global matrix, MAXV
    op = directed = cost = i = j = 0
    directed = g_d
    cost = g_c
    hasCost = True if cost == 1 else False
    num_nodes = n_n
    MAXV = num_nodes
    obj_graph.edges = []
    obj_graph.grade = []
    start_graph(obj_graph)
    obj_graph.num_nodes = num_nodes
    obj_graph.directed = True if directed == 1 else False
    matrix = np.zeros((obj_graph.num_nodes, obj_graph.num_nodes))
    obj_graph.num_edges = n_e
    create_graph(obj_graph, hasCost, matrix)
    random_int = random.randint(1, num_nodes)
    while obj_graph.edges[random_int] == None:
        random_int = random.randint(1, num_nodes)
    breadth_first_search(obj_graph, random_int)
TAM = 100
x = list(range(2,TAM,1))
y_complete = []
y_average = []
y_lineal = []
nodes_numbers = []
g_d = 2
g_c = 2

obj_graph = None
matrix = None

for num in x:
    nodes_numbers = []
    obj_graph = Graph()
    matrix = None
    
    n_n = num
    for i in range(0, num):
        nodes_numbers.append(random.randint(1, num))
    n_e = len(nodes_numbers)//2
    times = 0
    main_graph(n_n, n_e, g_c, g_d)
    y_average.append(times)
    
    # complete graph
    nodes_numbers = []
    for i in range(0, num):
        for j in range (0, num):
            if j > i:
                nodes_numbers.append(i+1)
                nodes_numbers.append(j+1)
    n_e = len(nodes_numbers)//2
    times = 0
    main_graph(n_n, n_e, g_c, g_d)
    y_complete.append(times)

    # lineal graph
    times = 0
    nodes_numbers = []
    for i in range(2, num+1):
        nodes_numbers.append(i-1)
        nodes_numbers.append(i)
        
    n_e = len(nodes_numbers)//2
    times = 0
    main_graph(n_n, n_e, g_c, g_d)
    y_lineal.append(times)
fig, ax = plt.subplots(facecolor='w', edgecolor='k')
ax.plot(x, y_average, marker="o",color="b", linestyle='None')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.grid(True)
ax.legend(["Breath first search"])
plt.title('Breath first search (average case)')
plt.show()

fig, ax = plt.subplots(facecolor='w', edgecolor='k')
ax.plot(x, y_complete, marker="o",color="b", linestyle='None')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.grid(True)
ax.legend(["Breath first search"])
plt.title('Breath first search (complete graph)')
plt.show()

fig, ax = plt.subplots(facecolor='w', edgecolor='k')
ax.plot(x, y_lineal, marker="o",color="b", linestyle='None')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.grid(True)
ax.legend(["Breath first search"])
plt.title('Breath first search (linear graph)')
plt.show()<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup