Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos, A pesquisa em profundidade inicia a travessia de um gráfico em um…

- - - - As listas de adjacência de um grafo ou dígrafo são uma coleção de listas vinculadas, um para cada vértice, que contém todos os vértices adjacentes ao vértice da lista (ou seja, todos os vértices conectados a ele por uma aresta). Normalmente, essas listas começam com um cabeçalho identificando um vértice para o qual a lista é compilada
      - A adjacência matriz de um gráfico com n vértices é uma matriz booleana n × n com uma linha e uma coluna para cada um dos vértices do gráfico, em que o elemento na i-ésima linha e a j-ésima coluna é igual a 1 se houver uma aresta do i-ésimo vértice para o j-ésimo vértice, e igual a 0 se não houver tal aresta.
  - - - Um caminho do vértice u ao vértice v de um gráfico G pode ser definido como um sequência de vértices adjacentes (conectados por uma aresta) que começa com u e termina com v. Se todos os vértices de um caminho são distintos, o caminho é considerado simples. O comprimento de um caminho é o número total de vértices na sequência de vértices que define o caminho menos 1, que é igual ao número de arestas no caminho
        
        Diz-se que um gráfico está conectado se para cada par de seus vértices u e v lá é um caminho de u a v. Se fizermos um modelo de um grafo conectado conectando algumas bolas representando os vértices do gráfico com strings representando as arestas, será uma peça única
        
        Um caminho direcionado é uma sequência de vértices em que cada par consecutivo do os vértices são conectados por uma aresta direcionada do vértice listado primeiro para o vértice listado a seguir.
- - - - Se a pesquisa em profundidade é uma travessia para os bravos, a busca em largura é uma travessia para os cautelosos. Prossegue de maneira concêntrica, visitando primeiro todos os vértices adjacentes a um vértice, então todos os vértices não visitados duas arestas além dele, e assim por diante, até que todos os vértices no mesmo componente conectado que o vértice inicial são visitados. Se ainda houver vértices não visitados, o algoritmo deve ser reiniciado em um vértice arbitrário de outro componente conectado do gráfico.
        
        De maneira semelhante a uma passagem DFS, é útil acompanhar uma passagem BFS construindo a chamada floresta de pesquisa em largura primeiro. O vértice inicial da travessia serve como a raiz da primeira árvore em al floresta. Sempre que um novo vértice não visitado é alcançado pela primeira vez, o vértice é anexado como filho ao vértice que está sendo alcançada por uma borda chamada borda da árvore. Se uma aresta levando a um vértice visitado diferente de seu predecessor imediato for encontrada, a aresta é identificada como uma aresta cruzada.
        
        A pesquisa em amplitude tem a mesma eficiência que a pesquisa em profundidade. Quanto à estrutura de uma floresta BFS de um grafo não direcionado, ele também pode ter dois tipos de arestas: arestas de árvore e arestas cruzadas. As bordas das árvores são os aqueles usados para alcançar vértices não visitados anteriormente. Arestas cruzadas conectam vértices a aqueles visitados antes, mas, ao contrário das arestas posteriores em uma árvore DFS, eles conectam vértices no mesmo nível ou em níveis adjacentes de uma árvore BFS