grafos en C ¿ ejemplos ?

[johnny]

Hola. ME gustaria tener algo de codigo par aimplementar grafos en C.
Tengo algo de codigo:

#define MAX_NODOS 10

typedef struct tipo_arco
{
int existe;
int peso;
}arco;


typedef struct _estructura
{
char matrizN[MAX_NODOS];
arco matrizA[MAX_NODOS][MAX_NODOS];
}estructura;



int main(int argc, char* argv[])
{
estructura *grafo;

grafo=(estructura*) calloc(1,sizeof(estructura));

memset(grafo->matrizA,0,sizeof(grafo->matrizA));

grafo->matrizA[0][0].existe=1;






return 0;
}


Como veis corresponde a la matriz de adyacencia. ¿ Es correcto ? ¿ Como
implementar la funcion de añadir un arco ? ¿ Seria simplemente añadir la
informacion correspondiente en la matriz de arcos ?

¿ Que metodos es normal implementar ? ¿ Recorrido en amplitud/profundidad ?

¿ Como podria implementar lista de adyacencia en lugar de matriz ?

gracias

[Super_Lopez]

Post by johnny
ME gustaria tener algo de codigo par aimplementar
grafos en C. Tengo algo de codigo: [..]

Googleando aparecen cienes de ejemplos.
Sin ir muy lejos, en Algoritmia.net y Wikipedia tienes varios.

Post by johnny
Como veis corresponde a la matriz de adyacencia.

Sólo matrizA (de tipo arco) es la matriz. El resto es paja.

Post by johnny
¿ Es correcto ?

No sé para qué define matrizN en la estructura. Quizás para
poner "nombre" a los vértices.

Post by johnny
¿ Como implementar la funcion de añadir un arco ?

Si te refieres a definir una arista entre dos vértices X e Y con
un peso N, basta con guardar los datos correspondientes en la
estructura:

grafo->matrizA[X][Y].existe = 1;
grafo->matrizA[X][Y].peso = X;

Si no es dirigido, recuerda mantener la simetría en la matriz.

Post by johnny
¿ Que metodos es normal implementar ?

Supongo que lo habitual es tal que así (matrices de adyacencia
cuando no suponen un excesivo consumo de recursos) o asignación
dinámica para grafos acíclicos, árboles, etc, según el caso.

Post by johnny
¿ Recorrido en amplitud/profundidad ?

¿En grafos ponderados con ciclos? No sé si congenian demasiado.
Si te refieres a caminos mínimos y esas cosas, lo suyo son los
algoritmos voraces como el de Dijkstra, p.ej.

De todas formas, tienes la matriz de adyacencia, que
precisamente te indica eso, la conexión entre nodos. Como el
ejemplo es de grafos no dirigidos, basta ir saltando de uno a
otro moviendote por la matriz (en realidad, por una similar con
algún arreglo) mediante backtracking o similares.

Post by johnny
¿ Como podria implementar lista
de adyacencia en lugar de matriz ?

¿Para qué quieres una "lista" de adyacencia? La matriz ya te da
toda la información del grafo, ¿no?

Igual lo que quieres es formar un árbol expandido a partir del
grafo. En ese caso, podrías echar un ojo al algoritmo de
Kruskal.

Un saludo.

[johnny]

Post by Super_Lopez

Post by johnny
ME gustaria tener algo de codigo par aimplementar
grafos en C. Tengo algo de codigo: [..]

Googleando aparecen cienes de ejemplos.
Sin ir muy lejos, en Algoritmia.net y Wikipedia tienes varios.

Post by johnny
Como veis corresponde a la matriz de adyacencia.

Sólo matrizA (de tipo arco) es la matriz. El resto es paja.

Post by johnny
¿ Es correcto ?

No sé para qué define matrizN en la estructura. Quizás para
poner "nombre" a los vértices.

Post by johnny
¿ Como implementar la funcion de añadir un arco ?

Si te refieres a definir una arista entre dos vértices X e Y con
un peso N, basta con guardar los datos correspondientes en la
grafo->matrizA[X][Y].existe = 1;
grafo->matrizA[X][Y].peso = X;
Si no es dirigido, recuerda mantener la simetría en la matriz.

Post by johnny
¿ Que metodos es normal implementar ?

Supongo que lo habitual es tal que así (matrices de adyacencia
cuando no suponen un excesivo consumo de recursos) o asignación
dinámica para grafos acíclicos, árboles, etc, según el caso.

Post by johnny
¿ Recorrido en amplitud/profundidad ?

¿En grafos ponderados con ciclos? No sé si congenian demasiado.
Si te refieres a caminos mínimos y esas cosas, lo suyo son los
algoritmos voraces como el de Dijkstra, p.ej.
De todas formas, tienes la matriz de adyacencia, que
precisamente te indica eso, la conexión entre nodos. Como el
ejemplo es de grafos no dirigidos, basta ir saltando de uno a
otro moviendote por la matriz (en realidad, por una similar con
algún arreglo) mediante backtracking o similares.

Post by johnny
¿ Como podria implementar lista
de adyacencia en lugar de matriz ?

¿Para qué quieres una "lista" de adyacencia? La matriz ya te da
toda la información del grafo, ¿no?
Igual lo que quieres es formar un árbol expandido a partir del
grafo. En ese caso, podrías echar un ojo al algoritmo de
Kruskal.
Un saludo.

hola. gracias por la info, pero ¿ me podrias pasar esa direccion exacta
de la wikipedia o de algoritmia.net ? Estoy en las webs principales,
pero no encuentro nada.

gracias
johnny

[johnny]

Post by johnny

Post by Super_Lopez

Post by johnny
ME gustaria tener algo de codigo par aimplementar
grafos en C. Tengo algo de codigo: [..]

Googleando aparecen cienes de ejemplos.
Sin ir muy lejos, en Algoritmia.net y Wikipedia tienes varios.

Post by johnny
Como veis corresponde a la matriz de adyacencia.

Sólo matrizA (de tipo arco) es la matriz. El resto es paja.

Post by johnny
¿ Es correcto ?

No sé para qué define matrizN en la estructura. Quizás para poner
"nombre" a los vértices.

Post by johnny
¿ Como implementar la funcion de añadir un arco ?

Si te refieres a definir una arista entre dos vértices X e Y con un
grafo->matrizA[X][Y].existe = 1;
grafo->matrizA[X][Y].peso = X;
Si no es dirigido, recuerda mantener la simetría en la matriz.

Post by johnny
¿ Que metodos es normal implementar ?

Supongo que lo habitual es tal que así (matrices de adyacencia cuando
no suponen un excesivo consumo de recursos) o asignación dinámica para
grafos acíclicos, árboles, etc, según el caso.

Post by johnny
¿ Recorrido en amplitud/profundidad ?

¿En grafos ponderados con ciclos? No sé si congenian demasiado. Si te
refieres a caminos mínimos y esas cosas, lo suyo son los algoritmos
voraces como el de Dijkstra, p.ej.
De todas formas, tienes la matriz de adyacencia, que precisamente te
indica eso, la conexión entre nodos. Como el ejemplo es de grafos no
dirigidos, basta ir saltando de uno a otro moviendote por la matriz
(en realidad, por una similar con algún arreglo) mediante backtracking
o similares.

Post by johnny
¿ Como podria implementar lista
de adyacencia en lugar de matriz ?

¿Para qué quieres una "lista" de adyacencia? La matriz ya te da toda
la información del grafo, ¿no?
Igual lo que quieres es formar un árbol expandido a partir del grafo.
En ese caso, podrías echar un ojo al algoritmo de Kruskal.
Un saludo.

hola. gracias por la info, pero ¿ me podrias pasar esa direccion exacta
de la wikipedia o de algoritmia.net ? Estoy en las webs principales,
pero no encuentro nada.
gracias
johnny

ya lo encontre, pero en ikipedia no vi codigo