ต้นไม้และกราฟ

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

ต้นไม้ - ความหมาย

ภาพต้นไม้ที่มีโหนด

โครงสร้างข้อมูลแบบ โหนด
แต่ละโหนดมี ลิงก์ ไปยังโหนดอื่นได้มากกว่าหนึ่งโหนด

ต้นไม้ - คำศัพท์

ภาพต้นไม้ที่มีโหนด โดยโหนดรากถูกระบายสีเหลือง

ต้นไม้ - คำศัพท์

ภาพต้นไม้ที่มีโหนด โดยโหนดรากถูกระบายสีเหลืองและโหนดพ่อแม่ถูกระบายสีส้ม

ต้นไม้ - คำศัพท์

ภาพต้นไม้ที่มีโหนด โดยโหนดรากถูกระบายสีเหลือง โหนดพ่อแม่ถูกระบายสีส้ม และโหนดลูกถูกระบายสีเขียว

ต้นไม้ - คำศัพท์

ภาพต้นไม้ที่มีโหนด

ต้นไม้ - คำศัพท์

ภาพต้นไม้ที่มีโหนดพร้อมระดับชั้นต่าง ๆ

ต้นไม้ - ต้นไม้ไบนารี

ภาพแสดงต้นไม้ไบนารี

แต่ละโหนดมีได้:
- ไม่มีโหนดลูก
- หนึ่งโหนดลูก
- สองโหนดลูก

ต้นไม้ - การสร้างต้นไม้ไบนารี

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

ภาพต้นไม้ที่มีโหนด

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

ต้นไม้ - การใช้งานจริง

การเก็บความสัมพันธ์เชิงลำดับชั้น
- ระบบไฟล์ของคอมพิวเตอร์
- โครงสร้างของเอกสาร HTML
หมากรุก: เส้นทางที่คู่ต่อสู้อาจเดิน
อัลกอริทึมการค้นหาและเรียงลำดับ

กราฟ

ภาพกราฟที่มีโหนด

ประกอบด้วย:
- โหนด/เวอร์เทกซ์
- ลิงก์/เอดจ์
ต้นไม้เป็นกราฟประเภทหนึ่ง

กราฟ - ประเภท

กราฟมีทิศทาง:
- มีทิศทางที่กำหนด

ภาพกราฟมีทิศทาง

กราฟ - ประเภท

กราฟไม่มีทิศทาง:
- เอดจ์ไม่มีทิศทาง
- ความสัมพันธ์เป็นแบบสองทาง

ภาพกราฟไม่มีทิศทาง

กราฟ - ประเภท

กราฟถ่วงน้ำหนัก:
- กำหนดค่าตัวเลขให้กับเอดจ์
- มีได้ทั้งแบบมีทิศทางและไม่มีทิศทาง

ภาพกราฟไม่มีทิศทางแสดงชื่อเมืองและระยะทางระหว่างเมือง

กราฟ vs. ต้นไม้

ต้นไม้

ไม่มีวงรอบ
ทุกโหนดต้องเชื่อมต่อกัน

ภาพต้นไม้ที่มีโหนด

กราฟ

มีวงรอบได้
มีโหนดที่ไม่เชื่อมต่อได้

ภาพกราฟที่มีโหนด

กราฟ vs. ต้นไม้

ต้นไม้

ไม่มีวงรอบ
ทุกโหนดต้องเชื่อมต่อกัน

ภาพต้นไม้ที่มีโหนด

กราฟ

มีวงรอบได้
มีโหนดที่ไม่เชื่อมต่อได้

ภาพกราฟที่มีโหนด โดยมีโหนดหนึ่งที่ไม่เชื่อมต่อกับส่วนอื่น

กราฟ - กรณีการใช้งานจริง

ความสัมพันธ์ของผู้ใช้ในโซเชียลเน็ตเวิร์ก
- การเป็นเพื่อน
- การติดตาม
- การกดไลก์
- และอื่น ๆ
สถานที่และระยะทาง
- เพิ่มประสิทธิภาพเส้นทาง
ฐานข้อมูลกราฟ
อัลกอริทึมการค้นหาและเรียงลำดับ

กราฟ - การสร้าง

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

ภาพกราฟมีทิศทาง

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python