Forum >> Principianti >> GRAFI

Pagina: 1

Buon giorno, mi sono trovato di fronte a degli esercizi con i grafi. Cosa è un grafo l'ho capito, ma vedendo l'esercizio svolto, non sono riuscito ad analizzarne il funzionamento, non riesco a capire per quale motivo lavora in quel modo.

''' 
Completare la funzione admat(g, v) che preso
in ingresso un dizionario g rappresentante la topologia di un grafo e un secondo dizionario v che
rappresenta il vettore dei nodi, restituisca la matrice di adiacenza del grafo, rappresentata come
lista di liste. In particolare, la generica chiave di v è l’etichetta di un nodo, mentre il valore è
un intero che identifica la riga (e anche la colonna) della matrice di adiacenza associata al grafo.
Ad esempio, il valore di g per il grafo in Figura 1 è (a parte l’ordine in cui compaiono le chiavi):
{’1’: [’2’, ’4’], ’2’: [’3’], ’4’: [’2’, ’3’]}. Qualora il valore di v fosse (di nuovo a
parte l’ordine delle chiavi) {’1’: 2, ’2’: 0, ’3’: 1, ’4’: 3}, allora la funzione dovrebbe
restituire la matrice [0, 1, 0, 0], [0, 0, 0, 0], [1, 0, 0, 1], [1, 1, 0, 0]. '''


def admat(g, v):

    mat = []
    for i in range(len(v)):
        l = []
        for j in range(len(v)):
            l.append(0)
        mat.append(l)

# Ha creato una matrice quadrata di lunghezza pari alla lunghezza di v

    for elem in v:  # chiave in v che è l'etichetta di un nodo

        if elem in g:
            i = velem  # Trovo la riga corrispondente al nodo elem
            l = gelem  # Lista di adiacenza di elem

            for nodo in l:

                j = vnodo  # Trovo la riga/colonna corrispondente a nodo
                matj = 1
    return mat



def main():

    g = {'1': ['2', '4'], '2': ['3'], '4': ['2', '3']}
    v = {'1': 2, '2': 0, '3': 1, '4': 3}
    out = admat(g, v)
    print(out)


main()



Poichè il grafo è g = (V, E) se i dati sono g e V non dovrei determinare E?

In ogni caso, la matrice di adiacenza di questo grafo è la seguente:


       1   2   3   4

1     0   1   0   1

2     0   0   1   0

3     0   0   0   0

4     0   1   1   0



quindi non capisco dato v come possa dare come risultato la lista di liste data nel testo.

Più che il programma non ho capito il ragionamento fatto, spero in qualcuno che mi possa aiutare.

Grazie!




--- Ultima modifica di michele3696 in data 2016-08-30 11:23:57 ---
Ciao,
ho praticamente il tuo stesso identico problema, non ho capito come funziona questo esercizio. :confused:
Sei riuscito a capire alla fine?


Pagina: 1



Esegui il login per scrivere una risposta.