Teoria dos Grafos: Aplicada em estruturas de dados e algoritmos Flashcards
O que é um grafo?
Um grafo é uma estrutura de dados composta por um conjunto de vértices (nós) e um conjunto de arestas (ligações) que conectam pares de vértices. Pode ser usado para modelar relações entre objetos.
Quais são os tipos principais de grafos?
Grafo simples: não possui laços nem arestas múltiplas.
Grafo direcionado (dígrafo): as arestas têm uma direção.
Grafo ponderado: as arestas possuem pesos.
Grafo completo: todos os pares de vértices estão conectados.
Grafo bipartido: vértices podem ser divididos em dois conjuntos disjuntos.
O que é um grafo ponderado?
Um grafo ponderado é um grafo em que cada aresta tem um valor (ou peso) associado a ela, representando custo, distância ou outra medida relevante.
Qual a diferença entre um grafo dirigido e um grafo não dirigido?
Grafo dirigido (ou dígrafo): as arestas têm direção, conectando um vértice de origem a um vértice de destino.
Grafo não dirigido: as arestas não têm direção, representando uma conexão bidirecional entre dois vértices.
O que é uma árvore em teoria dos grafos?
Uma árvore é um tipo especial de grafo que é conexo e acíclico, ou seja, todos os vértices estão conectados, mas não há ciclos. Árvores são usadas em várias estruturas de dados, como árvores binárias.
Qual é o propósito do algoritmo de Dijkstra?
O algoritmo de Dijkstra é utilizado para encontrar o caminho mais curto de um vértice de origem para todos os outros vértices em um grafo ponderado, onde todas as arestas têm pesos não negativos.
O que é um ciclo em um grafo?
Um ciclo em um grafo é um caminho que começa e termina no mesmo vértice, passando por uma sequência de vértices e arestas distintos.
O que é a busca em largura (BFS) em um grafo?
A busca em largura (BFS) é um algoritmo de exploração de grafos que visita todos os vértices de um grafo em camadas, começando de um vértice inicial e explorando todos os seus vizinhos antes de passar para os vértices de níveis seguintes.
O que é a busca em profundidade (DFS) em um grafo?
A busca em profundidade (DFS) é um algoritmo que explora um grafo começando por um vértice inicial, avançando o mais longe possível ao longo de cada caminho antes de retroceder.
Qual é a complexidade de tempo da busca em profundidade (DFS) e da busca em largura (BFS)?
Tanto a BFS quanto a DFS têm complexidade de tempo O(V + E), onde V é o número de vértices e E é o número de arestas no grafo.
