Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 25 visualizações

    Teoria Dos Grafos: Márcio Antônio Duarte UFG - Ciência Da Computação

    Enviado por

    arthurborgesmartins3
    O documento discute a teoria dos grafos e algoritmos de busca em grafos, especificamente busca em largura (BFS). O BFS explora todos os vértices a uma distância k de um vértice inicial antes de explorar vértices a uma distância k+1, permitindo descobrir todos os vértices alcançáveis a partir do vértice inicial. O documento fornece exemplos de como o BFS opera em grafos e discute conceitos relacionados como grafos acíclicos e árvores.

    Direitos autorais:

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

    Teoria Dos Grafos: Márcio Antônio Duarte UFG - Ciência Da Computação

    Enviado por

    arthurborgesmartins3
    25 visualizações23 páginas
    O documento discute a teoria dos grafos e algoritmos de busca em grafos, especificamente busca em largura (BFS). O BFS explora todos os vértices a uma distância k de um vértice inicial antes de explorar vértices a uma distância k+1, permitindo descobrir todos os vértices alcançáveis a partir do vértice inicial. O documento fornece exemplos de como o BFS opera em grafos e discute conceitos relacionados como grafos acíclicos e árvores.

    Descrição original:

    .

    Título original

    BFS

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    O documento discute a teoria dos grafos e algoritmos de busca em grafos, especificamente busca em largura (BFS). O BFS explora todos os vértices a uma distância k de um vértice inicial antes de explorar vértices a uma distância k+1, permitindo descobrir todos os vértices alcançáveis a partir do vértice inicial. O documento fornece exemplos de como o BFS opera em grafos e discute conceitos relacionados como grafos acíclicos e árvores.

    Direitos autorais:

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

    Teoria Dos Grafos: Márcio Antônio Duarte UFG - Ciência Da Computação

    Enviado por

    arthurborgesmartins3
    O documento discute a teoria dos grafos e algoritmos de busca em grafos, especificamente busca em largura (BFS). O BFS explora todos os vértices a uma distância k de um vértice inicial antes de explorar vértices a uma distância k+1, permitindo descobrir todos os vértices alcançáveis a partir do vértice inicial. O documento fornece exemplos de como o BFS opera em grafos e discute conceitos relacionados como grafos acíclicos e árvores.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    Você está na página 1de 23

    TEORIA DOS GRAFOS

    Márcio Antônio Duarte

    UFG – Ciência da Computação

    email: marcioaduarte@gmail.com
    Busca em Grafos

    Percorrer um grafo é um problema fundamental;


    Deve-se ter uma forma sistemática de visitar as
    arestas e os vértices;


    O algoritmo deve ser suficientemente flexível para se
    adequar à diversidade de grafos.
    Busca em Grafos

    Como saber se existe caminho entre dois vértices de
    maneira eficiente?


    Ideia: evitar explorar vértices já explorados

    marcar os vértices!

    vértice: não visitados, visitados e processados.
    Busca em Grafos

    Solução
    Manter uma lista de vértices no estado visitados;


    Há duas possibilidades:

    Busca em largura (usando uma fila);


    Busca em profundidade (usando uma pilha).
    BFS (Busca em Largura)
    BFS –Breadth-First Search


    Todos os nós com distância k a um nó v são
    visitados antes dos nós com distância k+1;


    Descobre todos os vértices alcançáveis a partir de
    v.
    BFS (Busca em Largura)
    BFS –Breadth-First Search (Algoritmo Genérico):

    Passo inicial

    desmarcar todos os vértices;

    selecionar origem e marcá-lo visitado;

    Passo geral (enquanto houver vértice não-visitado)

    Selecionar vértice visitado, u;

    Considerar aresta não explorada, (u, v);

    Se v não estiver marcado, marcar v como
    visitado;

    Marcar u processado quando não houver mais
    arestas incidentes a u a serem exploradas.
    BFS (Busca em Largura)

    Ordem de visita dos vértices e arestas?
    Algoritmo genérico não
    estabelece ordem!


    Qual é uma possível ordem?

    Sistemática de exploração

    Duas abordagens

    Explorar o vértice descoberto “mais antigo”;

    Explorar o vértice descoberto “mais recente.
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q:
    Resultado:
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q:
    Resultado:
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q: 2, 5, 6
    Resultado: 2, 5, 6
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q: 5, 6, 3
    Resultado: 2, 5, 6, 3
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q: 6, 3, 4
    Resultado: 2, 5, 6, 3, 4
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q: 3, 4
    Resultado: 2, 5, 6, 3, 4
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q: 4
    Resultado: 2, 5, 6, 3, 4
    BFS (Busca em Largura)
    Percorrendo um Grafo: BFS

    Q:
    Resultado: 2, 5, 6, 3, 4
    BFS (Busca em Largura)
    Interpretação

    Onda é propagada à partir da raiz;

    Onda expande em círculos, descobrindo vértices
    alcançáveis!
    BFS (Busca em Largura)
    Percorrendo um Grafo: árvore de busca em largura:

    As arestas (2,5) e (3,4) não percorridas!


    BFS (Busca em Largura)
    BFS –Breadth-First Search

    Em grafos não-dirigidos, cada aresta é visitada
    somente duas vezes;

    Em grafos dirigidos, cada aresta é visitada uma
    única vez;

    Em geral, armazena-se a distânciade cada nó em
    relação ao nó inicial onde a busca se iniciou;

    Exemplo: aplicações de caminho mais curto!

    É comum a utilização de esquemas de cores para
    identificar os nós ainda não visitados (branco),
    visitados (cinza) e já completamente processados
    (preto)!
    BFS (Busca em Largura)
    Exercício: faça a busca em largura no grafo abaixo,
    mostrando a ordem de visita aos vértices.
    BFS (Busca em Largura)
    Exercício: faça a busca em largura no grafo abaixo,
    mostrando a ordem de visita aos vértices.
    BFS (Busca em Largura)
    Grafo Acíclico
    ●
    Grafo acíclico é um grafo que não possui ciclos.

    Exemplo:
    ●
    K4 é acíclico?

    ●
    Como descobrir se um grafo é acíclico?
    BFS (Busca em Largura)
    Árvores
    - Uma árvore é um grafo acíclico conexo.
    - Folha: vértice com grau 1;
    - Raiz: um determinado vértice define orientação na
    árvore (pai, filhos, descendentes e ancestrais)

    ●
    Quantos caminhos (simples) distintos existe entre dois
    vértices quaisquer?
    ●
    Quantas arestas possui uma árvore com n vértices?
    BFS (Busca em Largura)
    Árvore Geradora
    ●
    Subgrafo que contém todos os vértices de G e é uma
    árvore.

    Você também pode gostar