Libreria de grafos

[m@o_614]

Saludos

Tengo que hacer un programa que me dice que cree un grafos simple( no permite mas de una arista entre dos vertices), que sean dirigido o no dirigido y que puede agregar o eliminar aristas y vertices, pero la verdad no tengo muy claro si debo de hacerlo con un arreglo de listas que es una opcion que me dijo el profesor que podia hacer, pero yo la veo muy dificil porque nunca he hecho un arreglo de listas, y tampoco se si tengo que pedirle el numero de vertices y de aristas al inicio del programa, si tengo que verificar que no este vacio el grafo antes de eliminar un vertice,si los vertices los represento como nodos las aristas tambien las tengo que crear como nodos??,puedo crear una arista aun si no tengo vertices?? esto lo tengo que validar tambien?? les agredeceria que me dieran algunas sugerencias de como empezarlo porque no tengo ni la mas minima idea

gracias

[rir3760]

Una opcion para almacenar los vertices es una lista, la otra una matriz. Como siempre puedes empezar revisando sitios como Wikipedia.

Un saludo

[m@o_614]

gracias rir3760 por tu respuesta, tu te refieres a almacenar los vertices con una lista ligada y las aristas con una matriz??? grafo[vertice1][vertice2] = arista, donde arista esta entre el vertice1 y el vertice2, pero si los vertices son nodos de una lista como los voy a poner como indice de una matriz??

[rir3760]

En una matriz de adyacencias solo almacenas el peso del vértice o bien un valor especial para indicar que el vértice entre las aristas no existe. El caso de la lista de adyacencias es similar (solo si existe el vértice se almacena el peso correspondiente).

Si tenemos este grafo:

Código [Seleccionar] Expandir

A ---- B ---- C ---- D
       |      |
       |      |
       E ---- F

La matriz de adyacencias es:

Código [Seleccionar] Expandir

  A B C D E F
A - 4 - - - -
B 4 - 4 - 2 -
C - 4 - 4 - 2
D - - 4 - - -
E - 2 - - - 4
F - - 2 - 4 -
Donde cada entrada "matriz[ i ][ j ]" indica si las aristas están conectadas o no.

Un saludo

[m@o_614]

Saludos, ya comence a hacer el codigo, primero tengo una typedef struct que me indica que voy a tener una matriz de tipo int a la que le tengo que asignar memoria dinamicamente y el numero de vertices, le pido cuantos vertices y aristas quiero, y despues inicializo el grafo, osea que cada uno de los elementos de la matriz sean -1  indicandome que no hay arista entre los vertices i y j, pero no se si esta parte y la de agregarArista estan bien hechas, exactamente esta parte:

Código (c) [Seleccionar] Expandir

void inicializaGrafo(Grafo *grafo,int num)
{
   int i,j,valor;
   grafo->numVertices = num;
   grafo->elementos = (int**)malloc(valor = num*num*sizeof(int));
   for(i=0;i < num;i++)
   {
       for(j=0;j < num;j++)
          grafo->elementos[i][j] = -1;
   }
}


el codigo completo es este:

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#define AGREGAR_ARISTAS 1
#define ELIMINAR_ARISTAS 2
#define SALIR 3

typedef struct
{
   int **elementos;
   int numVertices;
}Grafo;

int max_aristas(int num);
void agregarArista(int arista,int vertice1,int vertice2,Grafo *grafo);

int main()
{
   Grafo grafo;
   int opcion,numAristas,num,continuar = 1,maximo,arista,vertice1,vertice2;
   printf("Libreria de Grafos!!\n");
   printf("Dame numero de vertices: ");
   scanf("%d",&num);
   printf("Dame numero de aristas: ");
   scanf("%d",&numAristas);
   maximo = max_aristas(num);
   if(numAristas > maximo)
      printf("Error! El grafo no puede tener mas de %d aristas",maximo);
   else
   {
       inicializaGrafo(&grafo,num);
       do
       {
           printf("1. Agregar Arista\n");
           printf("2. Eliminar Vertice\n");
           printf("3. Eliminar Arista\n");
           printf("4. Salir\n\n");
           scanf("%d",&opcion);
           case AGREGAR_ARISTAS:
              printf("Dame el valor de la arista: ");
              scanf("%d",&arista);
              printf("Dame el valor del primer vertice: ");
              scanf("%d",&vertice1);
              printf("Dame el valor del segundo vertice: ");
              scanf("%d",&vertice2);
              agregarArista(arista,vertice1,vertice2,&grafo);
              break;
           case ELIMINAR_ARISTAS:
              //eliminarArista();
              break;
           case SALIR:
              continuar = 0;
              break;
           default: printf("Opcion invalida\n");
       }while(continuar);
   }
   return 0;
}

int max_aristas(int num)
{
   int maximo;
   maximo = (num(num-1))/2;
   return maximo;
}

void inicializaGrafo(Grafo *grafo,int num)
{
   int i,j,valor;
   grafo->numVertices = num;
   grafo->elementos = (int**)malloc(valor = num*num*sizeof(int));
   for(i=0;i < num;i++)
   {
       for(j=0;j < num;j++)
          grafo->elementos[i][j] = -1;
   }
}

void agregarArista(int arista,int vertice1,int vertice2,Grafo *grafo)
{
   grafo->elementos[vertice1][vertice2] = arista;
}


gracias