สรุปเนื้อหา "data structure"
เรื่อง กราฟ (Graph)
กราฟ(Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น เป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่ายงานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤต และปัญหาเส้นที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยลุ่มของสิ่งสองสิ่ง คือ
- โหนด(Nodes) หรือ เวอร์เทกซ์(Vertexes)
- เส้นเชื่อมระหว่างโหนด เรียก เอ็จ(Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง(Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs) บางครั้งเรียกว่า "ไดกราฟ"(Digraph)
การเขียนกราฟแสดงโหนดแต่ละเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบตายตัว การลากเส้นความสัมพันธ์เป็นลักษณะเส้นไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใดๆสามารถวนเข้าหาตัวมันเองได้
โดยทั่วๆไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ของสิ่งที่เราสนใจแทนโหนดด้วยจุด(pointes) และวงกลม(circles) ที่มีชื่อหรือข้อมูลกำกับเพื่อบอกความแตกต่างของแต่ละโหนด
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง(Empty Graph) นั่นคือ ไม่มีโหนดใดเป็นโหนดแรก(First Node) หรือไม่มีโหนดเริ่มต้นและไม่มีโหนดใดเป็นโหนดส้นสุด โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน(Adjacent)
กราฟแบบมีทิศทางเป็นเซตจำกัดของโหนดและเอ็จ
รูปแบบต่างๆของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟไม่มีทิศทางต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำหนดด้วยเท่านั้น
การแทนที่กราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟสิ่งที่ต้องจัดเก็บจากกราฟโดยทั่วไปก็คือเอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมาที่สุดคือการเก็บเอ็จในแถวลำดับ 2 มิติ
การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยเตอร์นี้ยุ่งยาก ในการจัดเก็บเพิ่มขึ้นเนื่องจากต้องเก็บโหนดและพอยเตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ
อย่างไรก็ตามทั้งสองวิธีไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา เพราะถ้ามีการเปลี่ยนแปลงส่วนใดส่วนหนึ่งของกราฟจะกระทบกับส่วนอื่นๆที่อยู่ในระดับที่ต่ำกว่าด้วยเสมอ
กราฟที่มีการเปลี่ยนแปลงตลอดเวลาอาจใช้วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและพอยเตอร์ แต่ต่างกันตรงที่จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
วิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุด คือ การแทนด้วยแอดจาเซนซีเมทริกซ์(Adjacency Matrix)
การท่องไปในกราฟ
การท่องไปในกราฟ(graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟโดยมีหลักในการทำงานคือแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำกันจึงจำเป็นต้องทำเครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
- การท่องแบบกว้าง(Breadth First Traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้นต่อมาเยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งยือนหมดทุกโหนด
- การท่องแบบลึก(Depth First Traversal) การทำงานคล้ายกับการท่องทีละระดับของทรีโดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ(backtrack) ตามแนววิถีเดิมนั้นจนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่นๆเพื่อเยือนโหนดอื่นๆต่อไปจนครบทุกโหนด
*********************************************************************************
