Grafos Flashcards
(10 cards)
O que é um Grafo (Graph) em Estruturas de Dados?
Um Grafo é uma estrutura de dados composta por um conjunto de nós (ou vértices) e um conjunto de arestas que conectam esses nós. Ele pode ser utilizado para representar relações entre entidades, como redes de computadores, rotas de transporte e redes sociais.
Quais são os componentes principais de um Grafo?
Vértices (Nós) e Arestas (conexões entre vértices). Em grafos dirigidos, as arestas possuem direção (origem e destino), enquanto em grafos não dirigidos as arestas não possuem direção.
Quais são os tipos de Grafos mais comuns?
Grafo Dirigido (Digrafo), Grafo Não Dirigido, Grafo Ponderado, Grafo Não Ponderado, Grafo Cíclico, Grafo Acíclico.
Como é a representação de um Grafo em memória?
Matriz de Adjacência e Lista de Adjacência.
O que é o Algoritmo de Dijkstra?
O Algoritmo de Dijkstra é usado para encontrar o caminho mais curto entre dois vértices em um grafo ponderado. Ele atribui uma distância mínima a cada vértice e relaxa as arestas para encontrar o caminho mais curto.
O que é o Algoritmo de Busca em Largura (BFS)?
O Algoritmo de Busca em Largura (BFS) percorre o grafo explorando todos os vizinhos de um vértice antes de mover para os vizinhos dos vizinhos. Ele é útil para encontrar o caminho mais curto em grafos não ponderados.
O que é o Algoritmo de Busca em Profundidade (DFS)?
O Algoritmo de Busca em Profundidade (DFS) percorre o grafo indo o mais profundamente possível antes de retroceder. Ele é útil para encontrar componentes conectados e realizar ordenação topológica em grafos dirigidos.
O que é o Grafo Completo?
Um Grafo Completo é um grafo onde há uma aresta entre todos os pares de vértices.
O que é um Ciclo em um Grafo?
Um Ciclo em um grafo é um caminho fechado, começando e terminando no mesmo vértice, e contém pelo menos uma aresta.
Qual a complexidade das operações em Grafos?
Busca em Largura (BFS): O(V + E), Busca em Profundidade (DFS): O(V + E), Dijkstra: O(V^2) com matriz de adjacência, O(E + V log V) com fila de prioridade.
