Grafos con listas de adyacencia

[zkraven]

Quiero representar el siguiente grafo ( https://drive.google.com/file/d/1fOm0w3xnxl9KzZOABiISkyx9fwvHcYHt/view?usp=sharing ), el caso es que tiene que ser necesariamente con una lista de listas, es decir, en una primera lista deben estar todos los vértices que componen cada grafo. Cada elemento de esta lista  tiene que contener el vértice, el enlace al siguiente vértice y un enlace a la lista de vértices adyacentes (componen las aristas).
Y la lista de adyacencia de cada vértice contiene la dirección del vértice adyacente, el peso de la arista (en los casos que existan) y el siguiente nodo que compone esta lista.
Alguna sugerencia

[Serapis]

Por cómo lo cuentas no queda claro:
1 - Si el ejercicio consiste en trasladar dichos datos a las listas y ya.
2 - O si el ejercicio auténtico ha de comenzar una vez pasados esos datos a las listas para luego operar con ellos. Es decir en este caso resulta pueril, obtener la lista de nodos únicos, pués se hace a mano todo.

La lista única de elementos será:
---> Madrid, Valencia, Alicante, Zaragoza, Barcelona Huesca
Permíteme ahorrar tecleo, sustituyendo el nombre de la ciudad por su inicial (pués no hay repes):
Lista única: MVAZBH

La forma de describir las relaciones, sería así:
   M = V|Z  
Es decir Desde Madrid puede irse por igual a Valencia que a Zaragoza, (son opciones).
Una ciudad a la que se accede desde varios puntos, aparecerá más de una vez a la derecha del '=', es el caso de Zaragoza:
   M = Z
   H = Z
Una ciudad a la que no se accede desde ninguna parte, solo aparecerá a la izquierda, por ejemplo Madrid y Huesca.
Técnicamente en teoría de compiladores, solo una producción es la raíz, el resto de producciones así se las llama 'muertas'.
Todos los términos que solo aparecen a la derecha (nunca llevan a otro nodo), se llaman terminales.
Todas las producciones que describen este grafo sería:
   M = V|Z
   V = A
   A = ""   // nulo
   Z = B
   B = ""  // nulo
   H = Z
...ahora bien si introducimos el concepto de lista, entonces (esas producciones, ciudades a) las que no se accede desde ninguna parte, son miembros-términos de lista, supongmaos que lista lo representamos como 'L', entonces la raíz será:
   L = M|H
Es decir, a Madrid y Huesca se accede desde Lista...
Como es la raíz, conviene ponerla encima del resto.
Así finalmente esta sería la lista de listas.
   L = M|H
   M = V|Z
   V = A
   A = ""   // nulo
   Z = B
   B = ""  // nulo
   H = Z

Una lista siempre se compone de elementos, ítems, nodos da igual como los quieras llamar...
El caso es que como (sucede en los grafos) cada elemento es a su vez una lista...
Se debe crear una clase lista, y estos podrían ser sus miembros:
Nombre (ejemplo): "Lista", "Madrid", Huesca
Siguiente: la/las listas a la que se accede desde él. Como pueden ser más de una ciudad, esto en efecto en vez de ser un nodo es una lista.
Padre: Nodo que dirige hacia él. Si cabe la posibilidad que más de un nodo apunte a él, también debe ser una lista, en vez de un nodo.
Estos miembros serán útiles para su recorrido.

Sin embargo como tenemos aún un valor más que consignar y no es único (la distancia), es conveniente que cada lista contenga a su vez un nodo y sea éste el que accede a la lista (es decir Siguiente será una instancia de nodo).

Clase Nodo:
Origen: Una referencia a la lista (la ciudad) en la que está.
Destino: Una referencia a la lista (la ciudad) a la que se llega.
Valor, distancia, tiempo: el dato a consignar, por ejemplo 300.

Entonces la lista (L = M|H), tendrá dos nodos.

Código [Seleccionar] Expandir


Lista L = CrearLista("Lista")


Código [Seleccionar] Expandir


Lista = funcion CrearLista(string Nombre)
   lista Ls = nueva Lista
   Ls.Nombre = Nombre

   devolver Ls
fin funcion


Código [Seleccionar] Expandir


n = CrearNodo( "Lista", "Madrid", 0)
L.add(n)

n= CrearNodo(Lista, Huesca, 0)
L.Add(n)

// Nota: origen es obligado que exista ya. Destino puede o no existir.
nodo = Funcion CrearNodo(Lista Origen, Lista Destino, string sDestino, entero Valor)
   Si Destino = null luego
       Destino = CrearLista(sDestino)
   Fin si
   n = nuevo nodo
   n.Origen = Origen
   n.destino = Destino
   n.Valor = valor

   devolver n
fin funcion


He dejado para el final, el pegamento que une todo, la función general que se invoca.
Pero antes de ello, es preciso darse cuenta que la lista de producciones, aunque es completa y correcta, no contiene los valores, así que modificamos las produciones d ela siguiente manera:
Z = B-300
Es decir señala que desde Zaragoza se accede a Barcelona con una distancia de 300.
Ahora modificamos todas las producciones para canonizarlas de dicha manera:
   L = M-0|H-0
   M = V-300|Z-300
   V = A-200
   A = "-0"   // nulo y distancia 0
   Z = B-300
   B = "-0"  // nulo
   H = Z-100

Todavía se puede simplicar el formato (para poder enviarlo como n string a una función 'GenerarGrafo' que devuelva como resultado la lista raíz...), en dos pasos:
1 - Si acordamos que de cada producción la primera es la ciudad origen, así podemos deshacernos del '='
   LM-0|H-0
   MV-300|Z-300
   VA-200
   A-0   // nulo y distancia 0
   ZB-300
   B-0  // nulo
   HZ-100
2 - y disponerlas todas juntas en un unico string, pero diferenciadas por un separador, por ejemplo ';'...
   LM-0|H-0;MV-300|Z-300;VA-200;A-0;ZB-300;B-0;HZ-100

Código [Seleccionar] Expandir


string producciones = "LM-0|H-0;MV-300|Z-300;VA-200;A-0;ZB-300;B-0;HZ-100"
Lista L = GenerarGrafo(producciones)

Ahora ya podemos pasar este string con tal formato, que contiene todos los datos del grafo, a una función que desguace e interprete el string, para generar la lista.

La función generar grafo:
- Primero debe partir el string recibido por el carácter ";" dejándolo en un array (función Split, suelen partir un string por un char o string y dejarlo en un array)

Código [Seleccionar] Expandir


// Algo así suelen funcionar las funciones de split....
array de string prods = split(producciones, ";")

- Cada índice en ese array contiene una producción. Como cada producción puede tener más de un nodo, nuevamente debe partirse mediante un split y el separador "|", en las ciudades (array ciudades).
- Si éste array tiene ciudades (´vease que las ciudades 'terminales' no llevan a ninguna otra, luego estaría vacío), la primera debe separarse en la ciudad origen (que es la que usamos para crear la lista para dichas ciudades) y la primera ciudad...
Ejemplo:

Código [Seleccionar] Expandir


prods(1) = "MV-300|Z-300"
array de string ciudades = Split(prods(x), "|")
Si ciudades.count > 0
   string origen = ciudades(0).firstchar
   ciudades(0).deletefirstChar

   lista ls = CrearLista(origen)

   por cada ciudad en ciudades
        3******
      nodo n = CrearNodo(Ls, Ld,
      ...
   siguiente
fin si

- Luego, antes de crear los nodos, en las ciudades aún estarán en la forma 'inicial + distancia', luego nuevamente hay que hacer un split, para separar la letra del valor y así poder crear el nodo, con los parámetros precisos.

En resumen, la función GenerarGrafo, será interpretar el parámetro de entrada para ir separándolo en sus partes y en varios bucles anidados, ir tratando cada cosa. A la entrada se obtiene el array de producciones, luego en un primer bucle se procesa cada producción. Que lo que haces es desguazar dicha producción en la ciudad origen y las ciudades a las que se accede. Si la ciudad es terminal, no tendrá ciudades, peor sí sí tiene.... Entonces en un segundo bucle se procesa cada ciudad de una producción, en el se separa la ciudad del valor de la distancia y luego crea el nodo con tales datos, y cada nodo se inserta en la lista de dichas producciones, etc...


Probablemente te resulte complicado de entender de una sola lectura, así que te aconsejo releerlo varias veces... y luego ya si eso, haces preguntas concretas.