Analise de Complexidade - Analise de complexidade de algoritmos de grafos lista

Prévia do material em texto

Disciplina: Algoritmos e estruturas de dados 
Curso: Ciência da computação 
 
 
 
Análise de Complexidade 
Análise de complexidade de algoritmos de grafos 
 
 
Exercícios Resolvidos com Explicações 
 
 
 
Questão 1 
 
Qual é a complexidade de tempo do algoritmo de Dijkstra para encontrar o caminho mais 
curto em um grafo? 
 
A) O(V + E) 
B) O(V^2 + E) 
C) O(V^2 + E^2) 
D) O(V^3 + E^3) 
E) O(2^V + E) 
 
Resposta: B) O(V^2 + E) 
 
Explicação: A complexidade de tempo do algoritmo de Dijkstra é O(V^2 + E), onde V é o 
número de vértices e E é o número de arestas do grafo. 
 
Questão 2 
 
Qual é o algoritmo de grafos que é mais adequado para encontrar o caminho mais curto 
em um grafo com pesos negativos? 
 
A) Algoritmo de Dijkstra 
B) Algoritmo de Bellman-Ford 
C) Algoritmo de Floyd-Warshall 
D) Algoritmo de Kruskal 
E) Algoritmo de Prim 
 
Resposta: B) Algoritmo de Bellman-Ford 
 
Explicação: O algoritmo de Bellman-Ford é mais adequado para encontrar o caminho 
mais curto em um grafo com pesos negativos, pois pode lidar com pesos negativos e 
detectar ciclos negativos. 
 
 
Questão 3 
 
Qual é a complexidade de espaço do algoritmo de Kruskal para encontrar a árvore 
geradora mínima de um grafo? 
 
A) O(V) 
B) O(E) 
C) O(V + E) 
D) O(V^2 + E^2) 
E) O(2^V + E) 
 
Resposta: C) O(V + E) 
 
Explicação: A complexidade de espaço do algoritmo de Kruskal é O(V + E), onde V é o 
número de vértices e E é o número de arestas do grafo. 
 
Questão 4 
 
Qual é o algoritmo de grafos que é mais adequado para encontrar o fluxo máximo em um 
grafo de fluxo? 
 
A) Algoritmo de Ford-Fulkerson 
B) Algoritmo de Edmonds-Karp 
C) Algoritmo de Dinic 
D) Algoritmo de Kruskal 
E) Algoritmo de Prim 
 
Resposta: A) Algoritmo de Ford-Fulkerson 
 
Explicação: O algoritmo de Ford-Fulkerson é mais adequado para encontrar o fluxo 
máximo em um grafo de fluxo, pois pode lidar com capacidades e encontrar o fluxo 
máximo. 
 
Questão 5 
 
Qual é a complexidade de tempo do algoritmo de Floyd-Warshall para encontrar a matriz 
de distâncias de um grafo? 
 
A) O(V^2 + E) 
B) O(V^3 + E) 
C) O(V^3 + E^2) 
D) O(V^4 + E^3) 
E) O(2^V + E) 
 
Resposta: B) O(V^3 + E) 
 
Explicação: A complexidade de tempo do algoritmo de Floyd-Warshall é O(V^3 + E), onde 
V é o número de vértices e E é o número de arestas do grafo. 
 
Questão 6 
 
Qual é o algoritmo de grafos que é mais adequado para encontrar o caminho mais curto 
em um grafo com vértices e arestas ponderadas? 
 
A) Algoritmo de Dijkstra 
B) Algoritmo de Bellman-Ford 
C) Algoritmo de Floyd-Warshall 
D) Algoritmo de Kruskal 
E) Algoritmo de Prim 
 
Resposta: A) Algoritmo de Dijkstra 
 
Explicação: O algoritmo de Dijkstra é mais adequado para encontrar o caminho mais curto 
em um grafo com vértices e arestas ponderadas, pois pode lidar com pesos positivos e 
encontrar o caminho mais curto. 
 
Questão 7 
 
Qual é a complexidade de espaço do algoritmo de Edmonds-Karp para encontrar o fluxo 
máximo em um grafo de fluxo? 
 
A) O(V) 
B) O(E) 
C) O(V + E) 
D) O(V^2 + E^2) 
E) O(2^V + E) 
 
Resposta: C) O(V + E) 
 
Explicação: A complexidade de espaço do algoritmo de Edmonds-Karp é O(V + E), onde 
V é o número de vértices e E é o número de arestas do grafo. 
 
Questão 8 
 
Qual é o algoritmo de grafos que é mais adequado para encontrar a árvore geradora 
mínima de um grafo ponderado? 
 
A) Algoritmo de Kruskal 
B) Algoritmo de Prim 
C) Algoritmo de Dijkstra 
D) Algoritmo de Bellman-Ford 
E) Algoritmo de Floyd-Warshall 
 
Resposta: A) Algoritmo de Kruskal 
 
Explicação: O algoritmo de Kruskal é mais adequado para encontrar a árvore geradora 
mínima de um grafo ponderado, pois pode lidar com pesos e encontrar a árvore geradora 
mínima. 
 
 
Questão 9 
 
Qual é a complexidade de tempo do algoritmo de Floyd-Warshall para encontrar a matriz 
de distâncias de um grafo ponderado? 
 
A) O(V^2 + E) 
B) O(V^3 + E) 
C) O(V^3 + E^2) 
D) O(V^4 + E^3) 
E) O(2^V + E) 
 
Resposta: B) O(V^3 + E) 
 
Explicação: A complexidade de tempo do algoritmo de Floyd-Warshall é O(V^3 + E), onde 
V é o número de vértices e E é o número de arestas do grafo. 
 
Questão 10 
 
Qual é o algoritmo de grafos que é mais adequado para encontrar o ciclo mais curto em 
um grafo ponderado? 
 
A) Algoritmo de Dijkstra 
B) Algoritmo de Bellman-Ford 
C) Algoritmo de Floyd-Warshall 
D) Algoritmo de Kruskal 
E) Algoritmo de Prim 
 
Resposta: B) Algoritmo de Bellman-Ford 
 
Explicação: O algoritmo de Bellman-Ford é mais adequado para encontrar o ciclo mais 
curto em um grafo ponderado, pois pode lidar com pesos negativos e encontrar o ciclo 
mais curto.