สวัสดีทุกคน
ในบันทึกนี้ ฉันตัดสินใจที่จะแสดงรายการโครงสร้างข้อมูลหลักที่ใช้จัดเก็บกราฟในวิทยาการคอมพิวเตอร์ และฉันจะพูดถึงโครงสร้างดังกล่าวอีกสองสามอย่างที่ "ตกผลึก" สำหรับฉันด้วย
เอาล่ะ มาเริ่มกันเลย แต่ไม่ใช่ตั้งแต่เริ่มต้น ฉันคิดว่าเราทุกคนรู้อยู่แล้วว่ากราฟคืออะไรและคืออะไร (มีทิศทาง ไม่กำหนดทิศทาง ถ่วงน้ำหนัก ไม่ถ่วงน้ำหนัก มีหรือไม่มีหลายขอบและลูป)
งั้นไปกัน. เรามีตัวเลือกอะไรบ้างสำหรับโครงสร้างข้อมูลสำหรับ "การจัดเก็บกราฟ"?
1. โครงสร้างข้อมูลเมทริกซ์
1.1 เมทริกซ์ที่อยู่ติดกัน เมทริกซ์ adjacency เป็นเมทริกซ์ที่ส่วนหัวของแถวและคอลัมน์สอดคล้องกับจำนวนจุดยอดของกราฟ และค่าของแต่ละองค์ประกอบ a(i,j) จะถูกกำหนดโดยการมีหรือไม่มีขอบระหว่างจุดยอด i และ j (เห็นได้ชัดว่าสำหรับกราฟที่ไม่มีทิศทาง เมทริกซ์ดังกล่าวจะสมมาตร หรือเราสามารถตกลงว่าเราเก็บค่าทั้งหมดไว้เหนือเส้นทแยงมุมหลักเท่านั้น) สำหรับกราฟที่ไม่ถ่วงน้ำหนัก a(i,j) สามารถกำหนดได้ด้วยจำนวนเส้นเชื่อมตั้งแต่ i ถึง j (หากไม่มีเส้นดังกล่าว ดังนั้น a(i,j)= 0) และสำหรับกราฟถ่วงน้ำหนัก จะต้องกำหนดน้ำหนักด้วย (น้ำหนักรวม) ของขอบดังกล่าว
1.2 เมทริกซ์อุบัติการณ์ ในกรณีนี้ กราฟของเราจะถูกจัดเก็บไว้ในตารางซึ่งตามกฎแล้ว หมายเลขแถวจะสอดคล้องกับหมายเลขของจุดยอด และหมายเลขคอลัมน์จะสอดคล้องกับขอบที่กำหนดไว้ล่วงหน้า หากจุดยอดและขอบประจันหน้ากัน ค่าที่ไม่เป็นศูนย์จะถูกเขียนลงในเซลล์ที่สอดคล้องกัน (สำหรับกราฟที่ไม่มีทิศทาง 1 จะถูกเขียนหากจุดยอดและขอบตกกระทบกัน สำหรับกราฟเชิง - “1” หากขอบ “ออก” จากจุดยอดและ “-1” ถ้ามัน “รวม” ไว้ (ซึ่งง่ายต่อการจดจำ เนื่องจากเครื่องหมาย “ลบ” ดูเหมือนจะ “รวม” ไว้ในตัวเลข “-1”) ด้วย สำหรับกราฟถ่วงน้ำหนัก คุณสามารถระบุน้ำหนักรวมของขอบได้ แทนที่จะระบุ 1 และ -1
2. โครงสร้างข้อมูลแจงนับ
2.1 รายการที่อยู่ติดกัน ดูเหมือนทุกอย่างจะง่ายที่นี่ โดยทั่วไป แต่ละจุดยอดของกราฟสามารถเชื่อมโยงกับโครงสร้างการแจกแจงใดๆ (รายการ เวกเตอร์ อาร์เรย์ ...) ซึ่งจะเก็บตัวเลขของจุดยอดทั้งหมดที่อยู่ติดกับจุดที่กำหนด สำหรับกราฟที่มีการกำหนดทิศทาง เราจะเพิ่มเฉพาะจุดยอดที่มีขอบ "กำหนดทิศทาง" จากจุดยอดคุณลักษณะเท่านั้นลงในรายการ สำหรับกราฟถ่วงน้ำหนัก การใช้งานจะซับซ้อนมากขึ้น
2.2 รายการซี่โครง. โครงสร้างข้อมูลค่อนข้างเป็นที่นิยม รายการของขอบ ดังที่ Captain Obviousness บอกเรา จริงๆ แล้วคือรายการของขอบของกราฟ ซึ่งแต่ละรายการจะระบุโดยจุดยอดเริ่มต้น จุดสิ้นสุด (สำหรับกราฟที่ไม่ได้กำหนดทิศทาง ลำดับไม่สำคัญในที่นี้ แม้ว่าสำหรับการรวมเข้าด้วยกัน คุณสามารถ ใช้กฎต่างๆ เช่น ระบุจุดยอดตามลำดับการเพิ่ม) และน้ำหนัก (สำหรับกราฟถ่วงน้ำหนักเท่านั้น)
คุณสามารถดูรายการเมทริกซ์ที่แสดงด้านบนโดยละเอียดได้ (และมีภาพประกอบ) เช่น .
2.3 อาร์เรย์ที่อยู่ติดกัน ไม่ใช่โครงสร้างที่พบบ่อยที่สุด โดยแก่นของมันคือรูปแบบของ "การบรรจุ" รายการที่อยู่ติดกันลงในโครงสร้างการแจงนับเดียว (อาร์เรย์ เวกเตอร์) องค์ประกอบ n ตัวแรก (ตามจำนวนจุดยอดของกราฟ) ของอาร์เรย์ดังกล่าวมีดัชนีเริ่มต้นของอาร์เรย์เดียวกัน โดยเริ่มจากจุดยอดทั้งหมดที่อยู่ติดกับจุดที่กำหนดจะถูกเขียนเรียงกันเป็นแถว
ที่นี่ฉันพบคำอธิบายที่เข้าใจได้มากที่สุด (สำหรับตัวฉันเอง):
3. Adjacency Vector และ Associative Adjacency Array
ปรากฎว่าผู้เขียนบรรทัดเหล่านี้ไม่ใช่โปรแกรมเมอร์มืออาชีพ แต่เกี่ยวข้องกับกราฟเป็นระยะ ๆ ส่วนใหญ่มักจะจัดการกับรายการขอบ แน่นอนว่าจะสะดวกหากกราฟมีหลายลูปและขอบ ดังนั้น ในการพัฒนารายการ edge แบบคลาสสิก ฉันเสนอให้ใส่ใจกับ "การพัฒนา/สาขา/การแก้ไข/การกลายพันธุ์" ของพวกเขา กล่าวคือ: เวกเตอร์ adjacency และอาร์เรย์ adjacency แบบเชื่อมโยง
3.1 เวกเตอร์ที่อยู่ติดกัน
กรณี (a1): กราฟไม่ถ่วงน้ำหนัก
เราจะเรียกเวกเตอร์ adjacency สำหรับกราฟที่ไม่ถ่วงน้ำหนักว่าเซตลำดับของจำนวนเต็มคู่ (a[2i), a[2i+1],... โดยที่ i ถูกกำหนดเป็นตัวเลข c 0) ซึ่งแต่ละคู่ของตัวเลข คือ a[2i], a[2i+1 ] ระบุขอบกราฟระหว่างจุดยอด a[2i] และ a[2i+1] ตามลำดับ
รูปแบบการบันทึกนี้ไม่มีข้อมูลเกี่ยวกับทิศทางของกราฟหรือไม่ (เป็นไปได้ทั้งสองตัวเลือก) เมื่อใช้รูปแบบไดกราฟ ขอบจะถือว่าเปลี่ยนทิศทางจาก a[2i] ไปยัง a[2i+1] ที่นี่และด้านล่าง: สำหรับกราฟที่ไม่มีทิศทาง หากจำเป็น สามารถใช้ข้อกำหนดสำหรับลำดับของจุดยอดในการบันทึกได้ (เช่น จุดยอดที่มีค่าต่ำกว่าของตัวเลขที่กำหนดให้มาก่อน)
ใน C++ ขอแนะนำให้ระบุเวกเตอร์ adjacency โดยใช้ std::vector จึงเป็นชื่อของโครงสร้างข้อมูลนี้
กรณี (a2): กราฟที่ไม่ถ่วงน้ำหนัก น้ำหนักขอบเป็นจำนวนเต็ม
โดยการเปรียบเทียบกับกรณี (a1) เราเรียกเวกเตอร์ adjacency สำหรับกราฟถ่วงน้ำหนักที่มีขอบจำนวนเต็ม เรียกว่าชุดลำดับ (อาร์เรย์ไดนามิก) ของตัวเลข (a[3i], a[3i+1], a[3i+2] ... โดยที่ i มีหมายเลข c 0) โดยที่ “triplet” แต่ละตัวของตัวเลข a[3i], a[3i+1], a[3i+2] ระบุขอบของกราฟระหว่างจุดยอดที่มีหมายเลข a[3i] และ a[3i+1] ตามลำดับ และค่า a [3i+2] คือน้ำหนักของขอบนี้ กราฟดังกล่าวสามารถกำหนดทิศทางได้หรือไม่ก็ได้
กรณี (b): กราฟแบบไม่ถ่วงน้ำหนัก, น้ำหนักขอบที่ไม่ใช่จำนวนเต็ม
เนื่องจากเป็นไปไม่ได้ที่จะจัดเก็บองค์ประกอบที่ต่างกันในอาร์เรย์เดียว (เวกเตอร์) ตัวอย่างเช่น การใช้งานต่อไปนี้จึงเป็นไปได้ กราฟถูกจัดเก็บไว้ในคู่ของเวกเตอร์ โดยเวกเตอร์แรกคือเวกเตอร์ที่อยู่ติดกันของกราฟโดยไม่ระบุน้ำหนัก และเวกเตอร์ที่สองมีน้ำหนักที่สอดคล้องกัน (เป็นไปได้สำหรับ C++: std::pair ). ดังนั้น สำหรับขอบที่กำหนดโดยคู่ของจุดยอดภายใต้ดัชนี 2i, 2i+1 ของเวกเตอร์แรก น้ำหนักจะเท่ากับองค์ประกอบภายใต้ดัชนี i ของเวกเตอร์ที่สอง
เหตุใดจึงจำเป็น?
ผู้เขียนบรรทัดเหล่านี้พบว่ามีประโยชน์มากในการแก้ปัญหาหลายประการ จากมุมมองที่เป็นทางการจะมีข้อดีดังต่อไปนี้:
- เวกเตอร์ adjacency เช่นเดียวกับโครงสร้าง "การแจงนับ" อื่นๆ มีขนาดค่อนข้างเล็ก ใช้หน่วยความจำน้อยกว่าเมทริกซ์ adjacency (สำหรับกราฟแบบกระจาย) และใช้งานได้ค่อนข้างง่าย
- โดยหลักการแล้ว จุดยอดของกราฟสามารถทำเครื่องหมายด้วยตัวเลขติดลบได้เช่นกัน จะเกิดอะไรขึ้นหากจำเป็นต้องมี "ความวิปริต" เช่นนี้?
- กราฟสามารถประกอบด้วยหลายขอบและหลายลูป โดยมีน้ำหนักต่างกัน (บวก ลบ แม้แต่ศูนย์) ไม่มีข้อจำกัดที่นี่
- คุณยังสามารถกำหนดคุณสมบัติต่างๆ ให้กับขอบได้ แต่สำหรับข้อมูลเพิ่มเติม โปรดดูส่วนที่ 4
อย่างไรก็ตาม ต้องยอมรับว่า “รายการ” นี้ไม่ได้หมายความถึงการเข้าถึง Edge อย่างรวดเร็ว และที่นี่ Associative Adjacency Array ก็เข้ามาช่วยเหลือ ซึ่งจะกล่าวถึงด้านล่างนี้
3.2 อาร์เรย์คำคุณศัพท์แบบเชื่อมโยง
ดังนั้น หากการเข้าถึงขอบที่เฉพาะเจาะจง น้ำหนักของมัน และคุณสมบัติอื่นๆ เป็นสิ่งสำคัญสำหรับเรา และข้อกำหนดหน่วยความจำไม่อนุญาตให้เราใช้เมทริกซ์ adjacency ลองคิดดูว่าเราจะเปลี่ยนเวกเตอร์ adjacency เพื่อแก้ไขปัญหานี้ได้อย่างไร ดังนั้น คีย์คือขอบของกราฟ ซึ่งสามารถระบุเป็นคู่ของจำนวนเต็มที่เรียงลำดับได้ สิ่งนี้มีลักษณะอย่างไร? มันไม่ใช่คีย์ในอาเรย์ที่เชื่อมโยงใช่ไหม และถ้าเป็นเช่นนั้นทำไมเราไม่ดำเนินการดังกล่าว? ขอให้เรามีอาร์เรย์ที่เชื่อมโยงโดยแต่ละคีย์ - คู่จำนวนเต็มที่เรียงลำดับ - จะเชื่อมโยงกับค่า - จำนวนเต็มหรือจำนวนจริงที่ระบุน้ำหนักของขอบ ใน C++ ขอแนะนำให้ใช้โครงสร้างนี้โดยยึดตามคอนเทนเนอร์ std::map (std::map , int> หรือ std::map , double>) หรือ std::multimap หากคาดว่าจะมีหลายขอบ เรามีโครงสร้างสำหรับจัดเก็บกราฟที่ใช้หน่วยความจำน้อยกว่าโครงสร้าง "เมทริกซ์" สามารถกำหนดกราฟที่มีหลายลูปและขอบ และไม่มีข้อกำหนดที่เข้มงวดสำหรับการไม่เป็นลบของตัวเลขจุดยอด (ฉันไม่รู้ด้วยซ้ำ ใครต้องการสิ่งนี้ แต่ก็ยัง)
4. โครงสร้างข้อมูลเต็ม แต่มีบางอย่างขาดหายไป
และเป็นเรื่องจริง: เมื่อแก้ไขปัญหาหลายๆ ปัญหา เราอาจจำเป็นต้องกำหนดคุณลักษณะบางอย่างให้กับขอบของกราฟ แล้วจึงจัดเก็บไว้ตามนั้น หากเป็นไปได้ที่จะลดคุณสมบัติเหล่านี้เป็นจำนวนเต็มอย่างไม่น่าสงสัย ก็เป็นไปได้ที่จะจัดเก็บ "กราฟที่มีคุณสมบัติเพิ่มเติม" ดังกล่าวโดยใช้เวอร์ชันขยายของเวกเตอร์ adjacency และอาเรย์ adjacency แบบเชื่อมโยง
ดังนั้น ขอให้เรามีกราฟแบบไม่ถ่วงน้ำหนัก สำหรับแต่ละขอบซึ่งจำเป็นต้องจัดเก็บ เช่น คุณลักษณะเพิ่มเติม 2 รายการที่ระบุด้วยจำนวนเต็ม ในกรณีนี้ มีความเป็นไปได้ที่จะนิยามเวกเตอร์ adjacency ให้เป็นเซตลำดับไม่ใช่ "คู่" แต่เป็น "ควอร์เตต" ของจำนวนเต็ม (a[2i], a[2i+1], a[2i+2], a [2i+3]…) โดยที่ a[2i+2] และ a[2i+3] จะกำหนดลักษณะของขอบที่สอดคล้องกัน สำหรับกราฟที่มีน้ำหนักจำนวนเต็มของขอบ โดยทั่วไปลำดับจะคล้ายกัน (ข้อแตกต่างเพียงอย่างเดียวคือคุณลักษณะจะตามน้ำหนักของขอบ และจะถูกระบุโดยองค์ประกอบ a[2i+3] และ a[2i+4] และตัวขอบจะระบุไม่ใช่ 4 แต่เป็นหมายเลขลำดับ 5) และสำหรับกราฟที่มีน้ำหนักขอบที่ไม่ใช่จำนวนเต็ม สามารถเขียนจุดสนใจลงในองค์ประกอบที่ไม่มีการถ่วงน้ำหนักได้
เมื่อใช้อาร์เรย์ adjacency แบบเชื่อมโยงสำหรับกราฟที่มีน้ำหนักขอบเป็นจำนวนเต็ม คุณสามารถระบุเป็นค่าไม่ใช่ตัวเลขตัวเดียว แต่เป็นอาร์เรย์ (เวกเตอร์) ของตัวเลขที่ระบุ นอกเหนือจากน้ำหนักของขอบ แล้ว ยังระบุอื่นๆ ทั้งหมดที่จำเป็น คุณสมบัติ. ขณะเดียวกัน ความไม่สะดวกสำหรับกรณีน้ำหนักที่ไม่ใช่จำนวนเต็มคือต้องระบุเครื่องหมายที่มีเลขทศนิยม (ใช่ ไม่สะดวก แต่ถ้ามีเครื่องหมายดังกล่าวไม่มากนัก และหากไม่ อย่าตั้งให้ "ยุ่งยาก" เป็นสองเท่าเกินไป มันอาจจะไม่มีอะไรเลย) ซึ่งหมายความว่าในอาร์เรย์ adjacency ที่เชื่อมโยงแบบขยาย C++ สามารถกำหนดได้ดังนี้: std::map , std::vector> หรือ std::map , std::vector โดยที่ค่าแรกใน "คีย์-ค่า-เวกเตอร์" จะเป็นน้ำหนักของขอบ จากนั้นจึงระบุการกำหนดลักษณะตัวเลขเป็นตัวเลข
วรรณกรรม:
เกี่ยวกับกราฟและอัลกอริธึมโดยทั่วไป:
1. คอร์เมน, โธมัส เอช., ไลเซอร์สัน, ชาร์ลส ไอ., ริเวสต์, โรนัลด์ แอล., สไตน์, คลิฟฟอร์ด อัลกอริทึม: โครงสร้างและการวิเคราะห์ ฉบับพิมพ์ครั้งที่ 2: ทรานส์ จากอังกฤษ – อ.: สำนักพิมพ์วิลเลียมส์, 2011.
2. ฮารารี แฟรงค์ ทฤษฎีกราฟ อ.: มีร์, 1973.
รายงานของผู้เขียนเกี่ยวกับเวกเตอร์และอาร์เรย์ที่เชื่อมโยงเดียวกันเหล่านี้ของ adjacencies:
3. เชอร์นูคอฟ เอส.เอ. เวกเตอร์คำประชิดและอาร์เรย์คำประชิดแบบเชื่อมโยงเป็นวิธีการแสดงและจัดเก็บกราฟ / SA Chernouhov แผนที่เวกเตอร์และคำใกล้เคียงกันเป็นโครงสร้างข้อมูลเพื่อแสดงกราฟ // การรวบรวมบทความของการประชุมทางวิทยาศาสตร์และการปฏิบัติระหว่างประเทศ “ปัญหาในการใช้ผลลัพธ์ของการพัฒนานวัตกรรมและวิธีการแก้ไข” (Saratov, 14.09.2019 กันยายน 2019) – สเตอร์ลิตามัก: AMI, 65, หน้า. 69-XNUMX
แหล่งข้อมูลออนไลน์ที่เป็นประโยชน์ในหัวข้อ:
4.
5.
ที่มา: will.com