Katia@cin.ufpe.br1 Busca em Grafos Katia S. Guimarães katia@cin.ufpe.br

  • View
    125

  • Download
    10

Embed Size (px)

Text of Katia@cin.ufpe.br1 Busca em Grafos Katia S. Guimarães katia@cin.ufpe.br

  • Slide 1
  • katia@cin.ufpe.br1 Busca em Grafos Katia S. Guimares katia@cin.ufpe.br
  • Slide 2
  • 2 Busca em Grafos OBJETIVO: Visitar todos os vrtices e arestas do grafo de forma sistemtica, para evitar repeties e conseqente desperdcio. Se o grafo uma rvore enraizada, isto , uma rvore na qual os vrtices obedecem a uma hierarquia, a tarefa simples.
  • Slide 3
  • katia@cin.ufpe.br3 Busca em rvores Enraizadas 1.Busca em pr-ordem Raiz visitada antes dos descendentes A B C E F D
  • Slide 4
  • katia@cin.ufpe.br4 Busca em rvores Enraizadas 2. Busca em ps-ordem Raiz visitada depois dos descendentes B E F C D A
  • Slide 5
  • katia@cin.ufpe.br5 Busca em rvores Enraizadas 3. Busca em in-ordem Raiz visitada entre os descendentes S faz sentido para rvores binrias ou similares (2-3, B, etc.) (Applet)
  • Slide 6
  • katia@cin.ufpe.br6 Algoritmo Pr-ordem Algoritmo Pr-ordem(raiz) Se raiz no nula ento Visite (raiz) Pr-ordem (left.raiz) Pr-ordem (right.raiz)
  • Slide 7
  • katia@cin.ufpe.br7 Algoritmo Ps-ordem Algoritmo Ps-ordem(raiz) Se raiz no nula ento Ps-ordem (left.raiz) Ps-ordem (right.raiz) Visite (raiz)
  • Slide 8
  • katia@cin.ufpe.br8 Algoritmo In-ordem Algoritmo In-ordem(raiz) Se raiz no nula ento In-ordem (left.raiz) Visite (raiz) In-ordem (right.raiz)
  • Slide 9
  • katia@cin.ufpe.br9 Busca em Grafos com Ciclos Se o grafo contm ciclos, preciso cuidar para evitar que arestas sejam visitadas mais de uma vez. 37 2 5 1 4 6
  • Slide 10
  • katia@cin.ufpe.br10 Busca em Grafos com Ciclos Exemplo: A partir do grafo abaixo obtemos 37 2 5 1 4 6 1 6 4 2 3 75
  • Slide 11
  • katia@cin.ufpe.br11 Busca em Grafos com Ciclos Se o grafo no uma rvore, ns definimos um subgrafo dele que uma rvore, para servir de espinha dorsal. Algoritmo bsico: Tome um vrtice qualquer s. Marque s. Enquanto houver arestas no visitadas, tome uma aresta (v, w) incidente a algum vrtice j marcado. Marque (v, w) (explorada) e v, w (visitados).
  • Slide 12
  • katia@cin.ufpe.br12 Busca em Grafos com Ciclos H duas tcnicas principais para busca: Busca em Profundidade Tomar a aresta no marcada incidente ao vrtice visitado mais recentemente. Busca em Largura Tomar a aresta no marcada incidente ao vrtice visitado menos recentemente.
  • Slide 13
  • katia@cin.ufpe.br13 Busca em Profundidade JAVA Applet para uma Busca em Profundidade JAVA Applet para Busca em grafo direcionado com pilha
  • Slide 14
  • katia@cin.ufpe.br14 Controle para Busca em Profundidade Main Procedure Inicialize pilha Q como vazia; Desmarque todos os vrtices e arestas; Tome um vrtice v qualquer; Inclua v em Q; P(v); Remova v de Q.
  • Slide 15
  • katia@cin.ufpe.br15 Algoritmo para Busca em Profundidade Procedimento P(v) Marque v como visitado; Para toda aresta (v, w) incidente a v faa: Se w no marcado ento /* aresta de rvore */ { Inclua w em Q; P(w) Remova w de Q } seno se w pai(v) ento /* aresta de retorno */ seno /* aresta de rvore */
  • Slide 16
  • katia@cin.ufpe.br16 Busca em Profundidade A busca em profundidade biparticiona o conjunto de arestas em: 37 2 5 1 4 6 - Arestas de rvore - Arestas de Retorno 1 6 4 2 3 75
  • Slide 17
  • katia@cin.ufpe.br17 Variaes de Busca em Profundidade O algoritmo de Busca em Profundidade usado como controle para muitas aplicaes em tempo linear. Ex. Componentes Biconexos (Tolerncia a falhas em redes) Ex: No grafo ao lado, os seguintes subgrafos gerados permanecem conexos se cair um link qualquer: G {1, 6} G {3, 7} G {1, 2, 3, 4, 5} 1 6 4 2 3 75
  • Slide 18
  • katia@cin.ufpe.br18 Busca em Largura Cria um centro no vrtice inicial e forma nveis ou camadas a partir deste n. 37 2 5 1 4 6 1 6 45 23 7
  • Slide 19
  • katia@cin.ufpe.br19 Busca em Largura Applet para Busca em Largura
  • Slide 20
  • katia@cin.ufpe.br20 Algoritmo para Busca em Largura Tome um vrtice qualquer v. Coloque v na fila F. Enquanto F no for vazia faa v Primeiro elemento da fila F Para toda aresta (v, w) incidente a v faa Se w no marcado ento Inclua w em F /* aresta de rvore */ seno se v = pai (w) ento /* aresta de rvore */ seno /* aresta de cruzamento */
  • Slide 21
  • katia@cin.ufpe.br21 Busca em Largura A busca em largura biparticiona as arestas do grafo em arestas de rvore e arestas de cruzamento. 37 2 5 1 4 6 1 6 45 23 7
  • Slide 22
  • katia@cin.ufpe.br22 Variaes de Busca em Largura O algoritmo de Busca em Largura tambm largamente usado como controle para aplicaes em tempo linear. Ex. Broadcast de mensagens em uma rede