1. Construa um algoritmo para calcular o número de componentes conexas de um grafo G representado por lista de adjacência. Qual a complexidade no pior caso para o seu algoritmo.

Passo 1

O enunciado pede para construirmos um algoritmo que, dado um grafo G representado por lista de adjacências, calcule quantas componentes conexas ele possui. Isso envolve conceitos de grafos e operações de busca (DFS ou BFS). Vamos precisar de um vetor de marcação dos vértices visitados e de uma rotina de exploração (por exemplo, busca em profundidade).

Passo 2

Inicializamos um vetor visited[1…n] com false para todos os n vértices de G, e uma variável count = 0 para contar componentes. Em seguida, fazemos um laço for sobre cada vértice u de 1 até n: se visited[u] for false, incrementamos count e chamamos a rotina dfs(u).

Passo 3

A rotina dfs(u) marca visited[u] = true e então percorre cada vizinho v em G.adj[u]. Se visited[v] for false, chamamos recursivamente dfs(v). Dessa forma, exploramos toda a componente conectada a u, marcando todos os vértices pertencentes.

Passo 4

Ao final do laço principal, a variável count conterá o número total de componentes conexas de G.

Passo 5

Para analisar a complexidade, note que cada vértice é marcado visitado apenas uma vez, e para cada vértice exploramos todas as suas arestas adjacentes exatamente uma vez durante as chamadas de dfs. A soma do trabalho feito é proporcional a visitar todos os vértices e todas as arestas.
Portanto, no pior caso, a complexidade de tempo é proporcional a ,|V| + |E|, onde ,|V|\ é o número de vértices de G e ,|E|\ é o número de arestas de G.

Resposta

A complexidade no pior caso é O(|V| + |E|).

Exercícios relacionados