Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS - Coggle Diagram
GRAFOS
Um grafo é chamado de não direcionado se todas as arestas nele forem não direcionadas.
Um grafo em que todas as arestas são direcionadas é chamado de grafo direcionado ou digrafo.
Um grafo em que cada par de seus vértices é conectado por uma aresta é chamado de completo.
Um grafo com relativamente poucas arestas faltando é chamado denso.
Um grafo com poucas arestas em relação ao número de seus vértices é chamado de esparso.
As principais representações de grafos são listas de adjacência e matriz de adjacência.
grafos ponderados são grafos nos quais números são atribuídos ás suas arestas, esses números são chamados de pesos ou custos.
ambas as principais representações de um grafo podem ser adaptadas para acomodar grafos ponderados.
as principais propriedades dos grafos são conectividade e aciclicidade.
DEPTH-FIRST SEARCH (DFS)
estrutura de dado: uma pilha
número de ordenações de vértices: duas ordenações
tipos de arestas (grafos não direcionados): árvore e aresta de retorno
aplicações: conectividade, aciclicidade, ponto de articulação
eficiência para matriz de adjacência: theta(|v|^2)
eficiência para lista de adjacência: theta(|v|+|e|)
BREADTH-FIRST SEARCH (BFS)
estrutura de dado: uma fila
número de ordenações de vértices: uma ordenação
tipos de arestas (grafos não direcionados): árvore e arestas cruzadas
aplicações: conectividade, aciclicidade, menor distância entre dois vértices
eficiência para matriz de adjacência: theta(|v|^2)
eficiência para lista de adjacência: theta(|v|+|e|)