กราฟ (Graph)
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นอีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
ตัวอย่าง
V = {A,B,C,D,E,F,G}
E = {ab,ac,ad,be,cd,cf,de,ef,fg,eg}
โครงสร้างข้อมูลแบบกราฟ (Graph)
ศัพท์ที่เกี่ยวข้อง
1. เวอร์เทก (Vertex) หมายถึง โหนด
2. เอดจ (Edge)หมายถึงเส้นเชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Undirected Graph
3. Arc หมายถึง เส้นที่เชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Directed Graph
4. ดีกรี (Degree)หมายถึงจำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน
Graph แบ่งเป็น 1.Directed Graph (Digraph)
2.Undirected Graph
โครงสร้างข้อมูลแบบกราฟ (Graph)
แอดจาเซนท์โหนด (Adjacent Node)
A กับ B ใช่
D กับ F ไม่ใช่
เส้นทาง (Path)
ใช้เรียกลำดับของ เวอร์เทก (Vertex) ที่เชื่อมต่อกันจากจุดหนึ่งไปยังอีกจุดหนึ่ง
(A,B,C,D,E)
(A,B,E,F)
Cycle
Path ที่ประกอบด้วยอย่างน้อย 3 Vertex และมีจุดเริ่มต้นและสิ้นสุดเดียวกัน เช่น
(B,C,E,B)
(B,C,D,E,B)
ลูป (Loop)
มีเพียง Arc เดียวและมีจุดเริ่มต้นและสิ้นสุดเดียวกัน
Directed Graph : มีการกำหนดทิศทาง
Strongly Connected ทุก ๆ 2 Vertex มี Path ทั้งไปและกลับ
(ทุกโหนดในกราฟมีพาทติดต่อถึงกันหมด)
Weakly Connected : มีอย่างน้อย 2 Vertex ที่มี Path ในทิศทางเดียว(บางโหนดไม่สามารติดต่อไปยังทุกโหนดในกราฟนั้นได้)
สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบมีทิศทาง = N * (N –1)
จากภาพที่ (ข) ซึ่งเป็นกราฟแบบมีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมดเท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้
สูตรหาจำนวนเอดจ์ของกราฟมีทิศทาง = N * (N –1)
= 4 * ( 4 – 1)
= 4 * 3
= 12 เส้น
Undirected Graph : ไม่มีการกำหนดทิศทาง
เป็นกราฟที่ไม่ระบุทิศทางของการเชื่อมต่อ
ซึ่งสามารถทำให้สามารถเดินทางไปมาระหว่างกันได้
สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบไม่มีทิศทาง
= (N * (N – 1)) / 2
กราฟแบบไม่มีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมด เท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้
สูตรหาจำนวนเอดจ์ของกราฟไม่มีทิศทาง = (N * (N – 1)) / 2
= (4 * (4 – 1)) / 2
= (4 * 3 ) / 2
= 12 / 2
= 6 เส้น
กราฟที่มีน้ำหนัก (Weighted Graphs)
กราฟที่แต่ละเอดจ์จะมีค่าบ่งบอกถึงความหมายอย่างใดอย่างหนึ่ง เช่น ระยะทาง ความเร็ว เวลาเดินทาง ค่าโดยสาร เป็นต้น
กราฟที่ไม่มีน้ำหนัก (Unweighted Graphs)
เป็นกราฟที่ไม่กำหนดน้ำหนักของเส้นเชื่อมต่อโดยให้แต่ละเส้นมีน้ำหนักเป็น 1 เท่ากัน
หมดทุกเส้น
การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้
1.Adjacency Matrix : ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List : ใช้ลิงค์ลิสต์เก็บข้อมูล
Adjacency Matrix
เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
Mk เป็นเมทริกซ์ของกราฟใด ๆ k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง
0 : ไม่เป็นแอดจาเซนซีกัน
1 : เป็นแอดจาเซนซีกัน
1
การแทนกราฟด้วยอะเรย์สองมิติ
Adjacency List
Graph Traversal
สามารถทำได้ 2 วิธี
1. แนวลึก : Depth-first Traversal
2. แนวราบ : Breath-first Traversal
Breath-first Traversal
เป็นการท่องเข้าไปในกราฟโดยเข้าเยี่ยมโหนดตัวแรก และดำเนินการ หากมีโหนดใกล้เคียงจะดำเนินการกับโหนดที่อยู่ด้านซ้ายก่อน
1. Enqueue vertex
2. Dequeue vertex และประมวลผล
3. Enqueue adjacent ทั้งหมดของ Vertex ในข้อ 2
4. ทำซ้ำข้อ 2-3 จนกว่าจะครบทุก Vertex และ Queue ว่าง
Network
คือ Graph ที่ทุก Edge มี Weight กำกับโดยความหมายของ Weight นั้นขึ้นอยู่กับการใช้งาน
Adjacency Matrix
Adjacency List
Minimum Spanning Tree (MST)
คือSpanning Tree ที่มีผลรวมของ Weight ทั้งหมดน้อยที่สุด
1.ใส่ Vertex เริ่มต้นใน Tree
2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมี Weight ต่ำสุด
3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex
Shortest Path หมายถึง Path ที่สั้นที่สุดระหว่าง 2 Vertexหาเส้นทางการส่งข้อมูลจากต้นทางไปปลายทาง โดยให้มีระยะทางสั้นที่สุด
1.ใส่ Vertex เริ่มต้นใน Tree
2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมีผลรวมของ Weight ต่ำสุด
3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex
minimum Spanning Tree เป็นรูปแบบของการค้นหาโดยกำหนดเรียกใช้โหนดทุกโหนดและทุกเส้นการเชื่อมต่อ มาลำดับความสำคัญของน้ำหนักโดยเริ่มจากค่าน้อยที่สุดในข่ายงาน ทำการเชื่อมต่อคู่โหนดนั้น และดำเนินการต่อไปในค่าน้ำหนักที่ต่อกัน แต่ถ้าโหนดใดมีการเชื่อมต่อคู่โหนดแล้วจะไม่เชื่อมต่ออีก
Shortest Path เป็นอัลกอริทึมที่ใช้ในการหาระยะทางที่สั้นที่สุดเช่นเดียวกับ MST แต่จะเปลี่ยนจากการหาเส้นทางจากโหนดแรกไปยังโหนดปลายทางของข่ายงาน เป็นโหนดที่กำหนดเป็นโหนดต้นทางไปยังโหนดต่าง ๆ โดยหาระยะทางสั้นที่สุดแต่ละเส้นทาง
Minimum Spanning Tree
Spanning Tree หมายถึง Tree ที่ประกอบด้วยทุก Vertex ใน Graph ซึ่งอาจมีได้มากกว่า 1 แบบ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น