Thuật toán đồ thị

Nhập môn Phân tích Mạng bằng Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Tìm đường đi

  • Tìm đường quan trọng cho
    • Tối ưu hóa: ví dụ đường vận chuyển ngắn nhất
    • Mô hình hóa: ví dụ lan truyền dịch bệnh, truyền thông tin
  • Thuật toán: Duyệt theo chiều rộng (BFS)
Nhập môn Phân tích Mạng bằng Python

Duyệt theo chiều rộng (BFS)

  • Ví dụ: Đường đi ngắn nhất giữa hai nút

Một đồ thị với khoảng chục nút. Hai nút kết nối gián tiếp được làm nổi bật.

Nhập môn Phân tích Mạng bằng Python

Duyệt theo chiều rộng (BFS)

  • Ví dụ: Đường đi ngắn nhất giữa hai nút

Cùng đồ thị như trước, nhưng một nút kề của một nút được làm nổi bật cũng được làm nổi bật.

Nhập môn Phân tích Mạng bằng Python

Duyệt theo chiều rộng (BFS)

  • Ví dụ: Đường đi ngắn nhất giữa hai nút

Cùng đồ thị như trước, nhưng các nút kề của mọi nút được làm nổi bật cũng được làm nổi bật.

Nhập môn Phân tích Mạng bằng Python

Duyệt theo chiều rộng (BFS)

  • Ví dụ: Đường đi ngắn nhất giữa hai nút

Cùng đồ thị như trước, nhưng thêm một lớp nút kề của các nút hiện đang được làm nổi bật cũng được làm nổi bật, và nút đích đã được đạt tới.

Nhập môn Phân tích Mạng bằng Python

Ôn lại: Láng giềng

G

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

len(G.edges())

57

len(G.nodes())

20
Nhập môn Phân tích Mạng bằng Python

Ôn lại: Láng giềng

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Nhập môn Phân tích Mạng bằng Python

Ayo berlatih!

Nhập môn Phân tích Mạng bằng Python

Preparing Video For Download...