using Random
using Dates  # Para medir el tiempo de ejecución
 
# Definir el grafo como un diccionario de listas de adyacencia
function create_graph(nodes::Int, edges::Int)
    graph = Dict{Int, Vector{Int}}()
    for i in 1:nodes
        graph[i] = []
    end
    for _ in 1:edges
        u = rand(1:nodes)
        v = rand(1:nodes)
        push!(graph[u], v)
    end
    return graph
end
 
# Implementación de DFS
function dfs(graph::Dict{Int, Vector{Int}}, start::Int)
    visited = Set{Int}()
    stack = [start]
    while !isempty(stack)
        node = pop!(stack)
        if node ∉ visited
            push!(visited, node)
            for neighbor in graph[node]
                push!(stack, neighbor)
            end
        end
    end
    return visited
end
 
# Implementación de BFS
function bfs(graph::Dict{Int, Vector{Int}}, start::Int)
    visited = Set{Int}()
    queue = [start]
    while !isempty(queue)
        node = popfirst!(queue)
        if node ∉ visited
            push!(visited, node)
            for neighbor in graph[node]
                push!(queue, neighbor)
            end
        end
    end
    return visited
end
 
# Configurar el grafo
nodes = 1000  # Cambia este valor para modificar el tamaño
edges = 5000  # Cambia este valor para modificar el tamaño
graph = create_graph(nodes, edges)
 
# Temporizador y ejecución
start_time = now()
visited_dfs = dfs(graph, 1)
dfs_time = now() - start_time
 
start_time = now()
visited_bfs = bfs(graph, 1)
bfs_time = now() - start_time
 
println("DFS Tiempo de ejecución: $dfs_time")
println("BFS Tiempo de ejecución: $bfs_time")
 

dXNpbmcgUmFuZG9tCnVzaW5nIERhdGVzICAjIFBhcmEgbWVkaXIgZWwgdGllbXBvIGRlIGVqZWN1Y2nDs24KCiMgRGVmaW5pciBlbCBncmFmbyBjb21vIHVuIGRpY2Npb25hcmlvIGRlIGxpc3RhcyBkZSBhZHlhY2VuY2lhCmZ1bmN0aW9uIGNyZWF0ZV9ncmFwaChub2Rlczo6SW50LCBlZGdlczo6SW50KQogICAgZ3JhcGggPSBEaWN0e0ludCwgVmVjdG9ye0ludH19KCkKICAgIGZvciBpIGluIDE6bm9kZXMKICAgICAgICBncmFwaFtpXSA9IFtdCiAgICBlbmQKICAgIGZvciBfIGluIDE6ZWRnZXMKICAgICAgICB1ID0gcmFuZCgxOm5vZGVzKQogICAgICAgIHYgPSByYW5kKDE6bm9kZXMpCiAgICAgICAgcHVzaCEoZ3JhcGhbdV0sIHYpCiAgICBlbmQKICAgIHJldHVybiBncmFwaAplbmQKCiMgSW1wbGVtZW50YWNpw7NuIGRlIERGUwpmdW5jdGlvbiBkZnMoZ3JhcGg6OkRpY3R7SW50LCBWZWN0b3J7SW50fX0sIHN0YXJ0OjpJbnQpCiAgICB2aXNpdGVkID0gU2V0e0ludH0oKQogICAgc3RhY2sgPSBbc3RhcnRdCiAgICB3aGlsZSAhaXNlbXB0eShzdGFjaykKICAgICAgICBub2RlID0gcG9wIShzdGFjaykKICAgICAgICBpZiBub2RlIOKIiSB2aXNpdGVkCiAgICAgICAgICAgIHB1c2ghKHZpc2l0ZWQsIG5vZGUpCiAgICAgICAgICAgIGZvciBuZWlnaGJvciBpbiBncmFwaFtub2RlXQogICAgICAgICAgICAgICAgcHVzaCEoc3RhY2ssIG5laWdoYm9yKQogICAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAgIGVuZAogICAgcmV0dXJuIHZpc2l0ZWQKZW5kCgojIEltcGxlbWVudGFjacOzbiBkZSBCRlMKZnVuY3Rpb24gYmZzKGdyYXBoOjpEaWN0e0ludCwgVmVjdG9ye0ludH19LCBzdGFydDo6SW50KQogICAgdmlzaXRlZCA9IFNldHtJbnR9KCkKICAgIHF1ZXVlID0gW3N0YXJ0XQogICAgd2hpbGUgIWlzZW1wdHkocXVldWUpCiAgICAgICAgbm9kZSA9IHBvcGZpcnN0IShxdWV1ZSkKICAgICAgICBpZiBub2RlIOKIiSB2aXNpdGVkCiAgICAgICAgICAgIHB1c2ghKHZpc2l0ZWQsIG5vZGUpCiAgICAgICAgICAgIGZvciBuZWlnaGJvciBpbiBncmFwaFtub2RlXQogICAgICAgICAgICAgICAgcHVzaCEocXVldWUsIG5laWdoYm9yKQogICAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAgIGVuZAogICAgcmV0dXJuIHZpc2l0ZWQKZW5kCgojIENvbmZpZ3VyYXIgZWwgZ3JhZm8Kbm9kZXMgPSAxMDAwICAjIENhbWJpYSBlc3RlIHZhbG9yIHBhcmEgbW9kaWZpY2FyIGVsIHRhbWHDsW8KZWRnZXMgPSA1MDAwICAjIENhbWJpYSBlc3RlIHZhbG9yIHBhcmEgbW9kaWZpY2FyIGVsIHRhbWHDsW8KZ3JhcGggPSBjcmVhdGVfZ3JhcGgobm9kZXMsIGVkZ2VzKQoKIyBUZW1wb3JpemFkb3IgeSBlamVjdWNpw7NuCnN0YXJ0X3RpbWUgPSBub3coKQp2aXNpdGVkX2RmcyA9IGRmcyhncmFwaCwgMSkKZGZzX3RpbWUgPSBub3coKSAtIHN0YXJ0X3RpbWUKCnN0YXJ0X3RpbWUgPSBub3coKQp2aXNpdGVkX2JmcyA9IGJmcyhncmFwaCwgMSkKYmZzX3RpbWUgPSBub3coKSAtIHN0YXJ0X3RpbWUKCnByaW50bG4oIkRGUyBUaWVtcG8gZGUgZWplY3VjacOzbjogJGRmc190aW1lIikKcHJpbnRsbigiQkZTIFRpZW1wbyBkZSBlamVjdWNpw7NuOiAkYmZzX3RpbWUiKQo=