Grafo que Representa uma Rede Social

[bernardino]

Considere a seguinte situação:

Temos um grafo que representa uma rede social, onde os vértices são pessoas e as arestas indicam amizades. Queremos encontrar o caminho mais curto de amizade entre duas pessoas específicas.

Levando em consideração a matriz de adjacência crie o desenho do grafo:

Código: Selecionar todos

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 6

// Função para implementar BFS
int bfs(int grafo[MAX_VERTICES][MAX_VERTICES], int inicio, int destino, int caminho[]) {
    int fila[MAX_VERTICES];
    int visitado[MAX_VERTICES] = {0}; // Array para marcar os vértices visitados
    int distancia[MAX_VERTICES]; // Array para armazenar as distâncias dos vértices
    int frente = 0, tras = 0;

    for (int i = 0; i < MAX_VERTICES; i++) {
        distancia[i] = -1; // Inicializando a distância com -1
    }

    // Coloca o vértice de início na fila
    fila[tras++] = inicio;
    distancia[inicio] = 0; // A distância para o vértice de início é 0
    visitado[inicio] = 1;

    while (frente < tras) {
        int atual = fila[frente++];
        
        // Se encontrou o destino, retorna a distância e o caminho
        if (atual == destino) {
            int aux = destino;
            int i = 0;
            while (aux != inicio) {
                caminho[i++] = aux;
                aux = caminho[aux];
            }
            caminho[i] = inicio;
            return distancia[destino];
        }

        // Explora os vizinhos do vértice atual
        for (int i = 0; i < MAX_VERTICES; i++) {
            if (grafo[atual][i] == 1 && !visitado[i]) {
                fila[tras++] = i;
                visitado[i] = 1;
                distancia[i] = distancia[atual] + 1;
                caminho[i] = atual; // Armazena o caminho
            }
        }
    }
    return -1; // Se não encontrar caminho
}

int main() {
    // Grafo de amizade representado como uma matriz de adjacência
    int grafo[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 1, 0, 0},
        {1, 0, 1, 0, 1, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 0, 0, 0, 1, 1},
        {0, 1, 0, 1, 0, 1},
        {0, 0, 0, 1, 1, 0}
    };
    
    int inicio = 0;  // Por exemplo, de 0 para 5
    int destino = 5;
    int caminho[MAX_VERTICES];
    
    int distancia = bfs(grafo, inicio, destino, caminho);

    if (distancia != -1) {
        printf("O caminho mais curto entre %d e %d tem distância %d.\n", inicio, destino, distancia);
        printf("Caminho: ");
        for (int i = distancia - 1; i >= 0; i--) {
            printf("%d ", caminho[i]);
        }
        printf("\n");
    } else {
        printf("Não há caminho entre %d e %d.\n", inicio, destino);
    }
    
    return 0;
}

Resultado da Execução

Código: Selecionar todos

O caminho mais curto entre 0 e 5 tem distância 2.
Caminho: 3 5 

Simulacao.png (20.66 KiB) Exibido 2064 vezes