Algoritmi pe grafuri

Introducere în analiza rețelelor în Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Găsirea căilor

  • Găsirea căilor este importantă pentru
    • Optimizare: ex. cele mai scurte rute de transport
    • Modelare: ex. răspândirea bolilor, transmiterea informațiilor
  • Algoritm: Căutarea în lățime
Introducere în analiza rețelelor în Python

Căutarea în lățime (BFS)

  • Exemplu: Cel mai scurt drum între două noduri

Un graf cu câteva noduri. Două noduri conectate indirect sunt evidențiate.

Introducere în analiza rețelelor în Python

Căutarea în lățime (BFS)

  • Exemplu: Cel mai scurt drum între două noduri

Același graf, dar nodul vecin unuia dintre nodurile evidențiate este și el evidențiat.

Introducere în analiza rețelelor în Python

Căutarea în lățime (BFS)

  • Exemplu: Cel mai scurt drum între două noduri

Același graf, dar nodurile vecine tuturor nodurilor evidențiate sunt și ele evidențiate.

Introducere în analiza rețelelor în Python

Căutarea în lățime (BFS)

  • Exemplu: Cel mai scurt drum între două noduri

Același graf, dar un alt set de noduri vecine este evidențiat, ceea ce înseamnă că nodul țintă a fost atins.

Introducere în analiza rețelelor în Python

Recapitulare: Vecini

G

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

len(G.edges())

57

len(G.nodes())

20
Introducere în analiza rețelelor în Python

Recapitulare: Vecini

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introducere în analiza rețelelor în Python

Să exersăm!

Introducere în analiza rețelelor în Python

Preparing Video For Download...