Aula 3: Grafos Ponderados + Matriz de Adjacência

[JayCesar]

📚 Implementação de grafos por matriz de adjacência

Grafo ponderado:

Dicas de programação em C (modularização em C)

Matriz adjacente com Peso:

---

Passagem por valor x passagem por referência

Quando eu passo uma variável como parâmetro por valor, eu altero somente dentro do método e não fora dele: Passagem de parâmetro por VALOR: o argumento é avaliado e COPIADO para o parâmetro

Obs: Por isso: dizemos que a mudança em um parâmetro dentro de um método não se reflete fora dele: variáveis locais.

E passagem por referência?

Passagem de parâmetro por REFERÊNCIA: o parâmetro é um apelido (“atalho”) para o argumento (os dois apontam para o mesmo endereço em memória!!!) - Mas isso é somento possível com C++

Fazendo isso em C:

Passando o endereço (ponteiro) da variável a ser alterada: o endereço é COPIADO (passagem por valor, afinal), mas aponta para o mesmo espaço em memória que contém a variável que você quer alterar!!!)

---

Pausa para dicas de programação (mensagens de erro)

Explicações anotadas em código:

#include <stdbool.h> /* variáveis bool assumem valores "true" ou "false"*/

#define MAXNUMVERTICES 100
#define AN -1 /*aresta nula, ou seja, valor que representa ausência de aresta*/

// Grafo não ponderado
typedef struct {
    bool mat[MAXNUMVERTICES][MAXNUMVERTICES];
    int numVertices;
    int numArestas;
} GrafoNaoPonderado;

// Grafo podnerado
typedef int Peso;
typedef struct {
    Peso mat[MAXNUMVERTICES][MAXNUMVERTICES];
    int numVertices;
    int numArestas;
} GrafoPonderado;

// Dicas de C
// Obs: Passagem por valor x passagem por referência

/*
inicializaGrafo(Garfo*, int nv): inicializa um grafo com nv vertices
Vertices vão de 1 a nv
Preenche as células com AN (representando ausência de aresta)
Retorna true se incializou com sucesso e false caso contrário
*/

bool inicializaGrafo(GrafoNaoPonderado* grafo, int nv){
    int i, j;
    if (nv > MAXNUMVERTICES){
        fprintf(stderr, "ERRO na chamada de incilizaGrafo: Numero de vertices maior que o maximo permitido de %d,\n", MAXNUMVERTICES);
        return false;
    }
    if(nv <= 0){
        fprintf(stderr, "ERRO na chamada de inicializaGrafo: Numero de vertices deve ser positivo.\n");
        return false;
    }

    grafo->numVertices = nv;
    grafo->numArestas = 0;

    for(int i = 0; i < grafo->numVertices; i++){
        for(int j = 0; j < grafo->numVertices; j++){
            grafo->mat[i][j] = AN;
        }
    }
    return true;
}

int main(){
    GrafoNaoPonderado g1;
    int numVertices;

    inicializaGrafo(&g1, 10);

    // imprimeGrafo(&g1)
    return 0;
}

Conclusão:

grafo_matrizadj.h:

#include <stdbool.h> /* variáveis bool assumem valores "true" ou "false"*/

#define MAXNUMVERTICES 100
#define AN (-1) /*aresta nula, ou seja, valor que representa ausência de aresta*/

typedef int Peso;
typedef struct {
    Peso mat[MAXNUMVERTICES][MAXNUMVERTICES];
    int numVertices;
    int numArestas;
} Grafo;

bool inicializaGrafo(Grafo* grafo, int nv);

grafo_matrizadj,c:

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

#include "grafo_matrizadj.h"

bool inicializaGrafo(Grafo* grafo, int nv) {
    if (nv > MAXNUMVERTICES) {
        fprintf(stderr, "[inicializaGrafo] ERROR - Numero de vertices maior que o maximo permitido de %d.\n", MAXNUMVERTICES);
        return false;
    }

    if (nv <= 0) { 
        fprintf(stderr, "[inicializaGrafo] ERROR - Numero de vertices deve ser positivo.\n");
        return false;
    }

    grafo->numVertices = nv;
    grafo->numArestas = 0;
    for (int i = 0; i < grafo->numVertices; i++) {
        for (int j = 0; j < grafo->numVertices; j++) {
            grafo->mat[i][j] = AN;
        }
    }
    return true;
}

testa_grafo.c:

#include <stdio.h>

#include "grafo_matrizadj.h"

int main() {
    Grafo g1;
    int numVertices;

    inicializaGrafo(&g1, 10);
    return 0;
}