- Construa um algoritmo para calcular o número de componentes conexas de um grafo
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.
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|).