Please enable JavaScript.
Coggle requires JavaScript to display documents.
., Depth-first search(DFS), Graph(G = (v, e)), Breadth-first search (BFS),…
.
Depth-first search(DFS)
Inicia a travessia em um vértice qualquer, marcando-o como visitado
Em cada iteração, o algoritmo prossegue para um vértice não visitado que é adjacente àquele em que se encontra atualmente.
Se houver vários desses vértices, um empate pode ser resolvido arbitrariamente. ou pela estrutura de dados que representa o grafo
Esse processo continua até que um beco sem saída - um vértice sem vértices adjacentes não visitados - seja encontrado.
Em um beco sem saída, o algoritmo faz backup de uma aresta até o vértice de onde veio e tenta continuar visitando vértices não visitados a partir daí.
O algoritmo eventualmente para após voltar ao vértice inicial, sendo este último um beco sem saída.
Se ainda restarem vértices não visitados, a primeira busca em profundidade deve ser reiniciada em qualquer um deles.
É conveniente usar uma pilha
(stack)
para rastrear a operação da pesquisa em profundidade.
Colocamos um vértice na pilha quando o vértice é alcançado pela primeira vez (ou seja, a visita do vértice começa) e retiramos um vértice da pilha quando ele se torna um beco sem saída (ou seja, a visita do vértice termina).
Graph(G = (v, e))
G = {V, E} é definido por um par de dois conjuntos:
V -> um conjunto finito e não vazio de itens chamados vértices
E -> conjunto de pares desses itens chamados arestas.
Se os pares de vértices não são ordenados, ou seja (u, v) == (v, u), os vértices são adjacentes entre si e que estão conectados pela borda não direcionada (u, v).
Chamamos os vértices u e v de extremidades da aresta (u, v) e dizemos que u e v são incidentes a esta aresta e aos seus pontos finais u e v.
Se um par de vértices (u, v) não é igual ao par (v, u), dizemos que a aresta (u, v) é direcionada do vértice u, chamado de cauda da aresta, até o vértice v, chamada de cabeça da borda.
a aresta (u, v) sai de u e entra em v.
Um grafo G é chamado não direcionado se todas as arestas nele são não direcionadas.
0 <= |E| <= (|V| * (|V| - 1))/ 2
Um grafo cujas arestas são direcionadas é chamado de direcionado. Gráficos direcionados também são chamados de dígrafos.
Um grafo com cada par de seus vértices conectados por uma aresta é chamado completo. Uma notação padrão para o gráfico completo com |V | vértices é K|V |
Um gráfico com relativamente poucas arestas possíveis faltando é chamado denso
um gráfico com poucas arestas em relação ao número de seus vértices é chamado de esparso.
O fato de estarmos lidando com um grafo denso ou esparso pode influenciar a forma como escolhemos representar o grafo e, consequentemente, o tempo de execução de um algoritmo que está sendo projetado ou utilizado.
Representação de Grafos
Matriz de adjacência
A matriz de adjacência de um grafo com n vértices é uma matriz booleana n × n com uma linha e uma coluna para cada um dos vértices do grafo
elemento da i-ésima linha e da j-ésima coluna é igual a 1 se houver um aresta do i-ésimo vértice ao j-ésimo vértice, e igual a 0 se tal aresta não existir.
Grafo denso
Lista de adjacência
são uma coleção de listas vinculadas, uma 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 ela por uma aresta).
Grafo esparso
Grados ponderados
Tem pesos atribuídos às suas arestas
O interesse em tais gráficos é motivado por inúmeras aplicações do mundo real, como encontrar o caminho mais curto entre dois pontos em uma rede de transporte ou comunicação ou o problema do caixeiro viajante mencionado anteriormente.
Para representar um grafo ponderado, seu elemento A[i, j] simplesmente conterá o peso da aresta do i-ésimo ao j-ésimo vértice se existir tal aresta e um símbolo especial, por exemplo, ∞ , se não houver tal borda.
Matriz de peso ou matriz de custo
As listas de adjacência para um grafo ponderado devem incluir em seus nós não apenas o nome de um vértice adjacente, mas também o peso da aresta correspondente.
Conectividade e aciclicidade
Um caminho do vértice u ao vértice v de um grafo G pode ser definido como uma sequência de vértices adjacentes (conectados por uma aresta) que começa com u e termina com v.
Um caminho direcionado é uma sequência de vértices em que cada par consecutivo de vértices é conectado por uma aresta direcionada do vértice listado primeiro ao vértice listado a seguir.
Se todos os vértices de um caminho são distintos, diz-se que o caminho é seja simples.
Propriedades baseadas na noção de caminho
Um ciclo é um caminho de comprimento positivo que começa e termina no mesmo vértice e não atravessa a mesma aresta mais de uma vez.
Um gráfico sem ciclos é dito acíclico.
uma coleção de pontos no plano chamados “vértices” ou “nós”, alguns deles conectados por segmentos de linha chamados “arestas” ou “arcos”.
Breadth-first search (BFS)
Visita todos os vértices adjacentes a um vértice inicial
depois todos os vértices não visitados a duas arestas de distância dele, e assim por diante, até que todos os vértices no mesmo componente conectado do vértice inicial sejam visitados.
Se ainda restarem vértices não visitados, o algoritmo deverá ser reiniciado em um vértice arbitrário de outro componente conectado do grafo.
É conveniente usar uma fila
(Queue)
para rastrear a operação da pesquisa em largura.
A fila é inicializada com o vértice inicial da travessia, que é marcado como visitado.
Em cada iteração, o algoritmo identifica todos os vértices não visitados adjacentes ao vértice frontal, marca-os como visitados e adiciona-os à fila;
depois disso, o vértice frontal é removido da fila.
depth-first search (DFS) and breadth-first search (BFS)
algoritmos muito importantes que processam sistematicamente todos os vértices e arestas de um gráfico
Esses algoritmos provaram ser muito úteis para muitas aplicações envolvendo gráficos em inteligência artificial e pesquisa operacional. Além disso, são indispensáveis para a investigação eficiente de propriedades fundamentais de grafos, como conectividade e presença de ciclo.
OBS
ADT
Número de ordenações de vértices
Aplicações
Ef. Adj. Matrix
Θ(|V²|)
Θ(|V²|)
Ef. Adj. Lista
Θ(|V |+|E|)
Θ(|V |+|E|)
conectividade, aciclicidade, pontos de articulação
conectividade, aciclicidade, caminhos de borda mínima
2
1
Stack
Queue
DFS
BFS