อัลกอริทึมกราฟ

การวิเคราะห์เครือข่ายเบื้องต้นด้วย Python

Eric Ma

Data Carpentry instructor and author of nxviz package

การค้นหาเส้นทาง

การค้นหาเส้นทางมีความสำคัญในด้านต่าง ๆ
- การหาค่าเหมาะที่สุด: เช่น เส้นทางขนส่งที่สั้นที่สุด
- การสร้างแบบจำลอง: เช่น การแพร่กระจายของโรค การส่งต่อข้อมูล
อัลกอริทึม: การค้นหาแบบ Breadth-first search

กราฟที่มีโหนดหลายโหนด โดยมีสองโหนดที่เชื่อมต่อกันทางอ้อมถูกไฮไลต์ไว้

กราฟเดิม แต่โหนดเพื่อนบ้านของโหนดที่ถูกไฮไลต์โหนดหนึ่งถูกไฮไลต์เพิ่มด้วย

กราฟเดิม แต่โหนดเพื่อนบ้านของโหนดที่ถูกไฮไลต์ทั้งหมดถูกไฮไลต์เพิ่มด้วย

กราฟเดิม แต่มีโหนดเพื่อนบ้านชุดถัดไปถูกไฮไลต์เพิ่ม ซึ่งหมายความว่าถึงโหนดเป้าหมายแล้ว

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

len(G.edges())

len(G.nodes())

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]

การวิเคราะห์เครือข่ายเบื้องต้นด้วย Python