Grafové algoritmy

Úvod do analýzy sítí v Pythonu

Eric Ma

Data Carpentry instructor and author of nxviz package

Hledání cest

  • Hledání cest je důležité pro
    • Optimalizaci: např. nejkratší trasy
    • Modelování: např. šíření nemocí, předávání informací
  • Algoritmus: Prohledávání do šířky
Úvod do analýzy sítí v Pythonu

Prohledávání do šířky (BFS)

  • Příklad: Nejkratší cesta mezi dvěma uzly

Graf s několika uzly. Dva nepřímo propojené uzly jsou zvýrazněny.

Úvod do analýzy sítí v Pythonu

Prohledávání do šířky (BFS)

  • Příklad: Nejkratší cesta mezi dvěma uzly

Stejný graf, ale sousední uzel jednoho ze zvýrazněných uzlů je také zvýrazněn.

Úvod do analýzy sítí v Pythonu

Prohledávání do šířky (BFS)

  • Příklad: Nejkratší cesta mezi dvěma uzly

Stejný graf, ale sousední uzly všech zvýrazněných uzlů jsou také zvýrazněny.

Úvod do analýzy sítí v Pythonu

Prohledávání do šířky (BFS)

  • Příklad: Nejkratší cesta mezi dvěma uzly

Stejný graf, ale další sousední uzly jsou zvýrazněny, takže byl dosažen cílový uzel.

Úvod do analýzy sítí v Pythonu

Připomenutí: Sousedé

G

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

len(G.edges())

57

len(G.nodes())

20
Úvod do analýzy sítí v Pythonu

Připomenutí: Sousedé

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Úvod do analýzy sítí v Pythonu

Lass uns üben!

Úvod do analýzy sítí v Pythonu

Preparing Video For Download...