Mensajes

[un tema de hace 14 años]

Has respondido a un tema de hace 14 años. Debes de haber utilizado el buscador, porque estaría sepultado por páginas y páginas de hilos.

Recuerda que no deben revivirse hilos tan antiguos. Si tienes alguna pregunta, abre un nuevo hilo y en todo caso cita el enlace a este hilo (no le veo la ventaja, pero es lo que dictan las normas del foro).

Y no puede ser que simplemente esté hecha con cualquier plantilla y luego modificada a mano... realmente uno cree que siempre todo sitio debe usar forzosamente una plantilla (y solo una y además sin modificar)?.

Cualquiera con los conocimientos adecuados puede usar una plantilla (cualquiera), simplemente para adelantar-ahorrar trabajo y luego ponerse a modificar a su antojo, donde al final no quede rastro de su origen o parezca proceder de diferentes plantillas.

Ya. Pero las respuestas han sido dadas.

Lo único que no se ha detallado es el cálculo de la entropía que debe uno asumir que es justamente lo que estais estudiando y en lo que debeis demostrar que habeis comprendido. Si uno resuelve eso, por vosotros, no mereciríais entonces la nota que os den, pues no os la habríais ganado al resolveros la tarea.

Solo aclararé por si quedan algunas dudas que en todo sistema, la suma de las probabilidades de aparición de cada símbolo (que aparecen en el sistema concreto) debe ser igual a 1, pués es lo mismo que decir la suma de las partes equivalen al todo (obvio, no?).

Inicialmente, por teoría: la frecuencia de aparación de cada símbolo (cáracter) en este caso sería 1/96. Como decía más arriba, si el texto tiene exactamente 96 caracteres y cada uno aparece una sola vez (lo que se llama ideal), entonces cada caracter aparece exactamente 1/96 que multiplicado por 96 (o 1/96 + 1/96... es decir 96 sumas) = 1
El 96 viene de que son 96 los caracteres imprimibles, pués es de asumir que tirais de un fichero de texto. Salvo que el profesor os hubiera indicado expresamente algo como a-z = A-Z... en cuyo caso las 'cuentas' deben cambiar.

Entonces, vuestro trabajo es considerar la cantidad de caracteres que contiene la línea y contar la aparición de cada símbolo-carácter, y así determinar su frecuencia de aparición. La suma luego de todas las probabilidades debe sumar 1 (o 0.9999999 que puede darse por un asunto de falta de precisión). No hagais redondeos en las probabilidades, a lo sumo eliminad lo que exceda de 4 decimales. incluso un valor 0.98 el profesor entenderá que ha sido resuelto... y dirá lo que oportunamente considere respecto de la precisión si lo considera necesario.

Pongo un ejemplo y no diré más:
-------------------------------------------------
Si tengo el texto: "independientemente"
Los símbolos únicos son: i,n,d,e,p,m,t
Cuantas veces aparece cada símbolo?:
i= 2
n= 4
d= 2
e= 6
p= 1
m= 1
t= 2
Cuantas letras hay?: 18
Entonces cual es la probabilidad con que aparece cada carácter?:
i= 2/18 = 0'1111
n= 4/18 = 0'2222
d= 2/18 = 0'1111
e= 6/18 = 0'3333
p= 1/18 = 0'0555
m= 1/18 = 0'0555
t= 2/18 = 0'1111
Cuánto suman las probabilidades?:
0'1111 + 0'2222 + 0'1111 + 0'3333 + 0'0555 + 0'0555 + 0'1111 = 0'9998

Otra cosa aparte es, si os piden cuantos bits se precisan para representar cada simbolo, pero asumo que eso en todo caso sería más adelante si tratais la compresión, aunque quizás paseis por encima de soslayo pues es parte de la teoria de la información, pero sin profundizar. La compresión no deja de ser un tema más profundo y no descarto que algún profesor esté tentado de hacer algún ejercicio simple, relativo a sencillos cálculos.


Relee las respuestas, está prácticamente todo ahí... decir o hacer más, ya supone hacer la tarea.


Releyendo tu mensaje incluso suena (quizás) un poco a pitorreo, puede parecer contradictorio,  quizás porque fue un copy/paste, o por lo menos se presta a 'diferentes' interpretaciones, cómo mínimo están desordenadas las ideas, o se ha manipulado inadecuadamente. Desde luego su redacción queda defectuosa tal como se presenta.

Crear una archivo de fuente de información
 Se pedirá el nombre de fichero por pantalla
 En el caso de que el archivo exista ya se mandará un mensaje de error
y no se hará nada.
Si el archivo no existe se creará de la siguiente
manera:
• Se pedirá el número de mensajes que tiene la fuente de
información
• Se pedirán las probabilidades de cada mensaje de una en una
hasta completar el fichero.
Al finalizar la toma de probabilidades, si la suma de las mismas no es
1 se mostrará un mensaje de error y se borrará el fichero.

Primero dice 'crear' un fichero, pero luego dice que si existe (será si existía uno del mismo nombre previo a crearlo), luego toca solicitar el nombre antes de crearlo.
Si ya existe, es lógico que se utilice (ese mismo) en vez de intentar crear otro, luego el mensaje de error procedente sería algo como: "El fichero ya existe, abriremos ese en vez de crear otro..." , por lo que esa frase de: "...no se hará nada", es de suponer que se refiere a "no se intentará crear otro si ya existe", y por tanto seguir adelante...

Pero luego la siguiente parte del enunciaod dice: "si no existe se creará de la siguiente manera...", que no se detalla (asumo que se puede haber retirado esa parte o que va en distinto orden).
Y al final lo que se espera que se haga con el fichero difiere solo de lo que solicitaba 'Lariscal...', en que en el caso de el/ella, solo se pedía para una determinada línea, y en tu caso se pide para cada línea del fichero, además vas contando las líneas que tiene el mismo porque también se exige.

La diferencia de detalles es tan nimia y simple que uno debiera ser capaz de hacer las ligeras modificaciones de código precisas.

... te ha debido de llevar un buen rato redactarla.

Sí... con las prisas (pues se avecinaba un texto largo), no lo revisé. He aprovechado ahora con más calma, para corregir sobretodo la ortografía (mi teclado suele comerse algunas letras, tengo que limpiarlo), y algún detalle menor o mejor redacción para que quede más claro, etc...


p.d.:

Olvidaba decirte, que en realidad si se puede hacerse el cálculo más abreviado para saber si el grafo es conexo o no, pero sólo en el caso de que sí lo sea, si no lo es, exigirá todo el recorrido igualmente.

Para ello, basta señalar como regla que cuando si pila alcance el número de nodos del grafo, entonces se demuestra que es conexo y puede salir y evitar el resto del recorrido (solo los numnodos de retornos).

Observa la diferencia en este recorrido:

Código [Seleccionar] Expandir


    nodo nodos []
    entero Pila[]
    entero cima, numnodos
    buleano nodirigido, Validado

    buleano = Inicializar(string grafo, string path)
        ...  // intenta establecer y validar el array nodos y crea la pila del tamaño numnodos
        validado = ....
        ...
        devolver validado
    fin funcion

    entero = funcion GrafoEsConexo(nodo n, entero numnodos, ...)
       buleano esconexo = FALSE

       si (validado = true)
            cima = 0
            si (nodirigido=TRUE)
                PilaPush(0)
                esconexo = RecorridoEsConexo(nodos[0] )
            sino  // si el grafo es dirigido, fuerza un recorrido desde cada nodo, para asegurarse.
                por cada nodo en nodos[]
                    PilaPush(k)
                    esconexo = RecorridoEsConexo(nodo)
                    PilaPop(k)
                    si (esconexo  = TRUE) salir del bucle                       
                    k +=1
                siguiente
            fin si
            PilaClear() // vaciar la pila.

            si (esconexo = TRUE)
                devolver 1     // es conexo
            sino
                devolver 0    // no es conexo
            fin si 
       sino
           devolver -1    // no se ha inicializado/validado el grafo.
       fin si
    fin funcion

// no necesitamos tirar del costo para calcular esto. La adyacencia los relaciona entre sí, por ese simple hecho.
buleano= funcion RecorridoEsConexo(nodo n)
    entero hijo  // indice absoluto en el array nodos[]
    buleano fin

    for cada hijo en n             
        si (PilaContiene(hijo) = false)
            PilaPush(hijo)                 
            fin = (cima< numnodos)             
            si (fin= FALSE)
                fin = RecorridoEsConexo(nodos[hijo] )
            fin si
            PilaPop(hijo)

            si (fin= TRUE)
                devolver TRUE  // sale de la función, es conexo
            fin si                 
        fin si
    siguiente

    devolver FALSE
fin funcion

El único modo de que la pila alcance el número de numnodos que tiene el grafo, es precisamente que sea conexo. Luego, tan pronto se alcance esa cantidad el recorrido puede finalizar. Si no es conexo, exigirá un recorrerlo completo.

La pila puese ser un objeto o un simple array y tener ahí mismo los métodos para su manejo, eso al gusto según acomode y el lenguaje elegido permite o facilita.

Se pueden ahcer muchos comentarios... permíteme extenderme, por que si no es casi preferible no decir nada.

- De entrada, como ejercicio está bien... la entrada de datos a petición uno por uno, pero lo ideal es que el programa acepte como entrada un string, que en sí mismo ya contenga todo el grafo y que tu programa lo desguace...
Digamos una función llamada SetDatos o Inicializacion que devuelva un buleano si el grafo está 'bien formado'. El string podría ser incluso la ruta de un fichero de texto, del que leer el grafo, incluso (es lo preferible) la misma función contener ambos parámetros, y ser procesada la primera entrada no nula entre ambos parámetros (es decir da preferencia al parámetro a la izquierda). Internamente el programa debiera mantener guardado los datos del grafo, así como si ha sido validado, para que una posterior llamada ('Procesar'), parta ya con la seguridad de que hay un grafo entrado y correcto merced a esa validacion. algo así...

Código [Seleccionar] Expandir


buleano Validado

buleano = Inicializar(string grafo, string path)
    si (grafo.length =0)
        si (path.length >0)
            grafo = LeerFile(Path)
        fin si
    fin si

    Si (grafo.length >0)
        validado = ValidarGrafo(grafo)
    sino
        validado = false
    fin si

    devolver validado
fin funcion

buleano = funcion Procesar(entero accion, otros parametros que fueren precisos)
   si (validado = TRUE)
        seleccion de accion
             accion = 1 ... invocar funcion1

             accion = x ... invocar funcionx
        fin seleccion
   sino
        mensaje "Actualmente no hay ningun grafo validado, debe ingresar uno antes de poder procesarlo..."
        devolver false
    fin si
fin funcion


- Como se ve al final del pseudocodigo previo, una vez que el grafo ha sido validado, se puede invocar ser procesado bajo diferentes peticiones, reflejado bajo el parámetro 'accion', una acción podría ser precisamente esa de '¿es un grafo conexo?'... en cuyo caso se invoca a la función que realiza esa averiguación.

- Desde un punto de vista puramente matemático, la matriz de adyacencia (no de 'adherencia') es muy útil, pero en un sistema informático, especialmente cuando un grafo vaya a ser grande o enorme, puede no ser muy útil del todo o un auténtico lastre.
Imagina un grafo de 100 nodos... 100x100 = 10.000 es decir tendrías que rellenar 10.000 casillas a mano, al estar hablando de un ejercicio donde tu mismo creas la entrada... y solo estamos hablando de 100 nodos... ¿qué, si fuera un grafo de 1.000 nodos (rellenarías una tabla de 1 millón de datos)?.
Ahondando más en el tema.... supongamos que el grafo ha de contener más propiedades que meramente a qué nodo está conectado (y veo que has usado un peso), pero pongamos que tienes más datos asociados que haya que procesar... cómo reflejarías en esa tabla cada uno de esos nuevos datos, más aún aunque no es complicado resolverlo dejando más espacio para rellenar datos, no aumentaría eso la cantidad de datos a rellenar aumentando el problema descrito en el párrafgo anterior?.

Hace alguna semanas, hice un grafo relacionado con sílabas... tenía aproximadamente (por pura casualidad) unos 100 nodos. Debe notarse como cada nodo solo referencia a los nodos a los que está conectado directamente, resulta absurdo rellenar las referencias de los nodos a los que no conecta. Se puede ver que aunque el listado todavía sea largo, es perfectamente asumible y además se puede guardar en un fichero, donde resultará cómodo de editar y guardar cambios.
Puedes mirar dicho ejemplo en el siguiente enlace:
https://foro.elhacker.net/hacking/diccionario_de_fuerza_bruta_tipo_v2-t510911.0.html;msg2253267#msg2253267
En el ejemplo presente en dicho enlace, se hace eco de una forma resumida, lo que acorta mucho más el texto redactado, si bien luego en memoria (al validar) debe expandirse.
Básicamente hice uso de algún tipo de macro, tal que ciertas apariciones repetitivas (y largas) se suplantan (en diseño), por una referecnia, y para reconocelro se trata como una 'directiva' (un nodo que debe tener un tratamiento especial previo).
En ejecución podría mantenerse también tal directiva, como un nodo de acceso, pero con cada nodo visitado, exigiría una comprobación de si es o no una directiva y entonces sería más lento... luego, uno debiera decidir si prima el ahorro de memoria o la velocidad de cálculo, y en base a ello decidir si expandir (cada caso) al validar o (solo el caso presente) al calcular a medida que aparecen...
Aún así, hay casos donde usar una forma canónica (la tabla de adyacencia), es deseable. Cada uno acertadamente debe comprender cuando se da tal caso.


- Lógicamente debes establecer un formato, una notación que seguir, y que tu función 'ValidarGrafo' debe interpretar y ser capaz de construir un array de un tipo de estructura (a partir del texto redactado en dicho formato).
Es esa estructura la que debe contener los diversos campos (propiedades), que cada nodo debe retener, así la complejidad de los datos, no se ve asfixiada por la entrada de datos que se intenta reflejar en una tabla cuadrada, que o se introduce manuamente uno a uno cada dato o un enorme fichero del que la mayor parte (probablemente) sean datos desechables, para los que ni siquiera haga falta guardarlos en parte alguna (cuando el programa tenga que operar).

- Por supuesto, como primera aproximación a la programación de grafos es más que adecuado empezar con una matriz de adyacencia, sobretodo para tomar confianza.
Nota al respecto que en cualquier caso, la iteración explora los nodos accesibles a uno dado (hijos, los directamente conectados) , y el acceso a un nodo (para luego recorrer sus 'hijos') obliga a la recursión. Son los bucles imprescindibles para recorrer un grafo. Y hay que notar que ni siquiera se necesita generar en memoria un grafo o un árbol, el recorrido lo va haciendo sobre la marcha, por ello la cantidad de memoria conumida mientras se ejecuta suele ser mínima, independientemente del tamaño del grafo.

- Tampoco resulta muy útil, más allá del ejercicio que supone, determinar si un grafo es conexo.
Aunque matemáticamente un grafo admite varias ramas, un grafo debe considerarse como un array de ramas, siendo cada rama, ni más ni menos que un grafo (el nombre de 'rama' solo tiene aquí un propósito diferenciador de la ubicación de una raíz existente pero no yacente)...
Por ejemplo, en tu grafo ese de la primera imagen (abajo a la izquierda), tienes un grafo no conexo... pero a nivel informático, no es aceptable tener un grafo a cuyas ramas no son accesibles. En determinados diseños eso equivale a decir que son datos erróneos o bien superfluos (y que por tanto pueden eliminarse)... pero a menudo lo que sucede es que falta una conexión de nivel mayor que no está presente, pero que sensiblemente existe.... luego ese grafo debería formatearse bajo un nuevo nodo que accede a sendos subgrafos.
Tienes por un lado la rama: 0-1-2-3-4-5 y por otro la rama 6-7, puede verse el conjunto como formado un nodo raíz llamado 8 que conecta a ambas ramas.
Técnicamente al hacer esto, debe asumirse la responsabilidad de decidir como se conectan al nodo 8, cada rama... solo a un nodo o a cada nodo de dicha rama?. La respuesta debe ser arrojada según el contexto del problema, pero tratándose de un ejercicio cualquier valor aleatorio puede valer.

- Por lo mismo, usar números como identificador de cada nodo, una vez más matemáticamente puede ser cómodo, pero de cara a una representación humana más comprensible es preferible asignarles un string... aunque solo sea una letra...
A-B-C-D-E... y mejor si son nombres largos cuando son ejemplos. Mientras desarrollas y pruebas el programa será más fácil no confundir nombres irrelevantes, como "1" o "J", usando por ejemplo Leon-Bilbao-Cadiz-Granada-Madrid, resultan más útil en dicho punto.
Lógicamente cuando el grafo es validado, será un índice en el array el que lo referencie, y puede optarse por dejar el nombre 'original' en la estructura asociada a cada nodo, más que nada por que la salida de datos, a menudo es conveniente devolver justamente esos nombres (que son más relevantes y nos aportan una información menos abstracta) que meramente su índice. El indice para procesado, y el nombre para el tratamiento humano (visualizar, comprobar).

Así por ejemplo, el grafo ese que refiero (de la primera imagen, abajo a la izquierda), yo lo describiría así:

Código [Seleccionar] Expandir


// nota: al poner 'conectado a' debe entenderse 'directamente conectado a'

R = A|G      //un nodo raíz 8, no presente conecta a cada rama del grafo (por no estar conectadas). Aquí se asume que conecta a los nodos 0 y 6 solamente.
A = B|F    // el nodo 0 solo está conectado a los nodos 1 y 5.
B= A|C|F  // el nodo 1 está conectado a los nodos 0, 2 y 5.
C= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5.
D= C|E|F  // el nodo 3 está conectado a los nodos 3,5 y 5.
E= D|F  // el nodo 5 está conectado a los nodos 4 y 5
F= A|B|C|D|E  // el nodo 5 está conectado al resto de nodos (de esta rama).

G= H  // el nodo 6 está conectado al nodo 7
H= G  // el nodo 7 está conectado al nodo 6

Como se puede ver (sin los comentarios), esto es mucho más breve que una matriz de adyacencia y describe exactamente el mismo grafo (he omitido el peso entre los nodos, para una primera aproximación a esta notación).

Nota además como el grado siendo no dirigido (originalmente), al ser un grafo con dos ramas no conexas, lo hemos convertido en un grafo dirigido, tal que desde una rama no es posible regresar a la raíz y seguir por la otra rama, pero en cambio cada rama supone (sigue siendo) un grafo no dirigido. Así este esquema cumple y completa la idea perseguida de grafo no conexo. Cuando se acceda a la primera rama, no conecta con la segunda y vicerversa. Siguen siendo ramas aisladas, pero ahora si forman un grafo 'tratable' (sus datos son accesbiles desde una raíz que puede ser tratado en bucle si se precisa desde la función principal que deriva a la de recorrido).

No es obligatorio que cada rama deba ser un grafo no dirigido.
...por ejemplo si desde A se llega a B pero desde B no se llegare a A, entonces:

Código [Seleccionar] Expandir


A = B|F
B= C|F

Comparando con lo anterior se ve que ahora desde B no se puede acceder a A...

Igualmente estableciendo pesos, en la notación, podría ser expresado así:

Código [Seleccionar] Expandir


A = B:3|F:5
B= A:3|C:2|F:4
C= B:2|D:8|F:6
D= C:8|E:1|F:3
E= D:1|F:4 
F= A:5|B:4|C:6|D:3|E:4

De un nodoX a otro nodoY hay el mismo peso que del nodoY al nodoX.

...pero no tiene porqué ser el mismo peso de A a B que de B a A (aunque suele ser lo habitual, no es exigible que lo sea)... ejemplo:

Código [Seleccionar] Expandir


A = B:3|F:5
B= A:7|C:2|F:4
C= B:2|D:8|F:6
D= C:5|E:1|F:3
E= D:4|F:4 
F= A:7|B:3|C:5|D:3|E:4




Y ahora veré de responder a tus preguntas:

- He considerado que un nodo no puede estar conectado consigo mismo; para saber si los nodos están conectados entre sí no hace falta, y estorba para el algoritmo.

Para este preciso propósito (conocer si un grafo es o no conexo) no.

A veces es preciso en un grafo señalar una forma en la que un nodo se atraviese a sí mismo un número determinado de veces, por ejemplo 2... en ese caso, es preferible añadir un nodo nuevo conectado igual que él, pero nombrado de forma distinta (como si fuera un nodo más).
Dentro de esta casuística puede suceder que está segunda aparición deba tener ciertas restricciones o reglas.
Por ejemplo podría estar conectado siempre junto a sí mismo como hace el nodo C en: A-B-C-C'-D-E.
En ese (hipotético) caso, se rediseña:
--- Los que conecten a C siguen conectados a C como antes.
--- El nuevo nodo creado (que por facilidad de reconocimeinto he bautizado como C' ), se conecta al resto de nodos como lo hacia C.
--- Pero C se conecta solo a C'.
--- Y C' podría o no, conectarse también a C si hubiera necesidad de señalar pesos distintos en la forma C-C' de C'-C. Es habitual que si un nodo es 'clonado' se otro (y siempre le precede-postcede), asuma un peso de 0.
Un ejemplo asumiendo en ese grafo tuyo que he tomado de ejemplo este caso, quedaría así (ahora sí, a la copia del nodo C' le ha acuñado un nombre específico Z):

A = B|F   
B= A|C|F 
C= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5. Este se desmontan en las dos siguientes reglas-nodos:
C= Z  //El nodo 2 se conecta así mismo, siempre, antes de conectarse a otros. Los otros conectan a C, y solo este a Z.
Z= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5.
D= C|E|F 
E= D|F 
F= A|B|C|D|E 

También he considerado solamente grafos en los cuáles los nodos están conectados en ambas direcciones: si se puede ir desde a hacia b, entonces también se puede ir desde b hacia a. (Creo que existen grafos en los cuáles puede haber trayectorias en un sentido pero no en el contrario).

Esto te lo he respondido más arriba, pero resumo con un simple ejemplo:

Código [Seleccionar] Expandir


A= B|C|D
B= A|C
C=
D= B|C

En este ejemplo, puede verse como A conecta a B,C y D, pero solo B conecta a A. B y D conectan a C, pero C no conecta a ninguno. Puede verse fácilmente que no hay 'reciprocidad' en la conexión, no es exigible, pero es algo que dependerá siempre del contexto dle problema.
Por ejemplo en español tenemos: 'artículo->nombre', pero no: 'nombre->artículo'  (artículo<->nombre), así decimos: "El perro", y nunca: "Perro el", pero en cambio 'nombre->adjetivo' si admite 'adjetivo->nombre', como en: "El perro rabioso", "El rabioso perro".

- El peso de la conexión únicamente es útil para saber si dos nodos están conectados...

No. De hecho ni siquiera en tu ejemplo debiera basarse en ello. En tu ejemplo la conexión viene establecida por la matriz de adyacencia.
Perfectamente podría haber una conexión con peso 0.
El peso en realidad es (debe verse como) un valor abstracto, pero que por ejemplificar se tipifica con el significado de su nombre: peso, distancia, costo... es más fácil basar ejemplos en un valor que además de medible, es fácilmente identificable como la distancia entre dos nodos, para una mejor asimilación en su comprensión.

Sirven también para dirigir búsquedas, ya que puede haber reglas que imponen:
1 - buscar las rutas cuya suma en costo no superen x valor.
2 - buscar todas las rutas cuyo costo total sea exactamente x valor.
3 - buscar la/s ruta/s cuyo costo sea la menor (el plurar es porque a priori no puede descartarse que haya más de una ruta que siendo de costo menor sea igual a otra ruta distinta con igual costo).
4 - buscar todas las ruta que ... que se encuentre un nodo final. Aquí el costo no es un limitante solo un valor de resultado.
5 - buscar todas als rutas de x cantidad de nodos.
Incluso es normal (lo habitual) que las reglas de búsqueda reúnan más de 1 condición.

- ¿Alguna idea para corregir el bucle de la línea 96 y que no empiece desde cero?

Ya comentaba al principio, que lo ideal es una función de preprocesado que valide el grafo completamente.
Esa validación suele exigir 2 bucles (incluso 3 si el número de líneas no coincide con el número de nodos, loque es conveniente, para no tener un formato muy estricto, es habitual añadir líneas en blanco por claridad en la edición).
Si hay 3 bucles, el primero filtra las líneas que no parecen describir los nodos y los cuenta.
Luego se crea el array (vacío) de la cantidad de nodos que parecen existir.
A continuación un bucle donde verifican los nodos raíz (la parte izquierda, que otorga el nombre del nodo) y contabiliza (y guarda) cuantos hijos tiene cada nodo (examinando la parte derecha de la linea de texto).
Si no tiene hijos se queda en 0 (o si conviene con num_hijos= -1). Como hay referencias sin resolver (como sucede con los compiladores), esto es, se nombra un hijo que todavía no ha sido añadido en el array, es preciso un segundo bucle, donde ahora ya se trata de referenciar cada nodo hijo (para cada nodo del grafo) con el indice que ocupa en el array.
Ahora ya tu bucle ahí no sería:

Código [Seleccionar] Expandir

for (j = 0; j < num_nodos; j++)[/node]
Sino:
[code]
for (j = 1; j < nodo.num_hijos; j++)
Así salta por encima de los nodos que no tengan hijos (nodos terminales).
En ese punto, también hay algo que decir, a veces la condición de búsqueda exige el caso 4 de la pregunta previa... es decir un nodo sin hijos (num_hijos = 0) se considera un nodo terminal.
En realidad deben satisfacerse varios algoritmos de recorrdo cada uno basado en un criterio de búsqueda generalmente mixto, es decir hay varios condicionantes, no uno solo.

¿Se mejoraría la eficiencia del programa usando una pila en lugar del arreglo y la posición?

El array contiene los datos de entrada, la pila debe contener los nodos activos en el recorrido presente. Son cosas distintas.

Código [Seleccionar] Expandir


estructura DatosHijo
   entero index
   entero costo
fin estructura

funcion procesa_grafo(nodo n, ...)
    DatosHijo hijo
    entero index

    por cada hijo en n
        index = hijo.index  //se trata de una estructura, index refiere a la posición de dicho nodo en el array.

        Si pila.Contiene(index) = false
            pila.push(index) // <--------------------
            ...
            Si cumple condiciones de búsqueda
                ...
                imprimir pila.tostring
            si no
                ...
                procesa_grafo(arrayNodos(hijo), ...)
            fin si
            pila.pop(index) //<------------------
        fin si
    siguiente
    ...
fin funcion

buleano = funcion Contiene(entero index)
   devolver arrayNodos(index).Apilado
fin si

funcion Push(entero index)
    arraynodos(index).Apilado = true
   
    pila(cima) = index
    cima +=1
fin funcion

funcion Pop(entero index)
   arraynodos(index).Apilado = FALSE
   cima -=1
fin funcion

string= funcion ToString
    entero j, k, n
    string s

    bucle para k desde 0 a cima-1
        n += arrayNodos(pila(k)).nombre.length
    siguiente

    s = espacios(n)
    n= 0
    bucle para k desde 0 a cima-1
        j = arrayNodos(pila(k)).nombre.length
        s.insert(n, j, arrayNodos(pila(k)).nombre)
        n += j
    siguiente

    devolver s
fin funcion


Y lo principal: ¿existiría otro tipo de algoritmo que no fuera recorrer todos los caminos posibles?

Depende del contexto.
- Un grafo puede ser resumido a menudo para procesar menos nodos de los debidos si se dan determinadas condiciones
- También puede ser acortado si se exigen ciertas condiciones-reglas de búsqueda.

En el ejemplo que te daba en el enlace de más arriba, pese a que tiene 100 nodos, se recorren:

Número de nodos: 101
Total de caminos: 408694
Total de Salidas: 405294

El número de 'caminos' son los nodos visitados, las 'salidas' son las búsquedas halladas, como se ve, el número de nodos visitados 'extras' es muy reducido y se explica allí a que se debe.

Un ejemplo de resumen:
En el siguiente hilo,
https://foro.elhacker.net/programacion_cc/proyecto_de_estructura_de_datos_grafos_c-t484196.0.html;msg2163932#msg2163932
el grafo que dibuja el interesado (ver el primer mensaje), para los nodos B,D y H, se crea un nuevo nodo (no presente pero que los representa), nodo E. Éste hace las veces de los 3, porque los 3 están en línea, es decir

Código [Seleccionar] Expandir


C= A|B|L
B= D
D= H
H= F
F= A|C|H
Cada uno de esos nodos tiene como entrada el previo y como salida el siguiente, sin más conexiones, luego pueden resumirse como uno solo a efectos de recorrido, el nombre para el nodo E (para su impresión), podría asumir el valor concatenado de ellos, si bien como la dirección puede variar (BDH, o HDB), es preferible representarlo como 'E', y ya en la impresión saber que se leen en uno u otro sentido según el nodo previo (C ó F).
Ese grafo está condicionado solo por la búsqueda de un nodo terminal. Te vendría bien como ejercicio.

Un ejemplo de acortamiento por recorrido:

Código [Seleccionar] Expandir


    ...
    Si pila.Contiene(index) = false
        costoTotal += hijo.costo
        Si (costoTotal < CostoMaximo)
            pila.push(index)
            ... // entre otras cosas el recorrido recursivo
            pila.pop(index)
        fin si
    fin si
    ....

Como se ve en el ejemplo, si hay una condición de búsqueda, y con la suma del nodo se supera el costo máximo admitido, es claro que añadir al recorrido los hijos que este nodo tenga, no hará si no crecer el costo (asumiendo que no hay costos negativos, que no suele ser frecuente), luego todos los hijos que deriven de éste pueden ser omitidos...
En el siguiente enlace:
https://foro.elhacker.net/programacion_general/problema_del_viajante_de_comercio_branch_and_bound-t510012.0.html
...se puede ver comentado casos de este tipo, si bien interesaba al principio hacer un recorrido total (fuerza bruta ciega), solo por conocer los tiempos de cálculo.
Más al final (averiguado ya el tiempo y la exactitud de la solución) se abordó soluciones tirando justamente de esas reglas de recorrido, que además se actualizaba con cada hallazgo que mejoraba el previo (es decir el costo, al incio toma el valor de infinito, en realidad el valor máximo qe admite el tipo de datos numérico usado, que se va sustituyendo por cada costo menos que el previo):

Código [Seleccionar] Expandir


...
costoTotal += .costo
Si (costoTotal < CostoMaximo)
    costoMaximo = costoTotal
    pila.Tostring
sino
    pila.push(index)
    ... // entre otras cosas el recorrido recursivo
    pila.pop(index)
fin si
...

... para reducir la cantidad de nodos visitados al máximo... Incluso reordenando a la entrada (en el preprocesado), los hijos de cada nodo por su costo.

Ahora bien, para el caso de conocer si el grafo es conexo, no queda margen, pués la respuesta solicitada es sí/no.
No obstante salvo como ejercicio o que sean datos que te pasan... en resumen si los datos los provees tú mismo, ya sabes de entrada si el grafo es conexo, al momento de ir generando el grafo, luego puede ser superfluo.

Por último: ¿alguna manera de programar más elegante (o eficaz) sin usar una función recursiva. Tengo entendido que ... la recursividad no son muy bienvenidas por los programadores

Solo desde la ignorancia puede hacerse tal afirmación.

La iteración debe usarse donde es precisa, en vez de la recursión y la recursión debe usarse donde es precisa en vez de la iteración. Forzar el uso de un tipo de bucle cuando debe usarse el otro es cuando resulta ineficiente.

Éste es el caso propicio donde la recursión tiene cabida: grafos (un árbol no deja de ser un grafo).
Sabido es que la recursividad puede ser reconvertida en iteratividad, si bien en este caso, supone que entonces tu mismo debes acometer todo el trabajo de salvaguarda de datos en cada iteración que en su caso es cedido a los mecanismos de recursión que tiran de la pila del programa. Luego al final, solo añades código que enturbia o complica el algoritmo subyacente y no queda claro que vayas a ganar eficiencia toda vez que los mecanismo de recursión están muy optimizados.[/code]

mmmm esto me suena a spam, ya en otro tema también vi esa misma página.

A mi a lo que me suena es a alguien que quiere realizar coleccionar citas para luego 'venderlas'...  Para localizar una sola cita, no hace falta ningún script, solo llamar por tf. una o varias veces, o acercarse (físicamente) a la oficina más próxima en sus horarios y reclamarla.

En cualquier caso, como es un sistema gubernamental y además muy específico (¿Cubano, mejicano?), a quien debiera pedir ayuda sobre el asunto es al propio gobierno (las sección/ministerio que corresponda), que es quien ha diseñado el sistema y habrá interpesto las trabas o exigencias específicas precisas o en su defecto a un foro específico sobre temas legales/técnicos (sobre el gobienro) del país correspondiente.

Lo estaba desmontando y ha salido humo tengo miedo que puede ser? Y si es la batería va a explotar?

Esto solo es posible que suceda en una situación:

Tenías el PC conectado a la red electrica o con batería, cuando te has puesto a desmontarlo. ...porque si está apagado (frío) y desconectado de la red electrica y baterías (que es como debe hacerse) es imposible que se provoque ningún humo de ninguna manera.

No estoy seguro que se pueda programar nada así.
El apagado sí, no tiene dudas, pero el encendido no, porque algo tiene que 'estar vigilante' para que llegado el momento lo prenda.

Como bien dices, desde el BIOS, con la opción WoL (WakeOnLAN), pero es para encendido remoto. Digo yo que entonces el script deseado puede yacer en otro equipo remoto que se encargue de 'llamar' al susodicho, cuando este previamente s ehaya activado la opción en la BIOS.

Localmente no... porque es absurdo.
- Si estás en casa, nada te impide prenderlo tú mismo exactamente cuando lo necesitas. Establecer horarios en ese sentido es absurdo, porque puede que se enciencia 1 hora antes de que llegues a casa (si te retrasas) o que tengas que 'esperar' (porque llegaste una hora antes a casa). El punto óptimo es: 'cuando lo necesitas', algo que ya se cumple.
- Y si no estás en casa puedes tirar de WoL...


Si no te vale el sistema, cabe preguntarse si tu intencionalidad apunta hacia algo vírico, que es cuando en efecto, ni estás en casa, ni de modo remoto puedes configurarlo porque no tienes acceso físico al BIOS... pero sigue uno queriendo manejar un horario de encendido y apagado (por ejemplo cuando se sabe que el dueño no está en casa (por ejemplo, porque está trabajando) que se encienda).

...y que es lo que tienes hecho hasta el momento?.

El título debe reflejar el problema que hay que resolver no 'tu problema'.

Además, para prguntar sobre Python hay otro foro mejor que éste (se supone que los pythoadictos lo visitarán más que aquí)...

Tienes que ir a las propiedades de la pantalla, en 'power', pestaña 'avanzado' o similar...
habrá una opción para activar y desactivar relacionado con 'standby':
'Preguntar contraseña cuando sale de standby' o similar.