• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

ppt_mac

Duvida em grafos(conversões)

8 mensagens neste tópico

Boas,

    tenho uma duvida que me surgiu enquanto estudava grafos. Num exercicio proposto pelo professor onde temos a  definição de uma estrutra para grafos do tipo:

define V 3

   typedef struct node{
       int destino;
       int peso;
     struct node *next;
   }Node;

typedef int GMA[V][V]; // matriz adjacencia
typedef Node * GLA[V]; // lista adjacencia

void converte(GMA g,GLA h){
int i,j; Node *aux;

for(i=0;i<V;i++) h[i]==NULL;
    for(j=0;j<V;j++){
       if(g[i][j] >=0){
          aux=(Node*)malloc(sizeof(Node));    
      aux->destino=j;
      aux->peso = h[i];
    h[i]= aux;
        }
     }
   }
}

O professor tinha pedido em como exercicio e que provavelmente saia em exame a conversão de GMA e GLA para a representação em Array dos grafos. A minha dúvida é como é feita essa representação dos grafos em Array.  Se me puderem ajudar nessas funções agradecia.

Obrigado

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas,

    tenho uma duvida que me surgiu enquanto estudava grafos. Num exercicio proposto pelo professor onde temos a  definição de uma estrutra para grafos do tipo:

define V 3

   typedef struct node{
       int destino;
       int peso;
     struct node *next;
   }Node;

typedef int GMA[V][V]; // matriz adjacencia
typedef Node * GLA[V]; // lista adjacencia

void converte(GMA g,GLA h){
int i,j; Node *aux;

for(i=0;i<V;i++) h[i]==NULL;
    for(j=0;j<V;j++){
       if(g[i][j] >=0){
          aux=(Node*)malloc(sizeof(Node));    
      aux->destino=j;
      aux->peso = h[i];
    h[i]= aux;
        }
     }
   }
}

O professor tinha pedido em como exercicio e que provavelmente saia em exame a conversão de GMA e GLA para a representação em Array dos grafos. A minha dúvida é como é feita essa representação dos grafos em Array.  Se me puderem ajudar nessas funções agradecia.

Obrigado

Isto aqui está-me a parecer demasiado com algo de Algoritmos e Complexidade.

Estou certo?

(quando eu digo parecer, é por o exercicio/maneira como esta definido, ser igual ao que o Professor Alcino fez.)

De qualquer modo, eu amanha vejo isso, e digo-te qualquer coisa, agora desculpa mas vou dormir.

Não é dificil, acho que tenho isso feito no caderno algures, amanha respondo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estás 100% correcto... Obrigado pela ajuda...Decerteza que uma dessas conversões vai sair no exame..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ora boas, como prometido, cá estou eu.

Só hoje vi bem o teu problema, e surgiu-me uma dúvida.

Tu queres as funções que convertem uma GMA, numa GLA e vice-versa?

esta dúvida em relação a tua questão surgiu-me porque não percebi bem o que querias dizer com isto:

A minha dúvida é como é feita essa representação dos grafos em Array.

O que queres mesmo dizer com isto?

Abraços

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Essa representação em array  é diferente da representação em matrizes. O prof JBB fez essa representação nas aulas teoricas, mas infelizmente não pude assistir.

Após uma pesquisa não sei se será isto :

Incidence list

The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and possibly weight and other data.

As funções que mais gostaria de ver era de GLA -> Array e GMA -> Array... Mandei um mail ao Alcino a pedir essa representação em Array, mas ainda não me respondeu.

Agradeço a tua ajuda.

Abraço

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nunca tinha visto essa representação, mas pelo que percebi, só precisas de ir percorrendo a MA (por exemplo), e para cada posição i e j, em que haja um arco, crias uma nova entrada no array, com o i, o j, e eventualmente o peso e outros dados associados ao arco (se o grafo não for orientado, consideras apenas os valores em que i>=j).

Exemplo:

A seguinte matriz

_ 2 _

_ _ 5

2 _ _

daria:

[(1,2,2),(2,3,5),(3,1,2)]

No caso de LA, o raciocínio é semelhante.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sinceramente, também não fui a essa aula, mas eu tenho colegas que vão ter com o alcino agora, eu se puder peço-lhes que perguntem, senão pergunto a alguém que saiba...

Abraços

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora