Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 31 visualizações

    Trabalho de Grafos 2023.2

    Enviado por

    João Victor Zezinho
    Este documento descreve um trabalho de implementação sobre algoritmos em grafos. Os alunos devem implementar um algoritmo que carrega um grafo direcionado de um arquivo de texto e executa o algoritmo DFS, começando pelo vértice com maior grau de saída. O algoritmo deve imprimir os vetores d e f e classificar as arestas de acordo com o DFS. O trabalho deve ser entregue em Python, C ou Java e pode ser feito em grupos de até 4 pessoas.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    Trabalho de Grafos 2023.2

    Enviado por

    João Victor Zezinho
    31 visualizações2 páginas
    Este documento descreve um trabalho de implementação sobre algoritmos em grafos. Os alunos devem implementar um algoritmo que carrega um grafo direcionado de um arquivo de texto e executa o algoritmo DFS, começando pelo vértice com maior grau de saída. O algoritmo deve imprimir os vetores d e f e classificar as arestas de acordo com o DFS. O trabalho deve ser entregue em Python, C ou Java e pode ser feito em grupos de até 4 pessoas.

    Título original

    Trabalho de Grafos 2023.2 (1)

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    Este documento descreve um trabalho de implementação sobre algoritmos em grafos. Os alunos devem implementar um algoritmo que carrega um grafo direcionado de um arquivo de texto e executa o algoritmo DFS, começando pelo vértice com maior grau de saída. O algoritmo deve imprimir os vetores d e f e classificar as arestas de acordo com o DFS. O trabalho deve ser entregue em Python, C ou Java e pode ser feito em grupos de até 4 pessoas.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    31 visualizações2 páginas

    Trabalho de Grafos 2023.2

    Enviado por

    João Victor Zezinho
    Este documento descreve um trabalho de implementação sobre algoritmos em grafos. Os alunos devem implementar um algoritmo que carrega um grafo direcionado de um arquivo de texto e executa o algoritmo DFS, começando pelo vértice com maior grau de saída. O algoritmo deve imprimir os vetores d e f e classificar as arestas de acordo com o DFS. O trabalho deve ser entregue em Python, C ou Java e pode ser feito em grupos de até 4 pessoas.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    de 2

    Trabalho de Implementação (T1)

    RUS0300 - Algoritmos em Grafos


    Semestre 2023.2

    Questão 1. Implemente um algoritmo que carregue as informações de um grafo direcionado que estão
    em um arquivo de texto (padrão de arquivo visto em sala). Em seguida execute o algoritmo DFS no
    grafo carregado obedecendo os itens a seguir:
    1. Você pode armazenar o grafo na estrutura de dados que desejar;
    a. Use precedência alfabética/numérica para armazenar os dados do grafo na estrutura;
    2. O seu DFS deve iniciar a busca pelo vértice que tem maior grau de saída;
    a. Caso precise reiniciar o DFS, escolha o vértice que tem o segundo maior grau de
    saída, depois o terceiro e assim por diante.
    3. Como resposta, o seu algoritmo deve imprimir na tela:
    a. Os valores do vetor d e f;
    b. A nomenclatura de todas as arestas (Aresta de Árvore, Aresta de Retorno, Aresta de
    Avanço ou Aresta de Cruzamento) do grafo carregado de acordo com o DFS
    executado.

    Obs: Informações sobre a implementação:


    ● Implemente seu código em linguagem Python ou C ou Java;
    ● A equipe do trabalho pode ser de até 4 discentes;
    ● Valor mínimo do trabalho 2,0 pontos na primeira ou segunda prova;
    ○ Você(s) pode(m) ganhar mais 1,0 ponto caso tenha interface gráfica simulando os
    passos do algoritmo em cores;
    ● Seu algoritmo será testado com os grafos do Professor que estão em um arquivo .txt cada;
    ● Se for detectado plágio, códigos gerados via Chat Gpt ou similares, então toda a equipe
    terá a nota da segunda prova zerada;
    ● Sobre o envio do trabalho:
    ○ Criar uma pasta com todos os códigos;
    ○ Adicionar um arquivo .txt com nome completo e matrícula dos discentes da equipe;
    ○ Zipar a pasta e enviar um único arquivo dos códigos pela tarefa aberta no Sigaa;
    ○ Cada discente deve enviar o arquivo zipado
    ○ Data máxima de envio: 20/11/2023

    UNIVERSIDADE FEDERAL DO CEARÁ - CAMPUS DE RUSSAS


    Avenida Felipe Santiago, 411, Bairro Campo Federal, CEP: 62900-420
    Telefone: (88) 3411-9218 | E-mail: [email protected] | Site: russas.ufc.br
    Simulação do Grafo do Slide da Aula
    Arquivo G1.txt
    8 14 D
    hh
    ab
    bc
    ea
    be
    bf
    cd
    gf
    cg
    dc
    dh
    ef
    fg
    gh

    Resultado do DFS a partir do vértice b (maior grau de saída).


    b c: Árvore
    c d: Árvore
    d c: Retorno
    d h: Árvore
    h h: Retorno
    c g: Árvore
    g f: Árvore
    f g: Retorno
    g h: Cruzamento
    b e: Árvore
    e a: Árvore
    a b: Retorno
    e f: Cruzamento
    b f: Avanço

    vetor d: [13, 1, 2, 3, 12, 8, 7, 4]


    vetor f: [14, 16, 11, 6, 15, 9, 10, 5]

    UNIVERSIDADE FEDERAL DO CEARÁ - CAMPUS DE RUSSAS


    Avenida Felipe Santiago, 411, Bairro Campo Federal, CEP: 62900-420
    Telefone: (88) 3411-9218 | E-mail: [email protected] | Site: russas.ufc.br

    Você também pode gostar