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(){
}