Algoritmi sui grafi

Introduzione all'analisi delle reti in Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Trovare percorsi

  • Il pathfinding è utile per
    • Ottimizzazione: es. percorsi di trasporto più brevi
    • Modellazione: es. diffusione di malattie, passaggio di informazioni
  • Algoritmo: visita in ampiezza (BFS)
Introduzione all'analisi delle reti in Python

Visita in ampiezza (BFS)

  • Esempio: percorso più breve tra due nodi

Un grafo con una dozzina di nodi. Due nodi collegati indirettamente sono evidenziati.

Introduzione all'analisi delle reti in Python

Visita in ampiezza (BFS)

  • Esempio: percorso più breve tra due nodi

Lo stesso grafo di prima, ma è evidenziato anche il nodo vicino a uno dei nodi evidenziati.

Introduzione all'analisi delle reti in Python

Visita in ampiezza (BFS)

  • Esempio: percorso più breve tra due nodi

Lo stesso grafo di prima, ma sono evidenziati anche i nodi vicini a tutti i nodi evidenziati.

Introduzione all'analisi delle reti in Python

Visita in ampiezza (BFS)

  • Esempio: percorso più breve tra due nodi

Lo stesso grafo di prima, ma è evidenziato un altro insieme di nodi vicini a quelli già evidenziati, quindi si è raggiunto il nodo di destinazione.

Introduzione all'analisi delle reti in Python

Ripasso: Vicini

G

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

57

len(G.nodes())

20
Introduzione all'analisi delle reti in Python

Ripasso: Vicini

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introduzione all'analisi delle reti in Python

Let's practice!

Introduzione all'analisi delle reti in Python

Preparing Video For Download...