Graph
กราฟ Graph เป็นโครงสร้างข้อมุลแบบไม่เชิงเส้น อีกชนิดหนี่ง กราฟเป็นดครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ไขปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤต และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
1. โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edger) การเชื่อมต่อ กราฟที่มีเอ็จเชื่อมต่อระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Garphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า การฟแบบมีทิศทาง
(Directed Deaphs) หรือมีลูกศร เป็นกราฟที่แสดงการเชื่อม ระหว่าง Vertex โดยแสดงทิศทางการเชื่อมต่อด้วย บางครั้งเรียกว่า ไดกราฟ (Digraph) ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัวการสากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใดๆ สามารถวนเข้ามาหาตัวมันเองได้
โดยทั่วๆไป การเขียนกราฟเพื่อแสดงให้เห็นด้วยความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วยจุด (Pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง(Empty Graph) แต่ละเอ็จชะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง อ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node)
หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจว่างไม่มีโหนดหรือเอ็จเลยป็นกราฟว่าง(Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (Source Node)และโหนดสิ้นสุด (Target Node)
รูปแบบต่างๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบ ของกราฟแบบไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนที่กราฟในหน่วยความจำ
ในการปฎิบัติการกับโครงสร้างกราฟ สื่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างดหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การแทนที่กราฟด้วยเมตริกซ์
โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย ค่า 0 และ 1
ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ
ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง
ตัวอย่างจากรูปกราฟแบบ Direct Graph
สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้
หากเป็นกราฟแบบ Undirected Graph
การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix
จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น