1

Estou tentado inserir vértices e ligações em um grafo, mas só funciona quando o grafo tem número par de arestas.

O código-fonte abaixo tem o TAD e as funções de inserir e criar grafos. Alguém consegue achar o erro pra mim?

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define infinito 10000
#define BRANCO 0
#define CINZA 1
#define PRETO 2

typedef struct grafo *Grafo;
typedef struct nodo *link;
typedef struct list nodol;
typedef struct li par;
typedef struct l lista;

void limpar_tela()
{
    //system("cls");
//  printf("\033[2J"); /* limpa a tela */
//  printf("\033[1H"); /* poe o curso no topo */
}


//a lista de adjacência de um vertice que aponta para várias arestas ligantes atravez desta lista do itpo nodo
//onde temo nosso v->w, em que w é o vertice de destino de um vertice V, que é seguida por um link de de apontadores para arestas

struct l
{
    int v;
    lista *proximo;
};



//a lista de adjacência de um vertice que aponta para várias arestas ligantes atravez desta lista do itpo nodo
//onde temo nosso v->w, em que w é o vertice de destino de um vertice V, que é seguida por um link de de apontadores para arestas


struct nodo
{
    int w,peso;
    link proximo;
};

struct li
{
    int peso,a;
};

struct list
{
    int v,w,peso;
    nodol *proximo;
};







//A função novo nodo, como nome diz aparti de um w criamos um link na lista de adj do vertice de origem v
// criamos o novo novo, alocamos e colocando os conteudo W neste e retornamos o próprio nodo para linkar a lista
link Novonodo( int w, link proximo)
{

    link a = malloc( sizeof (struct nodo));
    a->w = w;
    a->proximo = proximo;
    return a;
}



// a struct grafo, representa a repsentação do Grafo por lista de ajdacência, onde que adj é um ponteiro para um vetor
// de lista de adjacência, a V numero de vertices e A número de arestas.
struct grafo
{
    int V;
    int A;
    link *adj;
};

//Aqui criamos um grafo com a quantidade de arestas e vertices informado pelo usuário sem esquecer a restriçao do problema
// criamos uma lista de vertices, que todo seus apontadores são para NULL;

Grafo CriaGrafo( int V, int a)
{
    int x;
    Grafo G = malloc( sizeof *G);
    G->V = V;
    G->A = a;
    G->adj = malloc( V * sizeof (link));
    for (x = 1; x <=V; x++)
        G->adj[x] = NULL;
    return G;
}


///Na função inserir adiciona um link (entre v->w) entrem a origem e destino onde que a variavel QTDA=Quantide de arestas
// primeiro IF vericamos se não ira ligar em um vertice não existente
// depois enquando fazemos a contagem verificamos se existe aresta paralela ou se ira fazer um laço no no grafo caso seja orientado
//no final verificamos se não excedemos a capacidade permitida de inserção de aresta

void inserir(int orientado, Grafo G, int v, int w, int peso)
{
    link a;
    int qtda=0;


    if(orientado==1)
    {



        if ( v==w )
        {

            printf("Nao e possivel adicionar laço\n");
            return;

        }


        if(  w > G->V   )
        {
            printf("Nao e possivel adicionar, este verticce nao existe\n");
            return;
        }


        //conto quantas arestas ja foram adicionadas e verifico se existe aresta paralela e também laço
        for (a = G->adj[v]; a != NULL; a = a->proximo)
        {
            qtda=qtda+1;

            if ( v==w || a->w == v )
            {

                printf("Nao e possivel adicionar aresta paralela\n");
                return;

            }


        }




        //verifico se ira adicionar uma aresta desde que não exceda a quantidade limite estabelecida
        if( G->A > qtda)
        {
            printf("v = %d\n",v);
            G->adj[v] = Novonodo( w, G->adj[v]);

        }
        else printf("Nao e possivel adicionar mais arestas ao vertice|%d|\n", v);

    }
    else
    {
        printf("passou\n");
        //verifico se ira adicionar um laço
        if ( v==w )
        {
            printf("Nao e possivel adicionar laco\n");
            return;
        }


        if(  w > G->V   )
        {
            printf("Nao e possivel adicionar, este verticce nao existe\n");
            return;
        }


        //conto quantas arestas ja foram adicionadas
        for (a = G->adj[v]; a != NULL; a = a->proximo)
        {
            qtda=qtda+1;

            if(a->w==w)
            {
                printf("Nao sera possivel adicionar aresta paralela\n" );
                return;
            }

        }

        //verifico se ira adicionar uma aresta desde que não exceda a quantidade limite estabelecida
        if( G->A > qtda)
        {

            //caso o grafo não seja orientado se eu tendo |v|->[w], terei também de |w|->[v]

            G->adj[v] = Novonodo( w, G->adj[v]);
            G->adj[w] = Novonodo( v, G->adj[w]);


        }
        else printf("Nao e possivel adicionar mais arestas ao vertice|%d|\n", v);


    }
}




//Imprime o grafo  como uma lista de adjacencia
void imprime_grafo_peso(Grafo g)
{

    link a;

    int i=1;
    while(i<=g->V)
    {
        printf("|%d|-",i);

        for(a=g->adj[i]; a!=NULL; a=a->proximo) printf("[%d,p%d]->", a->w,a->peso);


        printf("0\n");
        i++;
    }

    printf("\n");
}


//Crio um nodo do tipo lista para vertices
lista *cria_v(lista *proximo, int v)
{

    lista *novo = malloc( sizeof (lista));
    novo->v=v;
    novo->proximo = proximo;

    return novo;
}


//inicializo a minha lista de com os vertices percentes ao meu grafo
void incializa_lista_Q(lista **q, Grafo g)
{
    *q=NULL;
    int i=1;
    while(i<= g->V)
    {
        *q=cria_v(*q,i);
        i++;
    }
}

///pego um da lista Q e um V dentro dela faço as seguintes verificações

lista* excluir_Q(lista *q, int v)
{
    lista *ant, *atual;
    ant=NULL;
    atual=q;


//verifico  até chegar o final da minha lista de Vertices ou encontrar o elemento a ser excluido
    while(atual!=NULL && atual->v!=v)
    {
        ant=atual;
        atual=atual->proximo;

    }
    //caso não encontro meu elemento retorno o própria lista
    if(atual == NULL) return q;
    //caso o anterior seja null, então apenas precisamos apontar para o próximo elemento da lista
    if(ant==NULL) q=atual->proximo;
//caso contrário existe um elemento no meio atualizo os ponteiros da nova lista
    else ant->proximo = atual->proximo;
//exclui meu vertice atual ou seja desaloca o nó não mais necessário na minha lista
    free(atual);

//retorno minha nova lista de elementos
    return q;



}

int main(){

}

1 Resposta 1

1

1. Os problemas mais simples

Primeiro, você não deve usar isso:

#include <conio.h>

Essa não é uma biblioteca padrão.

Na função ìnserir, você tem o seguinte:

if ( v==w || a->w == v )

Entretanto o v==w já foi verificado mais acima, onde há um return se isso for verdadeiro. Assim sendo, essa subexpressão sempre será falsa, e portanto pode ser eliminada.

Ainda na função inserir, você tem um if(orientado==1) onde grande parte do bloco do if é igual ao bloco do else. Isso daí é uma duplicação de código desnecessária, então seria muito melhor você tirar o bloco do if, manter apenas o bloco do else e então trocar apenas essa linha:

G->adj[w] = Novonodo( v, G->adj[w]);

Por isso:

if (orientado) G->adj[w] = Novonodo(v, G->adj[w]);

A sua função de criar grafos tem um problema:

G->adj = malloc( V * sizeof (link));
for (x = 1; x <=V; x++)
    G->adj[x] = NULL;

Ocorre que arrays em C vão da posição 0 até a tamanho - 1. Uma vez que foram alocados no malloc, um total de V elementos, então a última posição é a V - 1. Assim sendo a correção é essa:

G->adj = malloc(V * sizeof(link));
for (x = 0; x < V; x++) {
    G->adj[x] = NULL;
}

Isso também significa que na função inserir, isso daqui:

if(  w > G->V   )

Deveria ser isso:

if (w >= G->V)

E na imprime_grafo_peso, isso:

int i=1;
while(i<=g->V)

Deveria ser isso:

int i = 0;
while (i < g->V)

Aliás, esse while da imprime_grafo_peso ficaria melhor se você usasse um for.

O mesmo que ocorre no while da imprime_grafo_peso também se aplica à incializa_lista_Q.

Na estrutura nodo, você tem os campos w e peso, mas você só está usando w. Você até lê o peso no imprime_grafo_peso e o imprime, mas nunca define esse peso em lugar nenhum. Observe que você não usa o parâmetro peso da função inserir. Assim sendo, a função Novonodo deveria receber também o peso do nodo.

Na função inserir, você pode trocar o qtda=qtda+1 por qtda++.

2. Alterações estruturais mais profundas

Após fazer as mudanças que recomendei acima, há mais algumas alterações possíveis, porém são alterações estruturais e mais profundas.

Não use typedefs apenas por usar. Isso tende a deixar o código bem confuso. Você usa 5 typedefs em seu código:

typedef struct grafo *Grafo;
typedef struct nodo *link;
typedef struct list nodol;
typedef struct li par;
typedef struct l lista;

Os três últimos typedefs efetivamente só estão dando um nome diferente para alguma outra coisa. Isso tende apenas a causar confusão, vez que você terá coisas que tem dois nomes diferentes sendo que um não é uma simplificação do outro.

Já os dois primeiros typedefs, tendem a obscurecer o fato de que o tipo de dado em questão trata-se de um ponteiro. A menos que você tenha uma boa justificativa para fazer isso, esse tipo de coisa não costuma ser boa ideia.

Além disso, você tem duas estruturas diferentes do tipo lista:

struct l
{
    int v;
    lista *proximo;
};

struct list
{
    int v,w,peso;
    nodol *proximo;
};

Lembrando que lista é um outro nome para l e que nodol é um outro nome para list. Entretanto, você não parece estar usando o list (junto com o nodol) em lugar nenhum, então imagino que o lista e o l seja o que você quer.

Aliás, você parece também não parece usar li e par em lugar nenhum.

A forma que eu recomendo para se definir structs com os devidos typedefs é essa:

typedef struct Exemplo {
    int a, b, c;
    float d;
    OutroStruct *e;
    struct Exemplo *f;
} Exemplo;

Essa forma é bem limpa e clara, usando Exemplo como um sinônimo para struct Exemplo. A única desvantegem é que structs que contenham estrutura recursiva (como a Exemplo aí em cima) precisam usar struct Exemplo ao invés de apenas Exemplo do lado de dentro.

É possível evitar-se o uso de struct Exemplo dentro do próprio Exemplo se você usar protótipos. Além disso, no caso de estruturas indiretamente recursivas, usar protótipos é a melhor solução. Por exemplo:

typedef struct Recursivo Recursivo;
typedef struct Recursivo {
    char i, j, k;
    Recursivo *m;
} Recursivo;

typedef struct Homem Homem;
typedef struct Mulher Mulher;

typedef struct Homem {
    int a, b, c;
    Mulher *esposa;
} Homem;

typedef struct Mulher {
    double x, y, z;
    Homem *marido;
} Mulher;

A sua estrutura lista (também chamada de l) não parece estar sendo usada pelo grafo para nada, ainda mais porque o grafo já tem uma lista de adjacências representada por link e nodo e as funções CriaGrafo, inserir e imprime_grafo_peso sabem cuidar dela. Assim sendo, recomendo excluir a estrutura lista, o typedef l e as funções cria_v, incializa_lista_Q e excluir_Q.

Uma outra coisa que noto, é que o orientado é uma característica do grafo, e não da aresta a ser inserida. Assim sendo, isso deveria estar dentro da estrutura grafo e ser um parâmetro da função CriaGrafo.

Você tem funções para criar nodos e grafos, mas não tem as funções para excluir. é importante criar essas funções também.

Retirando todas as funções, structs e typedefs de listas e pares que você aparentemente não usa, retirando os typedefs não usados, renomeando as coisas para terem nomes mais descritivos (exemplo: origem e destino ao invés de v e w) e acrescentando as funções para excluir, o seu código fica assim:

#include <stdio.h>
#include <stdlib.h>
#define infinito 10000
#define BRANCO 0
#define CINZA 1
#define PRETO 2

void limpar_tela() {
    //system("cls");
    //printf("\033[2J"); /* limpa a tela */
    //printf("\033[1H"); /* põe o cursor no topo */
}

typedef struct Nodo {
    int peso, destino;
    struct Nodo *proximo;
} Nodo;

typedef struct Grafo {
    int maximo_vertices, maximo_arestas_por_vertice, orientado;
    Nodo **adjacencias;
} Grafo;

Nodo *Nodo_novo(int destino, int peso, Nodo *proximo) {
    Nodo *a = malloc(sizeof(Nodo));
    a->peso = peso;
    a->destino = destino;
    a->proximo = proximo;
    return a;
}

void Nodo_destroi(Nodo *nodo) {
    Nodo *atual = nodo;
    while (atual != NULL) {
        Nodo *aux = atual->proximo;
        free(atual);
        atual = aux;
    } 
}

Grafo *Grafo_novo(int orientado, int maximo_vertices, int maximo_arestas_por_vertice) {
    int x;
    Grafo *g = malloc(sizeof(Grafo));
    g->orientado = orientado;
    g->maximo_vertices = maximo_vertices;
    g->maximo_arestas_por_vertice = maximo_arestas_por_vertice;
    g->adjacencias = malloc(maximo_vertices * sizeof(Nodo *));
    for (x = 0; x < maximo_vertices; x++) {
        g->adjacencias[x] = NULL;
    }
    return g;
}

void Grafo_destroi(Grafo *g) {
    int x;
    for (x = 0; x < g->maximo_vertices; x++) {
        Nodo_destroi(g->adjacencias[x]);
    }
    free(g->adjacencias);
    free(g);
}

void Grafo_inserir_aresta(Grafo *g, int origem, int destino, int peso) {
    Nodo *a;
    int qtda = 0;

    if (origem == destino) {
        printf("Nao e possivel adicionar laço\n");
        return;
    }

    if (destino > g->maximo_vertices) {
        printf("Nao e possivel adicionar, este vertice nao existe.\n");
        return;
    }

    for (a = g->adjacencias[origem]; a != NULL; a = a->proximo) {
        qtda++;

        if (a->peso == destino) {
            printf("Nao sera possivel adicionar aresta paralela.\n");
            return;
        }
    }

    if (qtda > g->maximo_arestas_por_vertice) {
        printf("Nao e possivel adicionar mais arestas ao vertice %d.\n", origem);
        return;
    }

    g->adjacencias[origem] = Nodo_novo(destino, peso, g->adjacencias[origem]);
    if (g->orientado) g->adjacencias[destino] = Nodo_novo(origem, peso, g->adjacencias[destino]);
}

void Grafo_imprime(Grafo *g) {
    Nodo *a;
    int i;

    for (i = 0; i < g->maximo_vertices; i++) {
        printf("|%d|-", i);

        for (a = g->adjacencias[i]; a != NULL; a = a->proximo) {
            printf("[%d,p%d]%s", a->destino, a->peso);
        }

        printf("0\n");
    }

    printf("\n");
}

int main() {

}

3. Considerações finais

Ainda noto mais umas coisinhas:

  • Uma vez que você já trabalha com listas encadeadas, é possível se livrar de ter um limite no número de vértices no grafo. A ideia seria manter uma lista de vértices dentro do grafo e dentro de cada vértice colocar a lista de adjacências correspondente. Entretanto, buscar um determinado vértice dentro do grafo se tornaria uma tarefa um pouco (mas só um pouco) mais difícil.

  • Outra coisa que noto é que, mesmo se você quiser ter um limite fixo de vértices, uma vez que você não permite arestas paralelas e nem laços, então temos que o número de arestas por vértice é no máximo igual ao número de vértices menos um. Assim sendo, é bem fácil eliminar-se o limite no número de arestas por vértice.

  • Quanto ao problema de ter que ter um número par de arestas, não achei nada parecido com isso. Entretanto considerando-se que o seu main está vazio e que você não usa o infinito, PRETO, BRANCO e CINZA ainda, acredito que ele esteja incompleto ou que você cometeu um erro em alguma parte que não está no que você postou. Pode também ser algum problema referente a acessar memória fora da região correta, uma vez que você acessava de 1 até V, ao invés de 0 até V - 1, embora acredite que isso é mais improvável.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .