1
I’m trying to insert vertices and links into a graph, but it only works when the graph has an even number of edges.
The source code below has the TAD and the functions of inserting and creating graphs. Someone can find the error for me?
#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(){
}