กราฟคือโครงสร้างข้อมูลที่ประกอบด้วยกลุ่มของโหนด (nodes) และเส้นเชื่อมโหนด (edges) เข้าด้วยกันโดยแต่ละ edge จะเชื่อมโหนด 2 โหนดเข้าด้วยกัน

ถ้า edge มีทิศทาง (แสดงโดยหัวลูกศรด้านเดียว) เราเรียกว่ากราฟแบบมีทิศทาง (Directed graph)

ถ้า edge มีทิศทางทั้งสองด้าน (มีหัวลูกศรทั้งสองด้าน) หรือไม่มีทิศทาง (เป็นเส้นตรงไม่มีลูกศร) เราเรียกว่ากราฟแบบไม่มีทิศทาง (Undirected graph)

• ถ้าเส้นเชื่อมโหนดของกราฟแบบมีทิศทาง (directed graph) หรือไม่มีทิศทาง (undirected graph) วนกลับมาที่โหนดเดิมได้ เป็นวงกลม เราเรียกว่ากราฟวงกลม (cyclic graph)
• ถ้ากราฟมีทิศทางเป็นวงกลมเราเรียกว่า directed cyclic graph
• ถ้ากราฟมีทิศทางไม่เป็นวงกลมเราเรียกว่า directed acyclic graph (dag)
• ถ้าโหนด A กับ โหนด B อยู่ติดกัน (adjacent) เราเรียกว่ามีเส้นทางเดิน (path) จาก A ไปยัง B

• ถ้าเส้นเชื่อมระหว่างโหนดมีค่าน้ำหนัก (เป็นตัวเลข) กำกับ เราเรียกกว่ากราฟแบบมีน้ำหนัก (weighted graph)
• ถ้าเส้นเชื่อมระหว่างโหนดไม่มีค่าน้ำหนักกำกับ เราเรียกกว่ากราฟแบบไม่มีน้ำหนัก (unweighted graph)

• กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่นระบบเครื่อข่ายคอมพิวเตอร์ ระบบอินเตอร์เน็ต

• สายการบิน

• แผนที่ถนน

• เส้นทางการเดินรถ

• การหาเส้นทางที่สั้นที่สุด เป็นต้น

เราสามารถสร้างกราฟโดยใช้อาร์เรย์สองมิติดังนี้

int adj[MAXNODES][MAXNODES];

เราเรียกอาร์เรย์นี้ว่า adjacency matrix

ข้อมูลในแต่ละช่องของอาร์เรย์หมายถึงเส้นเชื่อมระหว่างโหนด ดังนั้นเราจึงสามารถใช้ข้อมูลนี้ในการตรวจสอบเส้นทางระหว่างโหนดได้ (Path Finder) ถ้ามีเส้นทางระหว่างโหนดก็กำหนดค่าเป็น 1 ถ้าไม่มีก็เป็น 0

ถ้าเป็นกราฟแบบมีน้ำหนัก ก็ให้ใส่ค่าน้ำหนักไปในอาร์เรย์ได้เลย

1. จาก adjacency matrix ที่กำหนด ให้วาดรูปกราฟแบบมีทิศทาง

2. จากกราฟที่กำหนด ให้เขียน adjacency matrix

เราสามารถสร้างกราฟโดยใช้ลิงค์ลิสต์มาเชื่อมต่อแต่ละโหนดของกราฟเข้าด้วยกัน เราเรียกกราฟนี้ว่า adjacency list โดยในลิสต์ประกอบด้วยสามส่วนคือส่วนที่เป็นข้อมูล ส่วนที่ตัวชี้ไปยังโหนดอื่น และส่วนที่เป็นตัวชี้ไปยังเส้นเชื่อมทั้งหมดของโหนดนั้นๆ ตามรูป

ข้อมูลในส่วนที่เป็นตัวชี้ไปยังเส้นเชื่อม จะบอกว่ามีเส้นทางจากโหนดนั้นไปยังโหนดอื่นๆตามเส้นเชื่อมทั้งหมด เช่นมีเส้นเชื่อมออกจากโหนด A 4 เส้น คือ A->B, A->C, A->D และ A->E ส่วนโหนด B และ โหนด E ไม่มีเส้นเชื่อมไปยังโหนดใดๆ หมายถึงไม่มีเส้นทางจาก B หรือ E ไปยังโหนดใดๆ

วิธีการค้นหาเส้นทางที่สั้นที่สุดในกราฟเรียกว่า greedy algorithm

ผู้คิดค้นวิธีการนี้เป็นคนแรกคือดิกสตรา (Dijkstra) นักคอมพิวเตอร์ชาวเนเธอร์แลนด์ จึงเรียกวิธีการนี้ว่า Dijkstra’s Algorithm

ประโยชน์ของการค้นหาเส้นทางที่สั้นที่สุดในกราฟเช่น การค้นหาระยะทางที่สั้นที่สุด การค้นหาราคาค่าเดินทางที่ถูกที่สุด การค้นหาเวลาที่สั้นที่สุด เป็นต้น

ถ้าต้องการหาระยะทางที่สั้นที่สุดระหว่างเมือง ก็สร้างกราฟให้โหนดแทนแต่ละเมือง และเส้นเชื่อมต่อแทนระยะทางระหว่างเมือง

ถ้าต้องการหาเวลาที่น้อยที่สุดในการเชื่อมต่อกับเซิฟเวอร์ ก็สร้างกราฟให้โหนดแทนคอมพิวเตอร์แต่ละเครื่อง และเส้นเชื่อมต่อแทนเวลาในการเชื่อมต่อ

ใช้สำหรับหาระยะทางที่สั้นที่สุดระหว่างสองโหนดในกราฟ ดังนี้

1. เริ่มจากโหนดที่กำหนด ให้เลือกโหนดถัดไปที่มีผลรวมของระยะทางจากโหนดเริ่มต้นถึงโหนดปัจจุบันน้อยที่สุด

2. ให้เลือกโหนดไปเรื่อยๆจนกว่าจะไปถึงโหนดปลายทางที่ต้องการ

ตัวอย่างที่ 1: Dijkstra’s Algorithm

ตัวอย่างที่ 2

จากกราฟที่กำหนด ให้หาระยะทางที่สั้นที่สุดจากจุด A ไปยังจุดอื่นๆทั้งหมด

ใช้ Dijkstra’s Algorithm เพื่อหาระยะทางที่สั้นที่สุดจากจุด A ไปยังทุกจุดดังนี้

1. ให้ลบเส้นเชื่อมทั้งหมดออกจากกราฟ

2. เริ่มที่จุด A ทำเครื่องหมายว่าแวะแล้วคือระยะเป็น 0 (แรเงาทึบตามรูป)

3. จากจุด A ให้ใส่เส้นเชื่อมที่ออกจาก A ทั้งหมด ตามกราฟเริ่มต้น ซึ่งมี 3 เส้นคือ A->E, A->C และ A->B ระยะทาง 2,3,5 ตามลำดับ

4. เลือกเส้นที่สั้นที่สุดคือ 2 เพื่อไปแวะที่จุด E แล้วทำเครื่องหมายว่าถึงแล้วคือระยะเป็น A->E=2

5. จาก E ให้ใส่เส้นเชื่อมที่ออกจาก E ทั้งหมด ตามกราฟเริ่มต้น ซึ่งมี 3 เส้นคือ E->D, E->B และ E->C ระยะทาง 4,6,10 ตามลำดับ

6. เลือกเส้นที่สั้นที่สุดลำดับถัดไป เริ่มจาก A คือระยะ 3, เส้นทางคือ A->C เพื่อไปแวะที่จุด C แล้วทำเครื่องหมายว่าแวะแล้วคือระยะเป็น A->C=3 และตัดเส้นเชื่อมเส้นอื่นที่มายัง C ออกทั้งหมด เพราะเราได้เส้นเชื่อมที่สั้นที่สุดแล้วคือ A->C

7. จาก C ให้ใส่เส้นเชื่อมที่ออกจาก C ทั้งหมด ตามกราฟเริ่มต้น ซึ่งมี 2 เส้นคือ C->B และ C->D ระยะทาง 1 และ 2 ตามลำดับ

8. เลือกเส้นที่สั้นที่สุดลำดับถัดไป เริ่มจาก A คือระยะ 4, เส้นทางคือ A->C->B เพื่อไปแวะที่จุด B แล้วทำเครื่องหมายว่าแวะแล้วคือระยะเป็น A->C->B=4 และตัดเส้นเชื่อมเส้นอื่นที่มายัง B ออกทั้งหมด เพราะเราได้เส้นเชื่อมที่สั้นที่สุดแล้วคือ A->C->B

9. จาก B ให้ใส่เส้นเชื่อมที่ออกจาก B ทั้งหมด ตามกราฟเริ่มต้น ซึ่งมี 1 เส้นคือ B->D ระยะทาง 6

10. เลือกเส้นที่สั้นที่สุดลำดับถัดไป เริ่มจาก A คือระยะ 5, เส้นทางคือ A->C->D เพื่อไปแวะที่จุด D แล้วทำเครื่องหมายว่าแวะแล้วคือระยะเป็น A->C->D=5 และตัดเส้นเชื่อมเส้นอื่นที่มายัง D ออกทั้งหมด เพราะเราได้เส้นเชื่อมที่สั้นที่สุดแล้วคือ A->C->D

11. ถ้าแวะครบทุกจุดแล้ว กราฟสุดท้ายที่ได้ จะมีลักษณะเป็นต้นไม้ จะเป็นกราฟที่กำหนดเส้นทางที่สั้นที่สุดจากจุด A ไปยังจุดอื่นๆในกราฟ คือจุด B, C, D, และ E

โปรแกรมจำลองการทำงานของ Dijkstra’s Algorithm

จากเส้นทางสายการบินตามรูป ให้สร้างกราฟที่เชื่อมต่อระหว่างทุกสนามบินด้วยระยะทางที่กำหนด จากนั้นให้หาเส้นทางบินที่สั้นที่สุดจาก BKK ไป HY

ให้อธิบายการประยุกต์ใช้กราฟเพื่อค้นหาเส้นทางที่สั้นที่สุดของการเดินทางโดยรถยนต์ภายในจังหวัดกรุงเทพ

1. จากกราฟที่กำหนด (ให้ถือว่าเป็นกราฟแบบไม่มีทิศทาง ไปกลับได้ทั้งสองทาง) ให้หาระยะทางที่สั้นที่สุดจากโหนด C และ โหนด E ไปยังโหนดอื่นๆทั้งหมด

2. จากกราฟที่กำหนด (ให้ถือว่าเป็นกราฟแบบไม่มีทิศทาง ไปกลับได้ทั้งสองทาง) ให้หาระยะทางที่สั้นที่สุดจากโหนด B ไปยังโหนดอื่นๆทั้งหมด

การท่องกราฟคือการแวะไปยังจุดต่างๆทั้งหมดในกราฟ ซึ่งค่อนข้างจะยุ่งยากกว่าการปีนต้นไม้ เพราะกราฟไม่มีรากหรือโหนดแรก เราสามารถท่องกราฟจากโหนดใดๆก็ได้ (ซึ่งต่างจากต้นไม้ ที่ต้องเริ่มจากรากเท่านั้น) สำหรับกราฟแบบไม่มีทิศทาง ไม่มีลำดับที่แน่นอน จะแวะไปทางไหนก่อนก็ได้

การท่องกราฟมีสองแบบคือแบบลึก (Depth-First) และแบบกว้าง (Breadth-First) ผลลัพธ์ที่ได้จากการท่องกราฟคือต้นไม้

การท่องกราฟแบบลึก ให้ท่องไปทางลึกจากบนลงล่าง ไปให้ไกลที่สุดเท่าที่จะไปได้ แล้วค่อยย้อนกลับเพื่อไปทางกว้าง โหนดที่แวะแล้วก็ไม่ต้องแวะซ้ำ จะได้ต้นไม้ที่สูง มีใบน้อย

การท่องกราฟแบบกว้าง ให้ไปทางกว้างจากซ้ายไปขวาให้หมดก่อน แล้วค่อยลงทางลึก โหนดที่แวะแล้วก็ไม่ต้องแวะซ้ำ จะได้ต้นไม้ที่เตี้ย มีใบมาก

ถ้าเริ่มที่โหนด A แวะไปให้ลึกที่สุดตามลำดับตัวอักษร ที่สร้างกราฟ จะได้ A->C->G->B->E เมื่อไปต่อไม่ได้ให้ย้อนกลับมาที่โหนดก่อนหน้า แล้วดูว่ามีทางไปต่อหรือไม่ ถ้ามีก็ไปต่อ ถ้าไปต่อไม่ได้ก็ย้อนกลับไปที่โหนดก่อนหน้าจนกว่าจะแวะครบทุกโหนด จะได้ผลลัพธ์ คือ A->C->G->B->E->F->H->D ตามลำดับการแวะที่โหนด

ถ้าเริ่มที่โหนด B จะได้ผลลัพธ์ คือ B->E->F->G->H และไปต่อไม่ได้แล้ว แต่ยังแวะไม่หมด ก็ให้สุ่มโหนดที่เหลือ ถ้าเลือก C จะได้ C โหนดเดียว ก็สุ่มโหนดต่อไป ถ้าเลือก A จะได้ A->D ตามรูปด้านบน จะได้ผลลัพธ์ของการท่องกราฟเป็นต้นไม้สามต้น

ถ้าเริ่มที่โหนด A แวะไปให้ลึกที่สุดตามลำดับตัวอักษร ที่สร้างกราฟ จะได้ A->B->E->F->K เมื่อไปต่อไม่ได้ให้ย้อนกลับมาที่โหนดก่อนหน้า แล้วดูว่ามีทางไปต่อหรือไม่ ถ้ามีก็ไปต่อ ถ้าไปต่อไม่ได้ก็ย้อนกลับไปที่โหนดก่อนหน้าจนกว่าจะแวะครบทุกโหนด จะได้ผลลัพธ์ ตามลำดับการแวะที่โหนดคือ A->B->E->F->K->G->C->D->H->I->J

ถ้าเริ่มที่โหนด A แวะโหนดลูกของ A ให้หมดก่อน แล้วจึงแวะไปที่โหนดลำดับถัดไปด้านล่าง โดยแวะไปที่โหนดระดับดียวกันให้หมดก่อน แล้วค่อยแวะไปที่ลำดับถัดไป ตามลำดับตัวอักษร ที่สร้างกราฟ จะได้ A->C->D เมื่อไปต่อไม่ได้ ให้เริ่มที่โหนดแรกด้านล่าง แล้วท่องกราฟแบบเดียวกัน จนกว่าจะแวะครบทุกโหนด จะได้ผลลัพธ์ ตามลำดับการแวะที่โหนดคือ A->C->D->G->B->F->E->H

ถ้าเริ่มที่โหนด A แวะโหนดลูกของ A ให้หมดก่อน แล้วจึงแวะไปที่โหนดลำดับถัดไปด้านล่าง โดยแวะไปที่โหนดระดับดียวกันให้หมดก่อน แล้วค่อยแวะไปที่ลำดับถัดไป ตามลำดับตัวอักษร ที่สร้างกราฟ จะได้ A->B->D->J เมื่อไปต่อไม่ได้ ให้เริ่มที่โหนดแรกด้านล่าง แล้วท่องกราฟแบบเดียวกัน จนกว่าจะแวะครบทุกโหนด จะได้ผลลัพธ์ ตามลำดับการแวะที่โหนดคือ A->B->D->J->E->C->H->I->F->G->K

1. จากกราฟที่กำหนด ให้ท่องกราฟแบบ Depth-First และ Breadth-First โดยเริ่มจากโหนด A

2. จากกราฟที่กำหนด ให้ท่องกราฟแบบ Depth-First และ Breadth-First โดยเริ่มจากโหนด B

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

กำหนดกราฟใดๆ ให้ท่องกราฟเพื่อสร้างต้นไม้ที่ผลรวมของน้ำหนักทั้งหมดมีค่าน้อยที่สุด ต้นไม้นี้เรียกว่า Minimum Spanning Tree (MST) ซึ่งเป็นการสร้างต้นไม้ที่เชื่อมต่อทุกโหนดเข้าด้วยกันโดยมีน้ำหนักรวมน้อยที่สุด โดยแต่ละโหนดจะมีเส้นเชื่อมเข้า-ออก ไม่เกิน 2 เส้น

จากตัวอย่างกราฟด้านบน กราฟเริ่มต้นเชื่อมต่อทุกโหนด มีน้ำหนักรวม 17 เราสามารถเปลี่ยนกราฟเป็นต้นไม้ได้หลายรูปแบบ ตามตัวอย่างคือ ต้นไม้ 4 ต้น ที่ยังคงเชื่อมต่อทุกโหนดเข้าด้วยกัน โดยมีหนักรวมเป็น 10, 12, 14 และ 15 ซึ่งต้นไม้ที่มีน้ำหนักรวมน้อยที่สุดคือ 10 (ในวงกลม) ต้นไม้ต้นนี้เราเรียกว่า Minimum Spanning Tree

---

การเปลี่ยนกราฟเป็นต้นไม้มีอยู่ 2 วิธีหลักๆคือ Prim’s Algorithm และ Kruskal’s Algorithm ดังนี้

ใช้สำหรับสร้าง minimum spanning tree (MST) ดังนี้

1. เลือกโหนดใดๆก็ได้เป็นโหนดเริ่มต้น
2. โหนดต่อมาให้เลือกจากเส้นเชื่อมต่อที่มีน้ำหนักน้อยที่สุด นับจากโหนดปัจจุบัน
3. ให้เลือกโหนดไปเรื่อยๆจนกว่าจะแวะไปครบทุกโหนด เราก็จะได้ต้นไม้ซึ่งแปลงมาจากกราฟ โดยผลลัพธ์ที่ได้คือต้นไม้ต้นเดียวกัน ไม่ว่าจะเริ่มต้นจากโหนดไหนก็ตาม แต่ต้นไม้นี้ไม่ใช้ต้นไม้คู่ (Binary tree)

1. ให้ลบเส้นเชื่อมทั้งหมดออกจากกราฟ
2. เริ่มที่จุด A ทำเครื่องหมายว่าแวะแล้ว
3. จากจุด A ให้เลือกเส้นเชื่อมที่สั้นที่สุดที่ออกจาก A ซึ่งคือเส้น A->D มีน้ำหนัก 1 ทำเครื่องหมายว่าแวะที่ D แล้ว
4. เลือกเส้นที่สั้นที่สุดเส้นถัดไป คือเส้น A->B มีน้ำหนัก 2 ทำเครื่องหมายว่าแวะที่ B แล้ว
5. เลือกเส้นที่สั้นที่สุดเส้นถัดไป คือเส้น D->C มีน้ำหนัก 2 ทำเครื่องหมายว่าแวะที่ C แล้ว
6. เลือกเส้นที่สั้นที่สุดเส้นถัดไป คือเส้น D->G มีน้ำหนัก 4 ทำเครื่องหมายว่าแวะที่ G แล้ว
7. เลือกเส้นที่สั้นที่สุดเส้นถัดไป คือเส้น G->F มีน้ำหนัก 1 ทำเครื่องหมายว่าแวะที่ F แล้ว
8. เลือกเส้นที่สั้นที่สุดเส้นถัดไป คือเส้น G->E มีน้ำหนัก 6 ทำเครื่องหมายว่าแวะที่ E แล้ว
9. ถ้าแวะครบทุกจุดแล้ว กราฟสุดท้ายที่ได้จะมีลักษณะเป็นต้นไม้ ที่มีผลรวมน้ำหนักที่เชื่อมต่อทุกโหนดน้อยที่สุดหรือ Minimum Spanning Tree จากต้นไม้ด้านบนจะมีผลรวมน้ำหนักเป็น 16

เป็นอีกวิธีหนึ่งในการสร้าง MST โดยตอนเริ่มต้นจะแยกกราฟให้เป็นป่าไม้ (Forest) แต่ละป่ามีต้นไม้แค่ต้นเดียว จากนั้นก็ค่อยๆเชื่อมต่อต้นไม้ทั้งหมดเข้าด้วยกัน จนเหลือต้นไม้เพียงต้นเดียว ทีมีผลรวมของน้ำหนักน้อยที่สุด

วิธีการคือ
1. ให้สร้างตารางของเส้นเชื่อมต่อทั้งหมดแล้วเรียงลำดับจากน้อยไปหามาก
2. ให้เลือกเส้นเชื่อมต่อที่น้อยที่สุดทีละเส้น แล้วเพิ่มโหนดของเส้นเชื่อมต่อนั้นเข้าไปในต้นไม้ เฉพาะเส้นเชื่อมต่อที่ไม่ทำให้เกิดกราฟวงกลม (cycle)
3. เมื่อทุกโหนดถูกใส่เข้าไปในต้นไม้ ก็จะได้ MST เส้นเชื่อมต่อที่ยังเหลืออยู่ก็ให้ตัดทิ้งไป

1. ให้ลบเส้นเชื่อมทั้งหมดออกจากกราฟ
2. สร้างตารางของเส้นเชื่อมโหนดทั้งหมดเรียงลำดับจากน้อยไปหามาก เช่น
3. เลือกเส้นเชื่อมต่อที่น้อยที่สุดทีละเส้น แล้วเพิ่มโหนดของเส้นเชื่อมต่อนั้นเข้าไปในต้นไม้ เฉพาะเส้นเชื่อมต่อที่ไม่ทำให้เกิดกราฟวงกลม (cycle) ตามตัวอย่างในตารางด้านล่างนี้

4. ถ้าเลือกครบทุกโหนดแล้ว จะได้ต้นไม้ ที่มีผลรวมน้ำหนักที่เชื่อมต่อทุกโหนดน้อยที่สุดหรือ Minimum Spanning Tree จากต้นไม้ด้านบนจะมีผลรวมน้ำหนักเป็น 16

1. จากกราฟที่กำหนด ให้สร้าง Minimum Spanning Tree ด้วย Prim และ Kruskal Algprithm

2. จากกราฟที่กำหนด ให้สร้าง Minimum Spanning Tree ด้วย Prim และ Kruskal Algprithm

3. จากกราฟที่กำหนด ให้สร้าง Minimum Spanning Tree ด้วย Prim และ Kruskal Algprithm