การหาเส้นทางของขอบทั้งหมดบนกราฟ

ฉันกำลังพยายามหาเส้นทางบนกราฟที่ครอบคลุมขอบทั้งหมด และสำรวจมันเพียงครั้งเดียว ซึ่งหมายความว่าจะมีจุด "สิ้นสุด" เพียงสองจุดเท่านั้น ซึ่งจะมีจำนวนโหนดที่ต่ออยู่เป็นจำนวนคี่ จุดสิ้นสุดเหล่านี้อาจมีขอบเชื่อมต่อหนึ่งอัน หรือเป็นส่วนหนึ่งของลูปและมีการเชื่อมต่อ 3 จุด

ดังนั้นในกรณีง่ายๆ ด้านล่าง ฉันต้องสำรวจโหนดตามลำดับ 1-2-3-4-5 (หรือ 5-4-3-2-1):

ในกรณีที่ซับซ้อนกว่าด้านล่างเส้นทางจะเป็น 1-2-3-4-2 (หรือ 1-2-4-3-2):

ด้านล่างนี้เป็นกราฟที่ถูกต้องด้วย โดยมีจุดสิ้นสุด 2 จุด: 1-2-4-3-2-5

ฉันพยายามค้นหาชื่อของอัลกอริทึมเพื่อแก้ไขปัญหานี้ และคิดว่ามันคือ "ปัญหาบุรุษไปรษณีย์จีน" แต่การนำสิ่งนี้ไปใช้ตามโค้ดที่ https://github.com/rkistner/chinese-postman/blob/master/postman.py ไม่ได้ให้ผลลัพธ์ที่ฉันคาดหวัง .

เส้นทาง Eulerian ดูเกือบจะเป็นสิ่งที่จำเป็น แต่ การใช้งานเครือข่ายx จะใช้ได้กับเครือข่ายแบบปิด (แบบวนซ้ำ) เท่านั้น

ฉันยังได้ดู Hamiltonian Path - และลองใช้ อัลกอริทึม networkx - แต่ประเภทกราฟ ไม่ได้รับการสนับสนุน

ตามหลักการแล้ว ฉันต้องการใช้ Python และ networkx เพื่อดำเนินการนี้ และอาจมีวิธีแก้ไขปัญหาง่ายๆ ที่เป็นส่วนหนึ่งของไลบรารีอยู่แล้ว แต่ดูเหมือนจะหาไม่พบ