Buscas-em-Grafos-DFS-e-BFS

Otimização em Grafos Buscas em Grafos Bruno Masquio 2 Grafos Buscas em Grafos Idéia Visitar a cada passo algum vizinho não visitado de vértices já visitados Buscas em Grafos Busca em Profundidade DFS Depth First Search Busca em Largura BFS Breadth First Search Busca Irrestrita em Profundidade 3 Grafos Busca em Profundidade DFS Idéia Visitar a cada passo algum vizinho não visitado do vértice mais recentemente visitado 1 2 3 5 4 6 Buscas em Grafos Ex A sequência 2 1 3 5 6 4 é uma DFS Ex A sequência 2 1 3 4 5 6 NÃO é uma DFS Grafos Busca em Profundidade DFS Idéia Visitar a cada passo algum vizinho não visitado do vértice mais recentemente visitado dfspai v marcar v marcadov 1 para vizinhos w de v se w não marcado dfsvw Buscas em Grafos Cada vértice visitado é marcado Normalmente usase um vetor para isso desmarcar vértices marcado 0 para i de 1 até n se i não marcado dfsii Apenas o parâmetro v de DFSpai v foi usado nesta versão da busca Muitas vezes é necessário usar os dois Podem ser usadas várias convenções para marcação a 01 b 0número do componente c 0ordem da visita desmarcadomarcado Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvore de Profundidade 6 5 3 1 4 2 Buscas em Grafos Após dfs22 2 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 6 5 3 1 4 2 1 2 Buscas em Grafos Após dfs21 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 3 6 5 3 1 4 2 1 2 Buscas em Grafos Após dfs13 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 5 3 1 2 Buscas em Grafos Após dfs35 6 5 3 1 4 2 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 4 5 3 1 2 Buscas em Grafos Após dfs54 6 5 3 1 4 2 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 6 4 5 3 1 2 Buscas em Grafos Após o retorno de dfs56 6 5 3 1 4 2 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 6 4 5 3 1 2 Buscas em Grafos Após dfs56 6 5 3 1 4 2 Grafos Busca em Profundidade Árvores Floresta de Profundidade são as árvores da recursão da busca Árvores de Profundidade 6 5 3 1 4 12 2 1 5 6 3 4 2 Buscas em Grafos 6 4 5 3 1 2 13 Busca em Profundidade DFS Matriz de Adjacência dfspai v cont cont1 prev cont para w 1n incl se Evw 1 e prew 0 dfsvw Buscas em Grafos Complexidade θn2 A marcação feita é guardando a ordem de visita no vetor ordem para i de 1 até n prei 0 cont 0 para i de 1 até n se prei 0 dfsii 14 Busca em Profundidade DFS Lista de Adjacência LA dfspai v cont cont 1 prev cont w LAv enquanto w nulo se prewvertice 0 dfsv wvertice w wprox para i de 1 até n prei 0 contador 0 para i de 1 até n se prei 0 dfsii Buscas em Grafos Complexidade θnm A marcação feita é guardando a ordem de visita no vetor ordem ordemv 0 significa que v não foi visitado struct adj LA adj int vertice adj prox Grafos Árvores revisão G é uma árvore é equivalente a dizer que duas das 3 condições são verdadeiras G é conexo G é acíclico EG VG 1 m n1 6 5 3 1 4 2 Buscas em Grafos Grafos Busca em Profundidade Árvores Florestas de Profundidade Mostram a sequência das visitas Pode haver mais de uma árvore de profundidade Árvores de Profundidade 6 5 3 1 4 2 Buscas em Grafos 6 4 5 3 1 2 1 2 3 4 5 6 16 2 1 5 6 3 4 Arestas de retorno Aresta de árvore 17 Grafos Busca em Profundidade DFS Propriedade I da DFS Todos os vértices e todas as arestas são visitados na busca Buscas em Grafos Propriedade II da DFS A complexidade da busca é θn2 se for usada a representação por matriz de adjacências Propriedade III da DFS A complexidade da busca é θnm se for usada a representação por listas de adjacências Propriedade IV da DFS Dado qualquer caminho C em G existe um vértice v desse caminho tal que todos os demais vértices do caminho estão em nós descendentes de v na árvore de profundidade de G 18 Grafos Busca em Profundidade Possibilidades da DFS Pequenas modificações no algoritmo permitem descobrir propriedades do grafo 1 2 3 5 4 6 Visita a todas as arestas Obtenção dos graus dos vértices Determinação se o grafo é conexo Determinação das componentes conexas Determinação de existência de ciclos Descoberta de elementos estruturais pontes blocos etc Descoberta se o grafo é bipartido ciclo árvore completo regular Buscas em Grafos 19 Grafos Busca em Profundidade Possibilidades da DFS Determinar se o grafo é conexo 1 2 3 5 4 6 desmarca vértices componentes 0 para i de 1 até n se i não marcado componentes componentes1 dfsii se componentes 1 escrever Desconexo senão escrever Conexo Buscas em Grafos 20 Grafos Busca em Profundidade Possibilidades da DFS Determinação dos componentes conexos 1 2 3 5 4 6 compConexa 0 contador 0 para i de 1 até n se compConexai 0 contador contador 1 dfsii para i de 1 até contador escreverComponente i para j de 1 até n se compConexaj i escreverj dfspai v compConexav contador para vizinhos w de v se compConexaw 0 dfsvw Buscas em Grafos 21 Grafos Busca em Profundidade Possibilidades da DFS Determinação de existência de ciclos 1 2 3 5 4 6 marcado 0 temCiclo F para i de 1 até n se marcadoi 0 temCiclo temCiclo ou dfsii se temCiclo escrever O grafo é cíclico senão escrever O grafo é acíclico bool dfspai v marcadov 1 para vizinhos w de v se marcadow 0 se dfsvw retornar V senão se w pai retornar V retornar F 22 Grafos Busca em Profundidade Problema ORIENTAÇÃO ACÍCLICA Dado um grafo simples orientar cada aresta do grafo transformálo em um digrafo tal que não hajam ciclos no digrafo criado 1 2 3 5 6 4 Buscas em Grafos 23 Grafos Busca em Profundidade 1 2 4 6 5 3 1 2 4 6 5 3 OK NÃO Problema ORIENTAÇÃO PARA DAG Dado um grafo simples orientar cada aresta do grafo transformálo em um digrafo tal que não hajam ciclos no digrafo criado Buscas em Grafos 24 Grafos Busca em Profundidade Solução ORIENTAÇÃO PARA DAG Criar a árvore de profundidade Arestas de árvore tornamse arestas diretas Arestas de retorno tornamse arestas inversas 5 3 1 2 6 4 6 3 5 4 1 2 1 2 4 6 5 3 Buscas em Grafos 25 Busca em Profundidade II DFS Matriz de Adjacências dfsuv contPre contPre1 prev contPre para w 1 até n incl se Evw 1 e prew 0 dfsvw contadorSaida contadorSaida 1 ordemSaidav contadorSaida para i 1 até n incl prei 0 ordemSaidai 0 contPre 0 contadorSaida 0 para i 1 até n incl se prei 0 dfsii Buscas em Grafos Complexidade On2 26 Árvore Floresta de Profundidade Árvore de Profundidade 6 4 2 1 5 6 3 4 5 3 6 5 3 1 4 2 1 2 Buscas em Grafos 1 2 3 4 5 6 Arestas de retorno Aresta de árvore Grafos Busca em Profundidade II DFS MA 6 5 4 3 1 2 Grafos Pontes Ponte Aresta que se removida desconecta o grafo Ex 56 1 2 3 5 4 6 Idéia de um algoritmo Dada uma árvore de profundidade a aresta vw será ponte quando w é filho de v e não há descendentes de w incluindo w com arestas de retorno para ancestrais de w 7 8 3 5 4 2 1 8 7 6 Buscas em Grafos 28 Grafos Pontes Ponte Aresta que se removida desconecta o grafo Ex 56 1 2 4 6 Idéia de um algoritmo Funções p os vértices prev ordem de entrada de v na DFS lowv menor ordem de entrada de um vértice alcançado diretamente por v ou por descendente de v na árvore de profund usando no máximo uma aresta de retorno 7 8 5 3 v pre low 1 1 1 2 2 1 4 3 1 5 4 1 3 5 1 6 6 6 7 7 6 8 8 6 Buscas em Grafos Conclusão Aresta 56 é ponte 3 5 4 2 1 8 7 6 29 Grafos Pontes pontespai v contador contador 1 prev contador lowv contador para vizinhos w de v se prew 0 se w não foi visitado pontesv w se loww prewse w não alcança ninguém visitado antes de w por aresta de retorno escrever v w é Ponte lowv minlowv loww atualiza o lowv baseado no descendente w senão se w pai aresta de retorno wv encontrada lowv minlowv prewv alcança w por aresta de retorno pre 0 contador 0 para i 1n incl se prei0 pontesii Buscas em Grafos 1 2 3 5 4 6 7 8 Grafos Pontes 1 2 3 5 4 6 7 8 Exemplo de ordem e low com a Busca começando no vértice 1 Buscas em Grafos Grafos Pontes 1 2 3 5 4 6 7 8 Exemplo de ordem e low com a Busca começando no vértice 1 Buscas em Grafos 1 1 2 2 1 3 3 1 4 4 1 5 51 6 6 7 7 6 8 8 6 Grafos Pontes 1 2 3 5 4 6 7 8 Exemplo com a Busca começando no vértice 1 v 1 2 3 4 5 6 7 8 P L P L P L P L P L P L P L P L 1 1 1 2 1 1 2 2 4 1 1 2 2 3 3 5 1 1 2 2 3 3 4 4 3 1 1 2 2 5 1 3 3 4 1 6 1 1 2 2 5 1 3 3 4 1 6 6 7 1 1 2 2 5 1 3 3 4 1 6 6 7 7 8 1 1 2 1 5 1 3 1 4 1 6 6 7 6 8 6 Buscas em Grafos P ordem e L low Grafos Articulações Articulação Vértice que se removido aumenta o número de componentes conexas do grafo Ex 5 1 2 3 5 4 6 Idéia de um algoritmo Dada uma árvore de profund o vértice v é ponto de articulação se a v é raiz da árvprof e tem mais de um filho ou b v não é raiz tem um filho w e não há descendentes de w incluindo o próprio com arestas de retorno para ancestrais de v 7 8 Buscas em Grafos 3 5 4 2 1 8 7 6 34 Grafos Pontos de Articulação Ponto de articulação Vértice que se removido desconecta o grafo Ex 5 1 2 4 6 Idéia de um algoritmo Funções p vértices prev e lowv como para pontes pav número de filhos de v que não alcançam ancestrais de v na árv prof 7 8 3 5 4 2 1 8 7 6 5 3 v pre low pa 1 1 1 1 2 2 1 0 4 3 1 0 5 4 1 1 3 5 1 0 6 6 6 1 7 7 6 0 8 8 6 0 Buscas em Grafos 35 Grafos Pontos de Articulação 1 2 3 5 4 6 pontospai v contador contador1 prev contador lowv contador pav 0 para vizinhos w de v se prew 0 pontosv w se prev loww pav pav1 lowv minlowv loww senão se w pai lowv minlowv prew 7 8 36 Grafos Pontos de Articulação 1 2 3 5 4 6 7 8 pre 0 cont 0 low 0 pa 0 raizDfs false para i de 1 até n se prei 0 raizDfsi true pontosi i para i de 1 até n incl se raizDfsi e pai 1 escrever vertice i é ponto de articulação senão se não raizDfsi e pai 0 escrever vertice i é ponto de articulação Externamente 37 Grafos Pontos de Articulação 1 3 2 6 4 5 Exemplo com a Busca começando no vértice 1 pre low pa 38 Grafos Pontos de Articulação 1 3 2 6 4 5 Exemplo com a Busca começando no vértice 1 110 pre low pa 220 330 440 310 540 660 441 550 311 640 210 111 Grafos Pontos de Articulação 1 3 2 6 4 5 Exemplo com a Busca começando no vértice 1 pre low pa pre low pa pre low pa pre low pa pre low pa pre low pa v 1 2 3 4 5 6 1 1 1 0 2 1 1 0 2 2 0 3 1 1 0 2 2 0 3 1 0 6 1 1 0 2 2 0 3 1 0 4 4 0 4 1 1 0 2 2 0 3 1 0 5 5 0 4 4 0 5 1 1 1 2 1 0 3 1 1 5 4 0 6 4 0 4 4 1 40 Grafos Componentes biconexas 1 2 3 5 4 6 Componente biconexa subgrafo maximal tal que ou seja uma aresta ou haja pelo menos dois caminhos distintos entre cada par de vértices do subgrafo É equivalente a dizer que cada par de vértices da componente biconexa quando há mais de 2 vértices na componente faz parte de um ciclo 7 8 Componentes biconexas do exemplo 12345 56 678 41 Grafos Componentes biconexas Marcador Vértice w que tem loww ordempaiw 1 2 3 5 4 6 Idéia de um algoritmo o marcador w mais embaixo da árvore de profundidade determina um componente elementos da subárvore com raiz em w paiw Removida essa componente aplicase recursão no grafo restante a Fazer dfs identificando marcadores e empilhando as arestas visitadas b Quando um marcador w é encontrado desempilhamse as arestas até a aresta w paiw inclusive 7 8 42 1 2 3 5 4 6 7 8 desmarcar vérticesarestas pilha s sesvazia cont 0 para i de 1 até n se prei 0 blocosi i Externamente Grafos Componentes biconexos 43 Grafos Componentes biconexos 1 2 3 5 4 6 blocospai v cont cont1 prev cont lowv cont se v não tem arestas adicionar a componente biconexa v para vizinhos w de v se wv não marcada sempilhaw v marcar w v se prew 0 blocosv w se prev loww desempilhar s até w v vw incluso lowv minlowv loww senão se w pai lowv minlowv prew 7 8 44 Grafos Determinação de Blocos 1 3 2 6 4 Exemplo com a Busca começando no vértice 1 P L P L P L P L P L P L v 1 2 3 4 5 6 12 23 13 36 46 45 1 1 1 2 1 1 2 2 3 1 1 2 2 3 1 6 1 1 2 2 3 1 4 4 4 1 1 2 2 3 1 5 5 4 4 5 1 1 2 1 3 1 5 4 6 4 4 4 56 5 Grafos Determinação de Blocos 1 3 2 6 4 Exemplo com a Busca começando no vértice 1 P L P L P L P L P L P L v 1 2 3 4 5 6 1 13 23 12 3 36 1 1 1 2 1 1 2 2 6 56 45 46 3 1 1 2 2 3 1 6 1 1 2 2 3 1 4 4 4 1 1 2 2 3 1 5 5 4 4 5 1 1 2 1 3 1 5 4 6 4 4 4 5 46 Grafos Busca em Largura BFS Idéia Visitar a cada passo algum vizinho não visitado do vértice mais antigamente visitado 1 2 3 5 4 6 Buscas em Grafos 47 Grafos Busca em Largura BFS Idéia Visitar a cada passo algum vizinho não visitado do vértice mais antigamente visitado bfsv fila q qenfilavv marcar v enquanto q não vazia pt elemento inicial de q para vizinhos w de t se w não marcado qenfilatw marca w qdesenfila desmarca vértices para i de 1 até n se i não marcado bfsi 48 Grafos Busca em Largura Árvores de Largura Mostram a sequência das visitas Pode haver mais de uma árvore de largura Árvores de Largura 1 3 4 6 2 1 6 3 5 4 5 2 6 5 3 4 2 1 49 Grafos Busca em Largura BFS MA bfsp v fila q qenfilapv prev contPre enquanto q não vazia pt elemento inicial de q para w de 1 até n se Etw 1 e prew 0 qenfilavw prew contPre qdesenfila pre 0 contPre 0 para i de 1 até n se prei 0 bfsii Complexidade On2 50 Grafos Busca em Largura Árvores de Largura Mostram a sequência das visitas Pode haver mais de uma árvore de largura Árvores de Largura 1 3 4 6 2 1 6 3 5 4 5 2 6 5 3 4 2 1 Aresta de cruzamento 1 3 2 6 4 5 51 Grafos Busca em Largura BFS LA bfspai v fila q qesvazia qenfilapv prev contador enquanto Q não vazia paiV v elemento inicial de q w Av enquanto w nulo se prewvertice 0 qenfilaw wvertice prewv cpre w wprox qdesenfila para i de 1 até n prei 0 contador 0 para i de 1 até n se prei 0 bfsAii Complexidade Onm 52 Grafos Busca em Largura Propriedades importantes da BFS 1 2 3 5 4 6 a Durante a BFS os vértices são enfilados por ordem de distância ao vértice da raiz da busca b Para qualquer nó da árvore de largura o caminho da raiz até esse nó é um caminho mínimo entre os dois nós 2 1 6 3 5 4 Distâncias para o vértice 2 1 4 e 5 estão à distância 1 3 e 6 à distância 2 Menor caminho de 2 a 6 2 5 6 Grafos Busca em Largura Determinação do caminho mínimo entre a raiz e outro vértice 1 2 3 5 4 6 Pode ser feito a partir da fila da BFS desde que se guarde junto com cada vértice a posição na fila do vértice pai na busca e a distância mínima 200 200 111 411 511 200 111 411 511 322 200 111 411 511 322 200 111 411 511 322 642 200 111 411 511 322 642 200 111 411 511 322 642 Situação da fila 2 1 6 3 5 4 54 Grafos Busca em Largura 1 2 3 4 5 6 20 11 41 51 32 64 Determinação do caminho mínimo entre a raiz e outro vértice caminhopp a posição do vértice na Fila Exemplo p5 para achar caminho entre 2 e 3 j p distancia 1 enquanto j 0 guardar filjv em um vetor C j filjposicaoPai distancia escrever C invertido 55 Grafos Busca em Largura Outras possibilidades da BFS Pequenas modificações no algoritmo permitem descobrir propriedades do grafo 1 2 3 5 4 6 Visita a todas as arestas Obtenção dos graus dos vértices Determinação se o grafo é conexo Determinação dos componentes conexos Determinação de existência de ciclos Descoberta de elementos estruturais pontes blocos etc Descoberta se o grafo é bipartido ciclo árvore completo regular 56 Grafos Comparação Profundidade x Largura 57 Grafos Busca Irrestrita em Profundidade Idéia Visitar a cada passo algum vizinho do vértice mais recentemente visitado 1 2 5 4 dfsIv marcar v para vizinhos w de v se w não marcado dfsIw desmarcar v desmarcar vértices para i de 1 até n se i não marcado dfsIi 58 Grafos Busca Irrestrita em Profundidade Árvores de Busca Irrestrita Mostram a sequência das visitas Pode haver mais de uma árvore 1 2 3 4 Floresta de Busca Irrestrita 2 4 3 1 3 4 2 1 4 3 3 4 3 4 2 2 1 1 4 4 3 2 2 1 1 3 59 Grafos Busca Irrestrita em Profundidade Exercício recomendado Mostrar uma árvore de profundidade irrestrita iniciando no vértice de letra mais próxima de um dos nomes do grupo W X M K F B Exercícios httpsleetcodecomproblemsnumberofprovinces httpsleetcodecomproblemsisgraphbipartite httpsleetcodecomproblemsminimumheighttrees httpsleetcodecomproblemskeysandrooms httpsleetcodecomproblemsinvertbinarytree httpsleetcodecomproblemspopulatingnextrightpointersineachnode