[ Foro de Pascal ]

Lista adyacente del fichero de ayer...

Hola de nuevo!

Hoy me ha surgido una nueva duda mucho mas dificil que la de ayer jejeje. El caso es que ahora necesito que, usando listas enlazadas, muestre una lista de adyacencia con respecto al fichero de ayer. El verdadero fichero sería:
____________________________________________________________
(La tercera columna no me hace falta para nada en este caso)
1
4 // indica el numero de vertices
1 2
1 3
2 3
2 4
3 4
____________________________________________________________

El caso sería que muestre por pantalla los vertices adyacentes a 1,2,3 y 4, es decir, por pantalla debería salir esto:

Adyacentes a vértice 1: 2, 3
Adyacentes a vértice 2: 3, 4
Adyacentes a vértice 3: 4
Adyacentes a vértice 4: (nil)

Me podéis dar alguna idea de cómo realizar esto???

Gracias!

---

ahora no tengo mucho tiempo para pensarlo bien pero la cosa vendria a ser para decir lo que tiene cada uno hacer un
for 1 to numerodevertices do
while (no feof(fich))
leo 2 numeros de estos
1 2
1 3
2 3
2 4
3 4
if (contadordefor==primernumero) then escribir el segundo numero

la idea es algo asi jaja lo pongo medio en c pork de pascal no me acuerdo pero para entender la idea creo que sirve, enga taluego.

---

Muchas gracias por la respuesta!

La verdad es que yo también había pensado en algo parecido pero, el caso es que debo hacerlo con listas (punteros). Por eso me encontraba y me encuentro confuso, sobretodo porque no controlo mucho la parte de punteros... y no se me ocurre como empezar a hacerlo.

Gracias de todas formas!

---

Pues por lo que te puedo decir, no tengo aún mente de programador, pero en la facultad estamos ahora liados con las listas y tal, así que si quieres te puedo pasar algún tipo de funcion o procedimiento que te haga falta para leer datos, añadir, etc en listas, con punteros y tal.

Saludos.

---

Pues me harías un gran favor, solo si no es mucha molestia para tí. Muchas gracias!

---

Yo te diría que primero pruebes a implementarlo como Array, para entender la parte básica del funcionamiento, lo que es relativo a grafos, el significado de la adyacencia, etc.

Cuando funcione bien como array, es el momento de intentar convertirlo a memoria dinámica, pero no antes (no hasta tener claro el problema).

El manejo de listas enlazadas lo tienes en el tema 13 del curso:
http://www.aprendeaprogramar.com/mod/resource/view.php?id=156

---

Hola, gracias por contestar!!

La verdad es que estuve un poco espeso con esa práctica, al final me cogí apuntes de listas, etc... y lo conseguí. Lo que implementé fue un 'array de listas' no se si se puede llamar así, pero hice eso jeje. Cada lista era un array que contenía datos guardados con listas, no se si me explico bien...

Si a alguien le interesa el código que avise y lo cuelgo en el foro.

Gracias!!

---

Si cuelgas el código en el foro yo te lo agradecería, porque precisamente ahora tengo que hacer una práctica de listas de arrays y no me vendría mal.

Saludos!!

---

No se si se trata del código mas óptimo pero, funciona!!! jejeje.

Recuerdo su funcionamiento: En primer lugar hay que leer datos de un fichero, el primer dato del fichero me dirá si es dirigido o no (0 o 1). El siguiente dato me muestra el numero de vertices del grafo. Y luego, los siguientes datos, la primera columna me dice que conecta con la segunda y viceversa en caso de que el grafo sea no dirigido que tendré que comparar la 1ª con la 2ª y luego la 2ª con la 1ª columna...

procedure lista_adyacencia(lista : lista_ady; var final : punt_nodo);
var
i : integer;
p : punt_nodo;

begin

clrscr;
abrir_fich(fich);

writeln();
writeln(' ==========================');
writeln(' LISTA DE ADYACENCIA GRAFO');
writeln(' ==========================');
read(fich, indicador);
writeln(' Indicador: ', indicador);
read(fich, n_vertices);
writeln(' Numero de vertices: ', n_vertices);

if (indicador = 0) then
writeln(' Grafo: DIRIGIDO')
else if (indicador = 1) then
writeln(' Grafo: NO DIRIGIDO');

for i := MIN to n_vertices do
begin
reset(fich);
read(fich, indicador);
read(fich, n_vertices);

new(lista[i]);
lista[i]^.siguiente := nil;
lista[i]^.vertice := i;

writeln();
write(' Lista ',lista[i]^.vertice,': ');
new(p);
p := nil;

while not eof(fich) do
begin
read(fich, v_ini, v_fin);

if (indicador = 0) then // 0 para grafos dirigidos
begin
if (i = v_ini) then
begin
if (lista[i]^.siguiente = nil) then
lista[i]^.siguiente := final
else
begin
new(p);
final^.siguiente := p;
final := p;
end;
final^.vertice := v_fin;
final^.siguiente := nil;
end;
end
else // 1 para grafos no dirigidos
begin
if ((i = v_ini) or (i = v_fin)) then
begin
if (lista[i]^.siguiente = nil) then
lista[i]^.siguiente := final
else
begin
new(p);
final^.siguiente := p;
final := p;
end;
final^.vertice := v_fin;
final^.siguiente := nil;

// en este caso evaluo si i es igual a la primera o a la segunda columna del fichero ya que estoy viendo grafos NO dirigidos
if (i = v_ini) then
final^.vertice := v_fin;
if (i = v_fin) then
final^.vertice := v_ini;

final^.siguiente := nil;
end;
end;
end;

// MOSTRAR LOS VERTICES ADYACENTES A CADA ARRAY, PARA ELLO ME PONGO CON EL PUNTERO 'P' DESDE EL PRIMER VERTICE ENCONTRADO QUE SERIA A DONDE APUNTA lista^.siguiente.

p := lista[i]^.siguiente;
while (p <> nil) do
begin
write(p^.vertice, ', ');
p := p^.siguiente;
end;
end; // del for i
writeln();
seguir;
close(fich);
end;

---

No es la forma más elegante pero bueno... ;-)

Lo "purista" sería que:

- Cada una de las listas de adyacencia de los vértices fuera una lista simple "normal",

- La lista de vértices fuera algo parecido a un arbol binario, ya que contendrá dos "hijos", uno es el siguiente vértice, y otro es la lista de vértices enlazados con el actual.

Por cierto, tu implementación no funciona correctamente en grafos no dirigidos. Con los datos que tu dabas, siendo grafo dirigido, tendrías

1 2
1 3
2 3
2 4
3 4
->
Adyacentes a vértice 1: 2, 3
Adyacentes a vértice 2: 3, 4
Adyacentes a vértice 3: 4
Adyacentes a vértice 4: (nil)

Pero si el grafo es no dirigido, tu rutina de mostrar podría no ser correcta. Me explico: según te pidan puede que ese fichero no sea correcto para un grafo no dirigido y debieran aparecer tanto 3 4 como 4 3, o bien que el fichero sí fuera correcto y si te hablan de 3 4 se está dando por sentado que también existe la arista 4 3. En ese caso, no bastaría con que miraras el primer vértice, sino que tendrías que recorrer todas las listas de adyacencia de cada vértice, porque el resultado correcto sería:

1 2
1 3
2 3
2 4
3 4
->
Adyacentes a vértice 1: 2, 3
Adyacentes a vértice 2: 1, 3, 4
Adyacentes a vértice 3: 2,4
Adyacentes a vértice 4: 2,3


(Siento contestar tan tarde, pero últimamente no tengo tiempo ni de respirar)

---

---