Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS - Coggle Diagram
GRAFOS
Dois algoritmos muito importantes
que processam sistematicamente todos os vértices e arestas de um grafo são:
Depth-first search (DFS)
Inicia a travessia de um grafo em um vértice arbitrário, marcando-o como visitado. Em cada iteração, o algoritmo prossegue para um vértice não visitado que
é adjacente ao que está atualmente.
O processo continua até um beco sem saída - um vértice sem vértices não visitados adjacentes -
é encontrado.
Em um beco sem saída, o algoritmo faz backup de uma aresta para o vértice de onde ele veio e tenta continuar visitando vértices não visitados de lá.
O algoritmo eventualmente para depois de fazer backup para o vértice inicial, com o último sendo um beco sem saída.
Até então, todos os vértices no mesmo componente conectado ao vértice inicial foram visitados.
Se os vértices não visitados ainda permanecerem, o método depth-first deve ser reiniciado em qualquer um deles.
É um algoritmo bastante eficiente, pois leva apenas o tempo proporcional ao tamanho da estrutura de dados usada para representar o gráfico em questão.
1 more item...
Breadth-first search (BFS)
procede de maneira concêntrica, visitando primeiro todos os vértices adjacentes a um vértice, então todos os vértices não visitados são separados por duas arestas, e assim por diante, até que todos os vértices no mesmo componente conectado ao 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 grafo.
É conveniente usar uma fila para percorrer a operação de busca 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 que são adjacentes ao vértice frontal, marca-os como visitados e adiciona-os à fila; depois disso, o vértice frontal é
removido da fila.
Assim, para a representação matricial de adjacências, o tempo de percurso está em theta(|V|^2), e para a lista de adjacências, está em theta(|V|+|E|) onde |V | e |E| são o número de vértices e arestas do grafo, respectivamente.
Há apenas duas diferenças notáveis entre grafos não direcionados e direcionados em representá-los:
A matriz de adjacência de um grafo direcionado não precisa ser simétrica;
Uma borda em um grafo direcionado tem apenas um (não dois) nós correspondentes no dígrafo listas de adjacências.
Um grafo é informalmente considerado como
uma coleção de pontos no plano chamados “vértices” ou “nós”, alguns deles
conectados por segmentos de linha chamados “bordas” ou “arcos”.
Formalmente, um grafo é definido por um par de dois conjuntos: um conjunto finito não vazio V de itens chamados vértices e um conjunto E de pares desses itens chamados arestas.
Se esses pares de vértices são
não ordenados, ou seja, um par de vértices (u, v) é o mesmo que o par (v, u), dizemos que
os vértices u e v são adjacentes um ao outro e que estão conectados pela aresta 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 essa aresta; também dizemos que a aresta (u, v) é incidente aos seus extremos u e v.
Um grafo G é dito não direcionado se cada aresta
é não direcionada.
Se um par de vértices (u, v) não é o mesmo que o par (v, u), dizemos que a aresta (u, v) é direcionada do vértice u, chamado de cauda da aresta, para o vértice v,
chamado de cabeça da borda.
Dizemos também que a aresta (u, v) sai de u e entra em v.
O grafo cuja aresta é direcionada é chamado de direcionado.
Os gráficos direcionados também são
chamados dígrafos.
Um grafo com relativamente poucas arestas faltando é chamado de denso; um grafo com poucas arestas em relação ao número de seus vértices é chamado esparso.
Se estivermos trabalhando com um grafo denso ou esparso pode influenciar como escolhemos representar o grafo e, consequentemente, o tempo de execução de um algoritmo que está sendo projetado ou usado muda.
Se um gráfico for esparso, a representação da lista de adjacências pode usar menos espaço do que a matriz de adjacência correspondente, apesar do armazenamento extra consumido por ponteiros das listas encadeadas;
Dentro geral, qual das duas representações é mais conveniente depende do natureza do problema, no algoritmo usado para resolvê-lo e, possivelmente, na tipo de gráfico de entrada (esparso ou denso).
Os grafos para algoritmos de computador são geralmente representados de duas maneiras: a matriz de adjacências e as listas de adjacências.
A matriz adjacências 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, em que o elemento na linha i e a j-ésima coluna é igual a 1 se houver uma aresta do i-ésimo vértice ao j-ésimo vértice, e igual a 0 se não houver tal aresta.
Um gráfico ponderado (ou dígrafo ponderado) é um gráfico (ou di gráfico) com números atribuídos às suas arestas.
Esses números são chamados de pesos ou
custos.
Entre as muitas propriedades dos grafos, duas são importantes para um grande número de aplicações: conectividade e aciclicidade. Ambos são baseados na
noção de caminho.
Um caminho do vértice u ao vértice v de um grafo 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 é dito 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 é o mesmo que o número de arestas no caminho.
Temos a seguinte desigualdade para o número de arestas |E| possível em um grafo não direcionado com |V | vértices e sem laços: 0 ≤ |E|≤|V |(|V | − 1)/2.
Um grafo com cada par de seus vértices conectados por uma aresta é chamado de completo. Uma notação padrão para o gráfico completo com |V | vértices é K|V|.
Um caminho direcionado é uma sequência de vértices em que cada par consecutivo de vértices é conectado por uma aresta direcionada do primeiro vértice listado para o vértice listado a seguir.
Um grafo é dito conexo se para cada par de seus vértices u e v houver é um caminho de u para v.
Um componente conectado é um componente máximo (não expansível incluindo outro vértice e uma aresta) subgrafo conectado de um dado grafo.
Um ciclo é um caminho de comprimento positivo que começa e termina em mesmo vértice e não percorre a mesma aresta mais de uma vez. Um grafo sem ciclos é dito ser acíclico.