Algoritmos de grafos

Introdução à Análise de Redes em Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Encontrando caminhos

  • Encontrar caminhos é importante para
    • Otimização: ex. rotas de transporte mais curtas
    • Modelagem: ex. contágio de doenças, difusão de informação
  • Algoritmo: Busca em largura (BFS)
Introdução à Análise de Redes em Python

Busca em largura (BFS)

  • Exemplo: menor caminho entre dois nós

Um grafo com uma dúzia de nós. Dois nós indiretamente conectados estão destacados.

Introdução à Análise de Redes em Python

Busca em largura (BFS)

  • Exemplo: menor caminho entre dois nós

O mesmo grafo de antes, mas o nó vizinho de um dos nós destacados também está destacado.

Introdução à Análise de Redes em Python

Busca em largura (BFS)

  • Exemplo: menor caminho entre dois nós

O mesmo grafo de antes, mas os nós vizinhos de todos os nós destacados também estão destacados.

Introdução à Análise de Redes em Python

Busca em largura (BFS)

  • Exemplo: menor caminho entre dois nós

O mesmo grafo de antes, mas outro conjunto de nós vizinhos dos nós já destacados também está destacado, o que significa que o nó alvo foi alcançado.

Introdução à Análise de Redes em Python

Relembrando: Vizinhos

G

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

len(G.edges())

57

len(G.nodes())

20
Introdução à Análise de Redes em Python

Relembrando: Vizinhos

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Introdução à Análise de Redes em Python

Vamos praticar!

Introdução à Análise de Redes em Python

Preparing Video For Download...