ConnectedComponents.c

/*
 *
 *	Grafos - Algoritmo para calcular o número de componentes conexos em um
 *determinado Grafo
 *
 *	GRAFO
 *   (0)               (1)-------------(4)---------------(5)
 *    |                 |               |                 |
 *    |                 |               |                 |
 *    |                 |               |                 |
 *   (2)               (3)---------------                 |
 *                      |                                 |
 *                      -----------------------------------
 *
 *
 *    Matriz de Adjacência
 *       0  1  2  3  4  5
 *    0  0  -  1  -  -  -
 *    1  -  0  -  1  1  -
 *    2  1  -  0  -  -  -
 *    3  -  1  -  0  1  1
 *    4  -  1  -  1  0  1
 *	 5  -  -  -  1  1  0
 *
 *
 *	6 Vértices
 *	8 Arestas
 */

#include <stdio.h>

#define VERTICES 6
#define INF -1

bool visitados[VERTICES];
int componentes = 0;

int matriz[VERTICES][VERTICES] = {
    {0, INF, 1, INF, INF, INF}, {INF, 0, INF, 1, 1, INF},
    {1, INF, 0, INF, INF, INF}, {INF, 1, INF, 0, 1, 1},
    {INF, 1, INF, 1, 0, 1},     {INF, INF, INF, 1, 1, 0}};

// Método recursivo que encontra os componentes conexos a partir de uma matriz
// de adjacências
void calculaComponentesConexos(int atual) {
  for (int i = 0; i < VERTICES; i++) {
    if (visitados[i] == false && matriz[atual][i] == 1) {
      visitados[i] = true;
      componentes++;
      printf("(%d)-", i);
      calculaComponentesConexos(i);
    }
  }
}

int main() {
  for (int i = 0; i < VERTICES; i++)
    visitados[i] = false;

  for (int i = 0; i < VERTICES; i++)
    if (visitados[i] == false) {
      componentes = 0;
      calculaComponentesConexos(i);
      printf(
          "\nNumero de componentes conexos iniciando pelo vertice %d: %d\n\n",
          i, componentes);
    }

  return 0;
}