Trabalho final de grafos

grafos-final.cpp

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>

#define MAX 100
#define INF 99999

int grafo[MAX][MAX]; // representação matricial dos grafos
// Funcao para ler a matriz
void leGrafo(int g[][MAX], int ordem, int tamanho)
{
    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < tamanho; j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
}
// Funções desenvolvidas no trabalho
// Verifica se o grafo é regular com Matriz de Adjacência
bool regular(int ordem)
{
    int grau = 0, grau_aux;
    for (int i = 0; i < ordem; i++)
        grau += (grafo[0][i] != 0 ? 1 : 0);
    for (int i = 1; i < ordem; i++)
    {
        grau_aux = 0;
        for (int j = 0; j < ordem; j++)
        {
            grau_aux += (grafo[i][j] != 0 ? 1 : 0);
        }
        if (grau != grau_aux)
            return false;
    }
    return true;
}

// busca em profundidade
void BuscaProfundidadeAdjac(int ordem, int origem, bool *visitado)
{
    visitado[origem] = true;
    for (int j = 0; j < ordem; j++)
        if (grafo[origem][j] && !visitado[j])
            BuscaProfundidadeAdjac(ordem, j, visitado);
}

//djiskra com custos por referencia
void dikstra_custo(int ordem, int inicial, int custos[])
{
    int custo[ordem];
    int menor_caminho = -1;
    bool visitado[ordem];
    for (int i = 0; i < ordem; i++)
    {
        visitado[i] = false;
    }

    for (int i = 0; i < ordem; i++)
    {
        custo[i] = INF;
    }
    custo[inicial] = 0;

    while (true)
    {
        menor_caminho = -1;
        for (int i = 0; i < ordem; i++)
        {
            if (!visitado[i] && (menor_caminho < 0 || custo[i] < custo[menor_caminho]))
            {
                menor_caminho = i;
            }
        }
        if (menor_caminho < 0)
        {
            break;
        }

        visitado[menor_caminho] = true;
        for (int i = 0; i < ordem; i++)
        {
            if (grafo[menor_caminho][i] && custo[i] > custo[menor_caminho] + grafo[menor_caminho][i])
            {
                custo[i] = custo[menor_caminho] + grafo[menor_caminho][i];
            }
        }
    }
    for (int i = 0; i < ordem; i++)
    {
        custos[i] = custo[i];
    }
}

//****CASOS DA IMPLEMENTA��O*********

// Caso 2)
bool is_kRegular(int tamanho, int ordem)
{
    unsigned int adjacenciasDaLinha = 0;

    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            if (grafo[i][j])
                adjacenciasDaLinha++;

            if (j == ordem - 1)
            {
                if (adjacenciasDaLinha != tamanho)
                    return false;
                adjacenciasDaLinha = 0;
            }
        }
    }

    return true;
}

//caso 3: grafo euleriano
int euleriano(int ordem)
{
    int grau[ordem];
    int i, j;
    for (i = 0; i < ordem; i++)
    {
        for (j = 0; j < ordem; j++)
        {
            grau[i] += grafo[i][j];
        }
    }
    for (i = 0; i < ordem; i++)
    {
        if (grau[i] % 2 != 0)
        {
            return 0;
        }
    }
    return 1;
}

// Caso 4)

void eulerianoCircuit(int ordem)
{

    if (euleriano(ordem))
    {
        for (int i = 0; i < ordem; i++)
        {
            for (int j = 0; j < ordem; j++)
            {
                if (grafo[i][j] == 1 && grafo[j][i] == 1)
                {
                    if (i == 0)
                    {
                        printf("%d - %d", i, j);
                    }
                    else
                    {
                        printf(" - %d", j);
                    }
                    grafo[i][j] = 0; // para evitar o loop
                    grafo[j][i] = 0;
                    break;
                }
            }
        }
        printf("\n");
    }
}

//5 - componentes conexas
void dfs(int g[][MAX], int ordem, bool visitado[], int inicio)
{
    visitado[inicio] = true;
    for (int i = 0; i < ordem; i++)
    {
        if (!visitado[i] && g[inicio][i] > 0)
            dfs(g, ordem, visitado, i);
    }
}

int conexos(int u)
{
    bool visitado[u];
    int inicio = 0;
    int cont = 0;

    for (int i = 0; i < u; i++)
    {
        visitado[i] = false;
    }
    for (int i = 0; i < u; i++)
    {
        if (!visitado[i])
        {
            dfs(grafo, u, visitado, i);
            cont++;
        }
    }
    return cont;
}

// Caso 6)
bool isCompleto(int ordem)
{
    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            if (!grafo[i][j] && i != j)
                return false;
        }
    }

    return true;
}

//caso 7: excentricidade de um vertice de grafo simples
int excentricidade(int ordem, int inicial)
{

    int custos[ordem];
    int exc = -1;
    dikstra_custo(ordem, inicial, custos);
    //os custos s�o o menor caminho entre inicial e cada vertice, logo o maior dos custos e a excentricidade
    for (int i = 0; i < ordem; i++)
    {
        //printf("%i ",custos[i]);
        if (custos[i] > exc)
        {
            exc = custos[i];
        }
    }
    return exc;
}

// Caso 8:


int raio(int ordem)
{
    int r, aux = 100;
    for (int i = 0; i < ordem; i++)
    {
        r = excentricidade(ordem, i);
        if (aux > r)
            aux = r;
    }
    return aux;
}

// Caso 9:

int diametro(int ordem)
{
    int r, aux = 0;
    for (int i = 0; i < ordem; i++)
    {
        r = excentricidade(ordem, i);
        if (aux < r)
            aux = r;
    }
    return aux;
}

//caso 10: centro
void centro(int ordem, int conjunto_centro[])
{

    int excentricidades_valores[ordem];
    int i, controle;
    int menor_exc = INF;

    for (i = 0; i < ordem; i++)
    {
        excentricidades_valores[i] = excentricidade(ordem, i);
        if (excentricidades_valores[i] < menor_exc)
        {
            menor_exc = excentricidades_valores[i];
        }
    }
    for (i = 0; i < ordem; i++)
    {
        if (excentricidades_valores[i] == menor_exc)
        {
            conjunto_centro[i] = 1;
        }
    }
}

// Caso 11:
void calcularComplemento(int ordem) {
    int complemento[MAX][MAX];
    
    for(int i=0; i<ordem; i++) {
        for(int j=0; j<ordem; j++) {
            if(!grafo[i][j] && i != j) 
                complemento[i][j] = 1;
            else 
                complemento[i][j] = 0;
        }
    }
    printf("\n");
    for(int i=0; i<ordem; i++) {
        for(int j=0; j<ordem; j++) {
            printf("%d ", complemento[i][j]);
        }
        printf("\n");
    }
}

// Caso 12: Grafo Bipartido

void isBipartido(int ordem)
{
    int grupo1[ordem], grupo2[ordem];
    int atual;

    grupo1[0] = 0;

    for (int i = 0; i < ordem; i++)
    {
        grupo1[i] = !grafo[0][i];

        grupo2[i] = grafo[0][i];
    }

    for (int i = 0; i < ordem; i++)
    {
        if (!grupo1[i])
            continue;
        atual = i;
        for (int j = 0; j < ordem; j++)
        {
            if (grafo[atual][j] && grupo1[j])
            {
                printf("o grafo nao e bipartido\n");
                return;
            }
        }
    }

    for (int i = 0; i < ordem; i++)
    {
        if (!grupo2[i])
            continue;
        atual = i;
        for (int j = 0; j < ordem; j++)
        {
            if (grafo[atual][j] && grupo2[j])
            {
                printf("o grafo nao e bipartido\n");
                return;
            }
        }
    }

    for (int i = 0; i < ordem; i++)
    {
        if (!grupo1[i])
            continue;
        atual = i;

        for (int j = 0; j < ordem; j++)
        {
            if (grafo[atual][j] && grupo2[j])
                continue;
            if (j == ordem - 1)
            {
                printf("o grafo nao e bipartido\n");
                return;
            }
        }
    }

    for (int i = 0; i < ordem; i++)
    {
        if (grupo1[i])
            printf("%d ", i);
    }
    printf("\n");

    for (int i = 0; i < ordem; i++)
    {
        if (grupo2[i])
            printf("%d ", i);
    }
    printf("\n");
}

//Case 13)
void alcancabilidade(int g[][MAX], int ordem)
{
    int saida[ordem][ordem];
    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            saida[i][j] = g[i][j];
        }
    }

    for (int k = 0; k < ordem; k++)
    {
        for (int i = 0; i < ordem; i++)
        {
            for (int j = 0; j < ordem; j++)
            {
                saida[i][j] = (saida[i][j] || ((saida[i][k]) && (saida[k][j])));
            }
        }
    }

    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            printf("%d ", saida[i][j]);
        }
        printf("\n");
    }
}

// Caso 14: emparelhamento máximo
void encontraEncaminhamentoMax(int ordem)
{
    for (int i = 0; i < ordem; i++)
    {
        for (int j = ordem; j > 0; j--)
        {
            if (grafo[i][j])
            {
                for (int k = 0; k < ordem; k++)
                    grafo[j][k] = 0;
                if (i < j)
                    printf("%d-%d\n", i, j);

                else
                    printf("%d-%d\n", j, i);

                j = 0;
            }
        }
    }
}

//caso 15: numero cromatico
int numero_cromatico(int ordem)
{

    int grau[ordem];

    int decrescente[ordem];
    int analisados[ordem];
    bool analise_completa = false;
    int cont = 0;
    int maior_valor = 0;
    int maior_indice = 0;

    int cor[ordem];
    //inicializa��o
    for (int i = 0; i < ordem; i++)
    {
        grau[i] = 0;
        analisados[i] = 0;
        decrescente[i] = -1;
        cor[i] = -1;
    }
    //grau dos nos
    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            if (grafo[i][j] == 1)
            {
                grau[i]++;
            }
        }
    }
    //organizando os n�s por ordem decrescente de grau
    for (cont = 0; cont < ordem; cont++)
    {
        maior_valor = 0;
        maior_indice = 0;
        for (int i = 0; i < ordem; i++)
        {
            if (grau[i] > maior_valor && analisados[i] == 0)
            {
                maior_valor = grau[i];
                maior_indice = i;
            }
        }
        analisados[maior_indice] = 1;
        decrescente[cont] = maior_indice;
    }

    //algortimo de welsh-powel
    cor[0] = 1;

    //para c1
    //para cada cor, pensando que o m�ximo de cores e 4
    for (int ci = 1; ci < 5; ci++)
    {
        //printf("analisando cor %i \n",ci);
        //para cada vertice
        for (int i = 0; i < ordem; i++)
        {
            int colorir = 1;
            //a cor foi definida nesse vertice?
            if (cor[i] == -1)
            { //sim, ou seja, ainda nao tem cor
                //para cada possibilidade de adjacencia do vertice
                for (int j = 0; j < ordem; j++)
                {
                    //o vertice � adjacente a essa possibilidade de adjacencia ?
                    if (grafo[i][j])
                    { //sim,
                        //essa adjacencia tem cor diferente de de ci?
                        if (cor[j] == ci)
                        { //sim e diferente, logo, nao impede o vertice de ser colorido com c1, entao colorir nao muda seu estado
                            colorir = 0;
                        }
                        else
                        { //nao, logo essa adjacencia � igual a ci, entao o vertice i nao pode ser pintado de ci
                        }
                    }
                    else
                    {
                    }
                } //depois de analisar todas as possiveis adjacencias em um vertice nao colorido, se colorir ainda for =1, entao pode colorir
            }
            else
            { //se cor != -1, entao ele ja foi colorido, ou seja, nao pode ser colorido de novo
                colorir = 0;
            }

            //se ate aqui cor ainda e igual a 1, entao ele nao foi colorido e nenhuma das adjacencias impede ele de ser ci, logo, pode ser ci
            if (colorir == 1)
            {
                cor[i] = ci;
            }
        }
    }

    int numero_cromatico_resultado = 0;
    for (int i = 0; i < ordem; i++)
    {
        if (cor[i] > numero_cromatico_resultado)
        {
            numero_cromatico_resultado = cor[i];
        }
    }

    return numero_cromatico_resultado;
}

// Caso 16: PRIM

int PRIM(int ordem)
{
    int verticeAtual, custoMin, pesoArv = 0;
    int custoTemp = 0; //Peso final da �rvore
    int verticesAnalisados = 0;
    int custo[ordem];
    bool visitado[ordem];

    //Verificar se o Grafo � conexo
    BuscaProfundidadeAdjac(ordem, 0, visitado);
    for (int i = 0; i < ordem; i++)
        if (!visitado[i])
            return -1;

    for (int i = 0; i < ordem; i++)
        visitado[i] = 0;

    for (int i = 0; i < ordem; i++)
        custo[i] = INF;
    verticeAtual = 0;
    custo[verticeAtual] = 0; //Vertice Inicial Definido

    while (verticeAtual != -1)
    {
        verticesAnalisados++;
        visitado[verticeAtual] = true;
        custoTemp += custo[verticeAtual];

        for (int j = 0; j < ordem; j++)
            if (grafo[verticeAtual][j])
                custo[j] = (custo[j] > grafo[verticeAtual][j]) ? grafo[verticeAtual][j] : custo[j];

        verticeAtual = -1;
        custoMin = INF;

        for (int i = 0; i < ordem; i++)
            if (!visitado[i] && custo[i] < custoMin)
            {
                verticeAtual = i;
                custoMin = custo[i];
            }
    }

    for (int i = 0; i < ordem; i++)
        pesoArv += custo[i];
    return custoTemp;
}

// Case 17)

struct t_aresta
{
    int dis;
    int x, y;
};

bool comp(t_aresta a, t_aresta b) { return a.dis < b.dis; }

#define MAXN 50500
#define MAXM 200200

t_aresta aresta[MAXM];

int pai[MAXN];
int peso[MAXN];

// arvore
t_aresta mst[MAXM];

int find(int x)
{
    if (pai[x] == x)
        return x;
    return pai[x] = find(pai[x]);
}

void join(int a, int b)
{
    a = find(a);
    b = find(b);
    if (peso[a] < peso[b])
        pai[a] = b;
    else if (peso[b] < peso[a])
        pai[b] = a;
    else
    {
        pai[a] = b;
        peso[b]++;
    }
}

//principal
void kruskal(int ordem)
{
    int n, m = 0, pesoAGMax = 0;
    n = ordem;
    for (int i = 0; i < ordem; i++)
    {
        for (int j = 0; j < ordem; j++)
        {
            if (j > i)
            {
                if (grafo[i][j] != 0)
                {
                    m++;
                    aresta[m].x = i + 1;
                    aresta[m].y = j + 1;
                    aresta[m].dis = grafo[i][j];
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        pai[i] = i;

    // ordenar as arestas
    std::sort(aresta + 1, aresta + m + 1, comp);

    int size = 0;
    for (int i = m; i >= 1; i--)
    {
        if (find(aresta[i].x) != find(aresta[i].y))
        {
            join(aresta[i].x, aresta[i].y);

            mst[++size] = aresta[i];
        }
    }
    // imprimir a MST
    for (int i = 1; i < n; i++)
        pesoAGMax += mst[i].dis;
    printf("%d\n\n", pesoAGMax);
}

int main()
{
    int operacao, ordem, tamanho;
    int inicial, r, d;
    //variavel para o caso 10: centro
    int conjunto_centro[MAX];
    /*
 Declaração de outras variáveis necessárias ao trabalho
 int a, b, p;
 int i, j, k;
 int Soma;
*/
    while (true)
    {
        scanf("%d", &operacao);
        if (!operacao)
            break;
        switch (operacao)
        {
        case 1: // Caso exemplo - Verificar se o Grafo é regular
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            if (regular(ordem))
                printf("Grafo regular\n");
            else
                printf("Grafo nao regular\n");
            break;
        case 2:
            scanf("%d", &ordem);
            scanf("%d", &tamanho);
            leGrafo(grafo, ordem, ordem);
            printf("Grafo ");
            if (!is_kRegular(tamanho, ordem))
                printf("nao ");
            printf("%d-regular\n", tamanho);
            break;
        case 3:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            if (euleriano(ordem))
                printf("Grafo Euleriano\n");
            else
                printf("Grafo nao Euleriano\n");
            break;
        case 4:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            eulerianoCircuit(ordem);
            break;
        case 5:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            printf("%d\n\n", conexos(ordem));
            break;
        case 6:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            printf("Grafo ");
            if (!isCompleto(ordem))
                printf("nao ");
            printf("Completo");
            break;
        case 7:
            scanf("%d %i", &ordem, &inicial);
            leGrafo(grafo, ordem, ordem);
            printf("\n");
            printf("%i \n", excentricidade(ordem, inicial));
            break;
        case 8:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            r = raio(ordem);
            printf("%d", r);
            break;
            break;
        case 9:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            d = diametro(ordem);
            printf("%d", d);
            break;
        case 10:

            scanf("%d", &ordem);

            for (int controle = 0; controle < ordem; controle++)
            {
                conjunto_centro[controle] = 0;
            }
            leGrafo(grafo, ordem, ordem);
            centro(ordem, conjunto_centro);
            printf("\n");
            for (int controle = 0; controle < ordem; controle++)
            {
                if (conjunto_centro[controle] == 1)
                {
                    printf("%i ", controle);
                }
            }
            break;
        case 11:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            calcularComplemento(ordem);
            break;
        case 12:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            isBipartido(ordem);
            break;

        case 13:
            //marcos
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            alcancabilidade(grafo, ordem);
            break;
        case 14:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            encontraEncaminhamentoMax(ordem);
            break;

        case 15:

            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            printf("\n");
            printf("%i \n", numero_cromatico(ordem));
            break;
        case 16:
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            if (PRIM(ordem) == -1)
                printf("NAO CONEXO");
            else
                printf("%d", PRIM(ordem));
            break;
        case 17:
            //marcos
            scanf("%d", &ordem);
            leGrafo(grafo, ordem, ordem);
            kruskal(ordem);
            break;
        }
        printf("\n");
    }
    return 0;
}