Grafos em C

[Hataro]

Bom tava implementando uma biblioteca de grafos e digrafos em C usando lista de adjacência pois acho mais simples de manuzear do que uma que use matriz, e tive uma duvida qnt a buscas de caminhos simples, já tenho uma função para buscar um caminho (pathR, DIGRAPHpath que agem por chamada, a 1° recursivamente) porem não informa o tipo, apenas retorna se há ou não um caminho queria que dessem uma olhada nela e me falassem como poderia ser resolvido o problema de achar um caminho simple em um grafo. :rolleyes:

Tive algumas luzes aki xP e uma idéia seria usar um vetor pra contabilizar os vertiçes caso eles se repitam toda vez q a função pathR fosse executada recursivamente. :wacko: ... mas fico aberto a sugestões.

O código é esse:

//BIBLIOTECA LISTA DE ADJACENCIA
#include "stdio.h"
#include "stdlib.h"
#define Vertex int
#define graph digraph
#define Graph Digraph
#define GRAPHinit DIGRAPHinit
#define GRAPHshow DIGRAPHshow
#define maxV 100

static int lbl[maxV], parnt[maxV][maxV];
typedef struct digraph *Digraph; // Objeto do tipo Digraph que contém o endereço de um digraph
typedef struct node *link;

struct digraph {  // Digrafo
    int V;        // Número de vértices
    int A;        // Número de arestas 
    link *adj;    // Ponteiro para a lista de adjacência (são ou não vizinhos)
};

struct node{
  Vertex w;
  link next;
};

link NEW (Vertex w, link next);
Digraph DIGRAPHinit (int V);
void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w);
void DIGRAPHshow (Digraph G);
void GRAPHinsertE (Graph G, Vertex v, Vertex w);

link NEW (Vertex w, link next){
  link x = malloc(sizeof*x);
  x->w = w;
  x->next = next;
  return x;
}

Digraph DIGRAPHinit (int V){
  Vertex v;
  Digraph G = malloc(sizeof *G);
  G->V = V;
  G->A = 0;
  G->adj = malloc(V * sizeof(link));
  for (v = 0; v < V; v++)
    G->adj[v] = NULL;
  return G;
}

void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w){
  link p;
  if (v == w) return;
  for (p = G->adj[v]; p!=NULL; p = p->next)
    if (p->w== w) return;
  G->adj[v]= NEW(w, G->adj[v]);
  G->A++;
}

GRAPHdeg(Digraph G, Vertex v){
  int x = 0;
  link p;
  for (p = G->adj[v]; p == G->adj[v]; p = p->next)
    x++;
  return x;
}
  
void GRAPHinsertE (Graph G, Vertex v, Vertex w){
  DIGRAPHinsertA(G,v,w);
  DIGRAPHinsertA(G,w,v);
}

void DIGRAPHshow (Digraph G){
  Vertex v;
  link p;
  for (v =0; v < G->V; v++){
    printf("%2d:", v);
    for (p = G->adj[v]; p != NULL; p = p->next)
      printf("%2d", p->w);
    printf("\n");
  }
}

/*void GRAPHremoveE(Digraph G, Vertex v, Vertex w){
  link p, p2;

  for(p = G->adj[v]; p != NULL; p = p->next){
    if(p->next == w)
      p2 = p->next;
      p->next = p2->next;
      printf("\n\n%d %d\n\n",p2,p2->next);
  }
}*/

void pathR (Digraph G, Vertex v){
  link p;
  lbl[v] = 0;
  for (p=G->adj[v]; p != NULL; p=p->next)
    if (lbl[p->w] == -1) {
      parnt[v][p->w] = 1;
      pathR(G,p->w);
    }
}


int DIGRAPHpath (Digraph G,Vertex s,Vertex t){
  Vertex v, y;
  for (v = 0; v < G->V; v++) {
    lbl[v] = -1;
    for(y = 0; y < G->V; y++){
      parnt[v][y] = 0;      
    }
  }
  parnt[s][s] = 1;
  pathR(G,s);
  if (lbl[t] != -1) 
    return 1;
  else 
    return 0;
}


main(){
  link next;
  Digraph g;
  int qtd, n, i, gral, y, a, b;
  
  printf("Informe a quantidade de vertices: ");
  scanf("%d", &n);
  printf("\n");
    
  while (n <= 0) {
    printf("Erro: informe outra quantidade ");
    scanf("%d", &n);
  }
  
  g = DIGRAPHinit(n);
  printf("\n# Inserindo Arcos\n");
  
  printf("\nQuantos arcos deseja inserir: ");
  scanf("%d", &qtd);
  printf("\n");
  
  while ((qtd <= 0) || (qtd > (n * (n - 1)))) {
    printf("Errado! Digite outro: ");
    scanf("%d", &qtd);
  }
  
  Vertex v, w;
  for (i = 0; i < qtd; i++) {
    
    printf("\nArco %d\n", i + 1);
    printf("Informe o arco na forma v-w: ");
    scanf("%d-%d", &v, &next);
    DIGRAPHinsertA(g, v, next);
  }
  

  
  printf("\ndigite o caminho para verificar a existencia(v-w): ");
  scanf("%d-%d", &v, &w);
  y = DIGRAPHpath(g, v, w);  
  
  if(y)
    printf("\nexiste caminho!\n");
  else
    printf("\nnao existe caminho!\n");
  
    
  printf("\nDigrafo formado:\n");
  DIGRAPHshow(g);
  
  /*printf("\n\ninforme o vertece q deseja excluir(v-w)");
  scanf("%d-%d",&v, &w);
  GRAPHremoveE(g, v, w );*/
  
  for(a = 0; a < n; a++){
    printf(" %d ",lbl[a]);
  }
  printf("\n\n");
  for(a = 0; a < n; a++){
    for( b = 0; b < n; b++){
      printf(" %d ",parnt[a][b]);
      }
    printf("\n");  
  }
  
  /*
  printf("\nDigrafo formado com aresta apagada:\n");
  DIGRAPHshow(g);*/
  
  system("pause");
  
}

bom, tem alguns pontos demarcados pois tava aki implementando outras funções, mas o foco é na DIGRAPHpath e pathR. Ainda não ta .h pois só vou implementa-la quando fizer todas as operações em um grafo.

Qualker duvida com o entendimento do código so postar q eu explico.

desde já agradeço!

Editado Maio 8, 2010 por quintelab
Removido Dúvida do título e adicionado BBCode Code