รูปปกบทความ

1. 🎯 ตอนที่ 14: ปูพื้นฐาน Graphs (เครือข่ายและความเชื่อมโยง)

2. 📖 เปิดฉาก (The Hook)

น้องๆ เคยสงสัยไหมครับว่า Google Maps รู้ได้อย่างไรว่าทางไหนคือ “เส้นทางที่สั้นที่สุด” หรือ “เร็วที่สุด” ฝ่าดงรถติดไปถึงที่ทำงาน? หรือเวลาที่เราเล่น Facebook, LinkedIn แล้วจู่ๆ ระบบก็เด้งขึ้นมาว่า “People You May Know” (คนที่คุณอาจรู้จัก) แถมยังแม่นซะด้วย! ระบบพวกนี้มันรู้ความสัมพันธ์ที่ซับซ้อนโยงใยกันเป็นใยแมงมุมขนาดนี้ได้อย่างไร?

คำตอบไม่ได้มาจากเวทมนตร์ครับ แต่มาจากโครงสร้างข้อมูลที่ทรงอิทธิพลที่สุดตัวหนึ่งในโลกของวิทยาการคอมพิวเตอร์ นั่นคือ Graph (กราฟ)! ในขณะที่ Array หรือ Linked List เก็บข้อมูลเป็นเส้นตรง และ Tree เก็บข้อมูลแบบลำดับชั้น (Hierarchy) แต่ Graph เกิดมาเพื่อจำลอง “เครือข่ายและความสัมพันธ์” ที่ไม่มีจุดเริ่มต้นหรือจุดสิ้นสุดตายตัว วันนี้พี่จะพาไปปูพื้นฐานโครงสร้างข้อมูลตัวนี้กันครับ รับรองว่าถ้าน้องๆ เข้าใจ Graph โลกของการเขียนโปรแกรมจะไม่เหมือนเดิมอีกต่อไป!

3. 🧠 แก่นวิชา (Core Concepts)

จากคัมภีร์ The Algorithm Design Manual และตำรา Data Structures ระดับโลก Graph $G = (V, E)$ ประกอบไปด้วยองค์ประกอบหลัก 2 ส่วนครับ:

  1. Vertices (หรือ Nodes): จุดยอดที่ใช้เป็นตัวแทนของ “สิ่งของ” หรือ “เอนทิตี” (Entities) เช่น ใน Facebook ตัว Vertex ก็คือโปรไฟล์ของพวกเราแต่ละคน หรือใน Google Maps มันก็คือพิกัดของสถานที่หรือทางแยกต่างๆ
  2. Edges (หรือ Links): เส้นเชื่อมที่ใช้บอก “ความสัมพันธ์” ระหว่าง Vertices เช่น เส้นเชื่อมบอกว่านาย A เป็นเพื่อนกับนาย B หรือเส้นถนนที่เชื่อมระหว่างสองสี่แยก

และด้วยความที่โลกเรามีความสัมพันธ์หลายรูปแบบ Graph จึงถูกแบ่งสายพันธุ์ย่อย (Flavors of Graphs) ออกไปอีก ดังนี้ครับ:

  • Directed vs. Undirected Graph (มีทิศทาง vs ไม่มีทิศทาง):
    • Undirected (ไม่มีทิศทาง): ความสัมพันธ์แบบไปกลับ เช่น การเป็นเพื่อนใน Facebook ถ้าน้องเป็นเพื่อนกับพี่ พี่ก็ต้องเป็นเพื่อนกับน้อง (เส้นเชื่อมวิ่งได้สองทาง)
    • Directed หรือ Digraph (มีทิศทาง): ความสัมพันธ์แบบวันเวย์ เช่น การกด Follow ใน Instagram หรือ Twitter น้องตามพี่ได้ แต่พี่ไม่จำเป็นต้องตามน้องกลับ (เส้นเชื่อมมีหัวลูกศรชี้บอกทิศทาง)
  • Weighted vs. Unweighted Graph (มีน้ำหนัก vs ไม่มีน้ำหนัก):
    • Unweighted (ไม่มีน้ำหนัก): ทุกเส้นเชื่อมมีค่าเท่ากันหมด เช่น การนับจำนวนคนรู้จัก (Hop) ว่าห่างกันกี่ช่วงตัว
    • Weighted (มีน้ำหนัก หรือ Network): เส้นเชื่อมแต่ละเส้นมี “ต้นทุน” หรือ “ระยะทาง” กำกับไว้ เช่น ถนนแต่ละเส้นใน Google Maps มีระยะทาง (กิโลเมตร) หรือเวลาที่ใช้เดินทาง (นาที) ไม่เท่ากัน เส้นที่มีรถติดก็จะมี Weight สูงกว่านั่นเอง
รูปประกอบ

4. 💻 ร่ายมนต์โค้ด (Show me the Code)

การเก็บข้อมูล Graph ในหน่วยความจำ (Memory) มีหลายท่า แต่ท่าที่ฮิตที่สุดและประหยัดพื้นที่สำหรับกราฟทั่วๆ ไป คือการใช้ Adjacency List (รายการความติดกัน) ครับ ในภาษา Python เราสามารถใช้ Dictionary จับคู่ระหว่าง Vertex และลิสต์ของเพื่อนบ้าน (Neighbors) ได้อย่างสวยงาม มาลองสร้าง Social Network จำลองกันครับ!

# จำลอง Social Network ด้วย Adjacency List สำหรับ Undirected Graph
# Key คือชื่อคน (Vertex) และ Value คือรายชื่อเพื่อน (Adjacent Vertices)
social_network = {
    'Alice': ['Bob', 'Cynthia', 'Diana'],
    'Bob': ['Alice', 'Cynthia', 'Fred'],
    'Cynthia': ['Alice', 'Bob'],
    'Diana': ['Alice', 'Fred'],
    'Fred': ['Bob', 'Diana'],
    'Elise': [] # Elise สายสันโดษ ไม่มีเพื่อนเลย (Isolated vertex)
}

# ฟังก์ชันง่ายๆ เพื่อหาว่า A และ B เป็นเพื่อนกันโดยตรงหรือไม่
def are_they_friends(graph, person1, person2):
    # เช็คแบบ O(1) ทางทฤษฎี (หรือ O(V) ใน worst case ของลิสต์) ว่าคนนึงอยู่ในลิสต์ของอีกคนไหม
    if person2 in graph.get(person1, []):
        return True
    return False

# ----- ลองวิชา -----
print("Alice เป็นเพื่อนกับ Bob หรือไม่?", are_they_friends(social_network, 'Alice', 'Bob')) 
# Output: True

print("Alice เป็นเพื่อนกับ Fred หรือไม่?", are_they_friends(social_network, 'Alice', 'Fred'))
# Output: False (แต่เขาสามารถรู้จักกันผ่าน Bob หรือ Diana ได้นะ!)

5. 🛡️ เคล็ดลับจากคัมภีร์ลับ (Under the Hood / Pro-Tips)

ถ้าน้องๆ ไปสัมภาษณ์งานบริษัท Tech ใหญ่ๆ คำถามปราบเซียนที่จะเจอคือ “เมื่อไหร่ควรใช้ Adjacency List และเมื่อไหร่ควรใช้ Adjacency Matrix?”

จากคัมภีร์ Data Structures and Algorithms มีกฎเหล็กในการตัดสินใจดังนี้ครับ:

  1. Adjacency Matrix: คือการสร้าง Array 2 มิติ ขนาด $V \times V$ (ตารางไขว้)
    • ข้อดี: ตรวจสอบว่ามีเส้นเชื่อมไหมได้ไวแสงระดับ $O(1)$ แค่เช็คพิกัด matrix[u][v]
    • ข้อเสีย: กินพื้นที่ Memory มหาศาลระดับ $O(V^2)$ สมมติว่ามีผู้ใช้ 1 ล้านคน น้องต้องสร้างตาราง 1 ล้าน x 1 ล้านช่อง! (พังแน่นอน)
    • เหมาะกับ: Dense Graphs (กราฟหนาแน่น) ที่ทุกๆ โหนดเชื่อมกันแทบจะหมด
  2. Adjacency List (แบบในโค้ดตัวอย่าง):
    • ข้อดี: กินพื้นที่ Memory น้อยมากๆ แค่ $O(V + E)$ ตามจำนวนคนและเส้นเชื่อมที่มีอยู่จริง
    • เหมาะกับ: Sparse Graphs (กราฟเบาบาง) ซึ่งในโลกความเป็นจริง โครงสร้างส่วนใหญ่เป็นแบบนี้ครับ! เช่น ต่อให้ Facebook มีคนเป็นพันล้านคน แต่คนนึงก็มีเพื่อนเฉลี่ยแค่หลักร้อยถึงพันคนเท่านั้น การใช้ Adjacency List จึงเป็น Best Practice สำหรับโจทย์ส่วนใหญ่ครับ

6. 🏁 บทสรุป (To be continued…)

Graph คือกระบวนทัศน์ขั้นสูงที่ช่วยให้เราจำลองโลกความเป็นจริงลงในคอมพิวเตอร์ได้อย่างไร้ขีดจำกัด ไม่ว่าจะเป็นวงจรไฟฟ้า, ระบบแผนที่, หรือ โครงข่ายอินเทอร์เน็ต แค่น้องเข้าใจนิยามของ Vertices, Edges, Directed และ Weighted ก็ถือว่ามีชัยไปกว่าครึ่งแล้วครับ!

แต่การมีแค่แผนที่เฉยๆ ก็คงหาทางออกไม่ได้จริงไหมครับ? ในตอนหน้า พี่จะพาน้องๆ ไปพบกับอัลกอริทึม “นักสำรวจ” อย่าง Breadth-First Search (BFS) และ Depth-First Search (DFS) ที่จะมาวิ่งลุยไปตามเส้นทางต่างๆ ใน Graph เพื่อหาคำตอบว่า “มีทางไปถึงเป้าหมายหรือไม่” และ “เส้นทางไหนสั้นที่สุด” เตรียมตัวให้พร้อม แล้วพบกันครับ!

ต้องการที่ปรึกษาด้านการออกแบบ System Architecture และพัฒนาระบบซอฟต์แวร์สเกลใหญ่ให้กับองค์กรของคุณ? ทีมงาน WP Solution พร้อมให้บริการออกแบบและพัฒนาซอฟต์แวร์แบบครบวงจร ดูรายละเอียดบริการของเราได้ที่: www.wpsolution2017.com หรือพูดคุยปรึกษาเบื้องต้นได้ที่ Line: wisit.p