กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (nodes) หรือ เวอร์เทกซ์ (vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (edges)
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดง ความสัมพันธ์ระหว่างโหนดได้ถูกต้อง
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า
กราฟแบบมีทิศทาง(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes)
หรือวงกลม (circles)ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้น
หรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้อง
มีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (first node) หรือไม่มีโหนดเริ่มต้นไม่มีโหนดใดเป็นโหนดสิ้นสุด ดังนั้นเราอาจจะกล่าวว่าเอ็จเชื่อมโหนด u และโหนด v หรือจะกล่าวว่าเอ็จเชื่อมโหนด v และโหนด u ก็มีความหมายเหมือนกัน
ตัวอย่างกราฟแบบไม่มีทิศทางในรูปแบบต่างๆ
ตัวอย่างกราฟแบบไม่มีทิศทางในรูปแบบต่าง ๆ และโหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ ใกล้กัน (adjacent) ถ้ามีเอ็จเชื่อมจากโหนดที่หนึ่งไปโหนดที่สอง กราฟ (ก) แสดงกราฟที่มีลักษณะ ต่อเนื่อง (connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใด ๆ ไปยังโหนดอื่นเสมอ โดยมีโหนด 1 กับโหนด 2 และ โหนด 3 กับ โหนด 4 เป็นโหนดที่ใกล้กัน แต่โหนด 1 และ 4 ไม่ใช่โหนดที่ใกล้กัน กราฟ (ข) แสดงกราฟที่มีลักษณะเป็น วีถี (path) มีเส้นทางเชื่อมไปยังโหนดต่าง ๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป กราฟ (ค) แสดงกราฟที่เป็นวัฎจักร (cycle) ซึ่งต้องมีอย่างน้อย 3 โหด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก กราฟ (ง) แสดงกราฟที่มีลักษณะ ไม่ต่อเนื่อง (disconnected) เนื่องจากไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย กราฟ (ก), (ข) และ (ค) ถือว่าเป็นกราฟต่อเนื่อง และกราฟ (จ) แสดงกราฟที่เป็นทรี โดยทรีเป็นกราฟที่ต่อเนื่อง ไม่มีทิศทาง และไม่เป็นวัฏจักร
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (empty graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น (source node) และโหนดสิ้นสุด (target node)
รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟ ไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
ตัวอย่างกราฟแบบมีทิศทาง
การแทนกราฟในหน่วยความจำ การแทนกราฟในหน่วยความจำด้วยวิธีเก็บเอ็จทั้งหมดใน แถวลำดับ 2 มิติ จะค่อนข้างเปลืองเนื้อที่ เนื่องจากมีบางเอ็จที่เก็บซ้ำอาจหลีกเลี่ยงปัญหานี้ได้โดยใช้แถวลำดับ 2 มิติเก็บโหนดและ พอยเตอร์ชี้ไปยงตำแหน่งของโหนดต่าง ๆ ที่สัมพันธ์ด้วย และใช้ แถวลำดับ1 มิติเก็บโหนดต่าง ๆ ที่มีความสัมพันธ์กับโหนดในแถวลำดับ 2 มิติ
การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยน์เตอร์นี้ยุ่งยากในการจัดการเพิ่มขึ้นเนื่องจากต้องเก็บโหนดและพอยน์เตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ 1 มิติ อย่างไรก็ตามทั้งสองวิธีที่กล่าวมาข้างต้นไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา ควรใช้ในกราฟที่ไม่มีการเปลี่ยนแปลงตลอดอายุขัยของการใช้งาน เพราะถ้ามีการเปลี่ยนแปลงส่วนใดส่วนหนึ่งของกราฟจะกระทบกับส่วนอื่น ๆ ที่อยู่ในระดับที่ต่ำกว่าด้วยเสมอ
กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจจะใช้วิธีแอดจาเซนซีลิสต์ (adjacency list) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและพอยน์เตอร์ที่กล่าวมาแล้วข้างต้น แต่ต่างกันตรงที่แทนที่จะเก็บโหนดที่มีความสัมพันธ์ด้วยไว้ในแถวลำดับ 1 มิติ จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
การท่องแบบกว้าง (breadth first traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
การท่องแบบลึก (depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
สรุปย่อ
กราฟเป็นโครงสร้างข้อมูลที่นำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ ค่อนข้างซับซ้อน ตัวอย่างโครงสร้างข้อมูลแบบกราฟ เช่น การวางข่ายงานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤต การวางแผนข่ายงาน และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น ซึ่งกราฟมีนิยามดังนี้
กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ
- โหนด หรือ เวอร์เทกซ์
- เส้นเชื่อมความสัมพันธ์ระหว่างโหนดเรียว่า เอ็จ
โดยกราฟจะมีอยู่สองประเภทคือ กราฟแบบมีทิศทาง และกราฟแบบไม่มีทิศทาง โดยกราฟแบบมีทิศทางเอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อ โดยมีโหนดเริ่มต้นและโหนดสิ้นสุด ส่วนกราฟแบบไม่มีทิศทางจะไม่คำนึงถึงลำดับของการเชื่อมต่อกัน ไม่มีโหนดแรกและโหนดสิ้นสุด นอกจากนั้นกราฟมีโครงสร้างหลายรูปแบบเช่น ต่อเนื่อง ไม่ต่อเนื่อง วิถี วัฎจักร และทรี เป็นต้น
การแทนกราฟในความจำหลักวิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จทุก ๆ เอ็จในแถวลำดับ 2 มิติ แต่วิธีนี้ค่อนข้างเปลืองเนื้อที่เนื่องจากมีบางเอ็จที่เก็บซ้ำเดิม อีกวิธีหนึ่งก็คือใช้แถวลำดับ 2 มิติเก็บโหนดและพอยน์เตอร์ชี้ไปยังตำแหน่งโหนดต่าง ๆ ที่สัมพันธ์ด้วย (ใช้แถวลำดับ 1 มิติเก็บโหนดที่สัมพันธ์ด้วย) หรือใช้วิธีแอดจาเซนซีลิสต์โดยใช้ลิงค์ลิสต์แทนแถวลำดับ 1 มิติ อย่างไรก็ตามทั้งสามวิธีที่กล่าวมาไม่เป็นที่นิยม วิธีที่นิยมมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ โดยถ้ากราฟของเรามี n โหนดต้องสร้างเมทริกซ์จัตุรัสขนาด n x n เช่น และค่าในเมทริกซ์จะเก็บว่าระหว่างโหนดสองโหนดมีคู่ใดบ้างที่มีความสัมพันธ์กัน เราสามารถหาได้ว่ามีเส้นทางขนาดเท่าใด และมีกี่เส้นทาง จากการนำแอดจาเซนซีเมทริกซ์มาคูณด้วยตัวมันเอง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น