ในวิทยาการคอมพิวเตอร์การเรียงลำดับเชิงโทโพโลยีหรือการเรียงลำดับเชิงโทโพโลยีของกราฟ แบบมีทิศทาง คือการเรียงลำดับเชิง เส้น ของจุดยอด ของกราฟ โดยที่สำหรับทุกขอบแบบมีทิศทาง(u,v)จากจุดยอดuไปยังจุดยอดv จุดยอด uจะอยู่ก่อน จุดยอด vในลำดับ ตัวอย่างเช่น จุดยอดของกราฟอาจแทนภารกิจที่จะต้องทำ และขอบอาจแทนข้อจำกัดที่ว่าภารกิจหนึ่งต้องทำก่อนอีกภารกิจหนึ่ง ในแอปพลิเคชันนี้ การเรียงลำดับเชิงโทโพโลยีเป็นเพียงลำดับที่ถูกต้องสำหรับภารกิจเหล่านั้น

กล่าวโดยละเอียด การเรียงลำดับเชิงทอพอโลยีคือการท่องกราฟที่แต่ละโหนดv จะถูกเยี่ยมชมก็ ต่อเมื่อโหนดที่เกี่ยวข้องทั้งหมดถูกเยี่ยมชมแล้วเท่านั้นการเรียงลำดับเชิงทอพอโลยีเป็นไปได้ก็ต่อเมื่อกราฟไม่มีวงจรแบบมีทิศทางนั่นคือ ถ้าเป็นกราฟแบบมีทิศทางที่ไม่มีวงจร (DAG) DAG ทุกตัวมีการเรียงลำดับเชิงทอพอโลยีอย่างน้อยหนึ่งแบบ และมี อัลกอริธึมแบบใช้เวลาเชิงเส้น ในการสร้าง การเรียงลำดับเชิงทอพอโลยีมีการใช้งานมากมาย โดยเฉพาะอย่างยิ่งในปัญหาการจัดอันดับ เช่นชุดส่วนโค้งป้อนกลับการเรียงลำดับเชิงทอพอโลยียังเป็นไปได้แม้ว่า DAG จะมีส่วนประกอบที่ไม่เชื่อมต่อกันก็ตาม

การประยุกต์ใช้การเรียงลำดับเชิงโทโพโลยีที่เป็นแบบอย่างคือการจัดตารางลำดับงานหรือภารกิจโดยพิจารณาจากความสัมพันธ์ ระหว่างกัน งานต่างๆ จะถูกแทนด้วยจุดยอด และจะมีเส้นเชื่อมจากxไปยังyหากงานxต้องเสร็จสมบูรณ์ก่อนที่งานyจะสามารถเริ่มต้นได้ (ตัวอย่างเช่น เมื่อซักผ้า เครื่องซักผ้าต้องเสร็จก่อนที่เราจะนำผ้าไปใส่ในเครื่องอบผ้า) จากนั้น การเรียงลำดับเชิงโทโพโลยีจะให้ลำดับในการดำเนินการงานต่างๆ การประยุกต์ใช้ที่เกี่ยวข้องอย่างใกล้ชิดของอัลกอริธึมการเรียงลำดับเชิงโทโพโลยีได้รับการศึกษาครั้งแรกในช่วงต้นทศวรรษ 1960 ในบริบทของ เทคนิค PERTสำหรับการจัดตารางเวลาในการจัดการโครงการ^{[ 1 ]}ในการประยุกต์ใช้นี้ จุดยอดของกราฟแสดงถึงเหตุการณ์สำคัญของโครงการ และเส้นเชื่อมแสดงถึงภารกิจที่ต้องดำเนินการระหว่างเหตุการณ์สำคัญหนึ่งกับอีกเหตุการณ์สำคัญหนึ่ง การเรียงลำดับเชิงโทโพโลยีเป็นพื้นฐานของอัลกอริธึมแบบเชิงเส้นสำหรับการค้นหาเส้นทางวิกฤตของโครงการ ซึ่งเป็นลำดับของเหตุการณ์สำคัญและภารกิจที่ควบคุมความยาวของตารางเวลาโครงการโดยรวม

ในวิทยาการคอมพิวเตอร์ การประยุกต์ใช้งานประเภทนี้เกิดขึ้นในการจัดตารางคำสั่ง การจัดลำดับการประเมินค่าเซลล์สูตรเมื่อคำนวณค่าสูตรใหม่ในสเปรดชีตการสังเคราะห์ตรรกะการกำหนดลำดับของงานคอมไพล์ที่จะดำเนินการในไฟล์ makefile การจัดเรียงข้อมูลและการแก้ไขการพึ่งพาของสัญลักษณ์ในลิงเกอร์นอกจากนี้ยังใช้ในการตัดสินใจว่าจะโหลดตารางที่มีคีย์ต่างประเทศในฐานข้อมูลในลำดับใด

โดยทั่วไปแล้ว อัลกอริทึมสำหรับการเรียงลำดับเชิงโทโพโลยีจะมีเวลาในการทำงานเป็นเชิงเส้นกับจำนวนโหนดบวกกับจำนวนขอบ ในทางสถิติเชิงอะซิมโทติก${\displaystyle O(\left|{V}\right|+\left|{E}\right|).}$

หนึ่งในอัลกอริทึมเหล่านี้ ซึ่งอธิบายครั้งแรกโดยKahn (1962)ทำงานโดยการเลือกจุดยอดในลำดับเดียวกับการเรียงลำดับเชิงโทโพโลยีในที่สุด^{[ 2 ]}ขั้นแรก ให้ค้นหารายชื่อ "โหนดเริ่มต้น" ที่ไม่มีขอบขาเข้าและแทรกเข้าไปในเซต S อย่างน้อยหนึ่งโหนดดังกล่าวจะต้องมีอยู่ในกราฟอะไซเคิลที่ไม่ว่างเปล่า (จำกัด) จากนั้น:

L ← รายการว่างที่จะบรรจุองค์ประกอบที่เรียงลำดับแล้ว S ← เซตของโหนดทั้งหมดที่ไม่มีเส้นเชื่อมขาเข้า ในขณะที่S ยังไม่ว่างเปล่า ให้ ลบโหนดn ออก จากS แล้วเพิ่มnลงในL สำหรับแต่ละโหนดmที่มีขอบeจากnไปยังm ให้ ลบขอบe ออก จากกราฟ ถ้าmไม่มีขอบขาเข้าอื่นให้ แทรก m ลงในSถ้ากราฟมีเส้นเชื่อมให้ส่งคืนข้อผิดพลาด (กราฟมีวงจรอย่างน้อยหนึ่งวง) มิเช่นนั้นให้ส่งคืนL (ลำดับที่เรียงตามลำดับโทโพโลยี)

ถ้ากราฟเป็นDAG ( Directed Aggregate) คำตอบจะอยู่ในรายการ L (ถึงแม้ว่าคำตอบนั้นอาจไม่จำเป็นต้องเป็นคำตอบเดียว) มิเช่นนั้น กราฟจะต้องมีวงจรอย่างน้อยหนึ่งวง และด้วยเหตุนี้จึงไม่สามารถเรียงลำดับเชิงทอพอโลยีได้

เนื่องจากผลลัพธ์ของการเรียงลำดับนั้นไม่ซ้ำกัน โครงสร้าง S จึงอาจเป็นเพียงเซต คิว หรือสแต็กก็ได้ ขึ้นอยู่กับลำดับที่นำโหนด n ออกจากเซต S จะได้ผลลัพธ์ที่แตกต่างกันไป อัลกอริทึมของ Kahn ที่ใช้ลำดับตัวอักษรในการแก้ปัญหาความเสมอภาคเป็นส่วนประกอบสำคัญของอัลกอริทึม Coffman–Grahamสำหรับการจัดตารางงานแบบขนานและ การ วาด กราฟแบบหลายชั้น

อัลกอริทึมทางเลือกสำหรับการเรียงลำดับเชิงโทโพโลยีคืออัลกอริทึมที่ใช้ การค้นหาแบบเจาะ ลึก (depth-first search ) อัลกอริทึมนี้จะวนลูปผ่านแต่ละโหนดของกราฟในลำดับที่กำหนด โดยเริ่มการค้นหาแบบเจาะลึกซึ่งจะสิ้นสุดลงเมื่อพบโหนดใดๆ ที่เคยถูกเยี่ยมชมมาแล้วตั้งแต่เริ่มต้นการเรียงลำดับเชิงโทโพโลยี หรือโหนดนั้นไม่มีขอบขาออก (เช่น โหนดใบ)

L ← รายการว่างที่จะมีโหนดที่เรียงลำดับแล้ว ในขณะที่มีโหนดที่ไม่มีเครื่องหมายถาวรให้ เลือกโหนดที่ไม่มีเครื่องหมายn เยี่ยมชม( n ) ฟังก์ชัน visit(node ​​n ) ถ้าnมีเครื่องหมายถาวรให้ส่งคืนค่าถ้าnมีเครื่องหมายชั่วคราวให้หยุด(กราฟมีวงจรอย่างน้อยหนึ่งวง) ทำเครื่องหมายnด้วยเครื่องหมายชั่วคราว สำหรับแต่ละโหนดmที่มีเส้นเชื่อมจากnไปยังm ให้ไป เยี่ยมชม ( m ) ทำเครื่องหมายnด้วยเครื่องหมายถาวร เพิ่มnต่อท้ายL

แต่ละโหนดnจะถูกเพิ่มเข้าไปในรายการเอาต์พุต L ก็ต่อเมื่อพิจารณาโหนดอื่นๆ ทั้งหมดที่ขึ้นอยู่กับn (ลูกหลานทั้งหมดของnในกราฟ) โดยเฉพาะอย่างยิ่ง เมื่ออัลกอริทึมเพิ่มโหนดnเราจะมั่นใจได้ว่าโหนดทั้งหมดที่ขึ้นอยู่กับnอยู่ในรายการเอาต์พุต L แล้ว: พวกมันถูกเพิ่มเข้าไปใน L โดยการเรียกซ้ำของ visit() ที่สิ้นสุดก่อนการเรียก visit nหรือโดยการเรียก visit() ที่เริ่มต้นก่อนการเรียก visit n เสียอีก เนื่องจากแต่ละขอบและโหนดถูกเยี่ยมชมเพียงครั้งเดียว อัลกอริทึมจึงทำงานในเวลาเชิงเส้น อัลกอริทึมการค้นหาแบบเจาะลึกนี้เป็นอัลกอริทึมที่อธิบายโดยCormen et al. (2001) [ ^{3 ]}ดูเหมือนว่าจะได้รับการอธิบายครั้งแรกในสิ่งพิมพ์โดย Tarjan ในปี^{1976 [ 4 ]}

บนเครื่องเข้าถึงแบบสุ่มขนานสามารถสร้างลำดับเชิงโทโพโลยีได้ใน เวลา O ((log n ) ² ) โดยใช้โปรเซสเซอร์จำนวนพหุนาม ทำให้ปัญหานี้อยู่ในระดับความซับซ้อนNC ^{2 [ 5 ]} วิธีหนึ่งในการทำเช่นนี้คือการยกกำลังสองเมทริกซ์ประชิดของกราฟที่กำหนดซ้ำๆ เป็นจำนวนครั้งตามลอการิทึม โดยใช้การคูณเมทริกซ์แบบ min-plusโดยเพิ่มค่าสูงสุดแทนการลดค่าต่ำสุด เมทริกซ์ที่ได้จะอธิบายระยะ ทาง เส้นทางที่ยาวที่สุดในกราฟ การเรียงลำดับจุดยอดตามความยาวของเส้นทางขาเข้าที่ยาวที่สุดจะสร้างลำดับเชิงโทโพโลยี^{[ 6 ]}

อัลกอริทึมสำหรับการเรียงลำดับเชิงโทโพโลยีแบบขนานบนเครื่องหน่วยความจำแบบกระจาย จะทำการขนานอัลกอริทึมของ Kahn สำหรับ DAG ^{[ 7 ]}โดยทั่วไปแล้ว อัลกอริทึมของ Kahn จะลบจุดยอดที่มีดีกรีขาเข้า 0 ซ้ำๆ และเพิ่มจุดยอดเหล่านั้นลงในการเรียงลำดับเชิงโทโพโลยีตามลำดับที่ถูกลบออก เนื่องจากขอบขาออกของจุดยอดที่ถูกลบออกก็ถูกลบออกด้วยเช่นกัน จึงจะมีชุดจุดยอดใหม่ที่มีดีกรีขาเข้า 0 ซึ่งขั้นตอนจะทำซ้ำไปเรื่อยๆ จนกว่าจะไม่มีจุดยอดเหลืออยู่ อัลกอริทึมนี้จะทำการวนซ้ำ โดยที่Dคือเส้นทางที่ยาวที่สุดในGแต่ละรอบการวนซ้ำสามารถทำแบบขนานได้ ซึ่งเป็นแนวคิดของอัลกอริทึมต่อไปนี้ ${\displaystyle G=(V,E)}$${\displaystyle D+1}$

ต่อไปนี้ สมมติว่าการแบ่งส่วนกราฟถูกจัดเก็บไว้ใน หน่วยประมวลผล (PE) จำนวน pหน่วย ซึ่งมีป้ายกำกับเป็นi แต่ละ PE iจะเริ่มต้นชุดของจุดยอดเฉพาะที่ด้วยดีกรีขาเข้า 0 โดยที่ดัชนีบนสุดแสดงถึงการวนซ้ำปัจจุบัน เนื่องจากจุดยอดทั้งหมดในชุดเฉพาะที่มีดีกรีขาเข้า 0 กล่าวคือ จุดยอดเหล่านั้นไม่ได้อยู่ติดกัน ดังนั้นจึงสามารถกำหนดลำดับใดก็ได้สำหรับการเรียงลำดับเชิงโทโพโลยีที่ถูกต้อง ในการกำหนดดัชนีทั่วโลกให้กับแต่ละจุดยอด จะมีการคำนวณ ผลรวมนำหน้าตามขนาดของi ดังนั้นในแต่ละขั้นตอน จะมีการเพิ่มจุดยอดจำนวน i จุดลงในการเรียง ลำดับเชิงโทโพโลยี${\displaystyle 0,\dots ,p-1}$${\displaystyle Q_{i}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$

ในขั้นตอนแรก PE jจะกำหนดดัชนีให้กับจุดยอดภายในใน จุดยอดเหล่านี้ในจะถูกลบออก พร้อมกับขอบขาออกที่เกี่ยวข้อง สำหรับแต่ละขอบขาออกที่มีจุดปลายvอยู่ใน PE อื่นข้อความจะถูกส่งไปยัง PE lหลังจากที่จุดยอดทั้งหมดในถูกลบออกแล้ว ข้อความที่ส่งไปจะถูกส่งไปยัง PE ที่เกี่ยวข้อง ข้อความที่ได้รับแต่ละข้อความจะอัปเดตค่า indegree ของจุดยอดภายในvหากค่า indegree ลดลงเหลือศูนย์vจะถูกเพิ่มเข้าไปในจากนั้นการวนซ้ำครั้งต่อไปจะเริ่มต้นขึ้น ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$${\displaystyle Q_{j}^{1}}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle l,j\neq l}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{2}}$

ในขั้นตอนk , PE jจะกำหนดดัชนีโดยที่ คือจำนวนจุดยอดทั้งหมดที่ประมวลผลแล้วหลังจากขั้นตอน⁠ ⁠กระบวนการนี้จะทำซ้ำจนกว่าจะไม่มีจุดยอดเหลือให้ประมวลผล ดังนั้นด้านล่างนี้คือภาพรวมรหัสเทียมระดับสูง ของ โปรแกรมเดียวสำหรับข้อมูลหลายชุดของอัลกอริทึมนี้ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$${\displaystyle a_{k-1}}$${\displaystyle k-1}$${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$

โปรดทราบว่าผลรวมนำหน้าสำหรับค่าชดเชยเฉพาะที่สามารถคำนวณได้อย่างมีประสิทธิภาพในแบบขนาน ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$

องค์ประกอบการประมวลผล pตัวที่มี ID ตั้งแต่ 0 ถึงp - 1 อินพุต: G = (V, E) DAG ที่กระจายไปยัง PE โดยดัชนี PE j = 0, ..., p - 1 เอาต์พุต:การเรียงลำดับเชิงโทโพโลยีของ G ฟังก์ชัน traverseDAGDistributed δ ดีกรีขาเข้าของจุดยอดท้องถิ่นV Q = { v ∈ V | δ[ v ] = 0} // จุดยอดทั้งหมดที่มีดีกรีขาเข้าเป็น 0 จำนวนจุดยอดที่ประมวลผล = 0 ทำการ สร้างผลรวมคำนำหน้า ทั่วโลกตามขนาดของQ // รับค่าออฟเซ็ตและจำนวนจุดยอดทั้งหมดในขั้นตอนนี้ offset = nrOfVerticesProcessed + sum(Q i , i = 0 to j - 1) // jคือดัชนีของโปรเซสเซอร์ สำหรับแต่ละ u ใน Q localOrder[u] = index++; foreach (u,v) in E do post message ( u, v ) to PE owning vertex v nrOfVerticesProcessed += sum(|Q i |, i = 0 to p - 1) ส่งข้อความทั้งหมดไปยังเพื่อนบ้านของจุดยอดใน Q รับข้อความสำหรับจุดยอดท้องถิ่น V ลบจุดยอดทั้งหมดใน Q สำหรับแต่ละข้อความ ( u, v ) ที่ได้รับ: ถ้า --δ[v] = 0 เพิ่มvลงในQ ในขณะที่ขนาดโดยรวมของQ > 0 ส่งคืนคำสั่งซื้อในท้องถิ่น 

ต้นทุนการสื่อสารขึ้นอยู่กับการแบ่งกราฟที่กำหนดอย่างมาก สำหรับเวลาในการทำงาน บน โมเดล CRCW-PRAMที่อนุญาตให้ดึงและลดค่าในเวลาคงที่ อัลกอริทึมนี้จะทำงานในโดยที่Dคือเส้นทางที่ยาวที่สุดในGและΔคือระดับสูงสุด^{[ 7 ]}${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

การเรียงลำดับเชิงโทโพโลยียังสามารถใช้ในการคำนวณเส้นทางที่สั้นที่สุดผ่านกราฟทิศทางแบบไม่มีวงจรที่มีน้ำหนักได้ อย่างรวดเร็ว ให้ Vเป็นรายการของจุดยอดในกราฟดังกล่าวตามลำดับเชิงโทโพโลยี จากนั้นอัลกอริทึมต่อไปนี้จะคำนวณเส้นทางที่สั้นที่สุดจากจุดยอดต้นทางsไปยังจุดยอดอื่นๆ ทั้งหมด: ^{[ 3 ]}

ในทำนองเดียวกัน:

บนกราฟที่มี จุดยอด nจุดและขอบm เส้น อัลกอริทึมนี้ใช้เวลา Θ( n + m )กล่าวคือเวลาเชิงเส้น^{[ 3 ]}

ถ้าการเรียงลำดับเชิงโทโพโลยีมีคุณสมบัติที่ว่าคู่ของจุดยอดที่อยู่ติดกันทั้งหมดในลำดับที่เรียงแล้วเชื่อมต่อกันด้วยขอบ ขอบเหล่านั้นจะสร้างเส้นทางแฮมิลโทเนียน แบบมีทิศทาง ในDAGถ้ามีเส้นทางแฮมิลโทเนียนอยู่ ลำดับการเรียงลำดับเชิงโทโพโลยีจะเป็นเอกลักษณ์ ไม่มีลำดับอื่นใดที่เคารพขอบของเส้นทาง ในทางกลับกัน ถ้าการเรียงลำดับเชิงโทโพโลยีไม่สร้างเส้นทางแฮมิลโทเนียน DAG จะมีลำดับเชิงโทโพโลยีที่ถูกต้องสองลำดับขึ้นไป เพราะในกรณีนี้ สามารถสร้างลำดับที่ถูกต้องลำดับที่สองได้เสมอโดยการสลับจุดยอดที่อยู่ติดกันสองจุดที่ไม่ได้เชื่อมต่อกันด้วยขอบ ดังนั้นจึงสามารถทดสอบได้ในเวลาเชิงเส้นว่ามีลำดับที่เป็นเอกลักษณ์หรือไม่ และมีเส้นทางแฮมิลโทเนียนอยู่หรือไม่ แม้ว่า ปัญหาเส้นทางแฮมิลโทเนียนจะเป็นปัญหา NP-hardสำหรับกราฟแบบมีทิศทางทั่วไป (เช่น กราฟแบบมีทิศทางแบบวัฏจักร) ^{[ 8 ]}

ลำดับเชิงทอพอโลยีมีความเกี่ยวข้องอย่างใกล้ชิดกับแนวคิดของการขยายเชิงเส้นของลำดับบางส่วนในทางคณิตศาสตร์ เซตที่มีลำดับบางส่วนเป็นเพียงเซตของวัตถุพร้อมกับนิยามของความสัมพันธ์อสมการ "≤" ซึ่งสอดคล้องกับสัจพจน์ของการสะท้อน ( x  ≤  x ) การสมมาตรแบบผกผัน (ถ้าx  ≤  yและy  ≤  xแล้วx  =  y ) และการถ่ายทอด (ถ้าx  ≤  yและy  ≤  zแล้วx  ≤  z ) ลำดับสมบูรณ์คือลำดับบางส่วนซึ่งสำหรับวัตถุสองชิ้นxและy ใดๆ ในเซตนั้นx  ≤  yหรือy  ≤  xลำดับสมบูรณ์เป็นที่คุ้นเคยในวิทยาศาสตร์คอมพิวเตอร์ในฐานะตัวดำเนินการเปรียบเทียบที่จำเป็นสำหรับการดำเนินการ อัลกอริทึม การเรียงลำดับแบบเปรียบเทียบสำหรับเซตจำกัด ลำดับสมบูรณ์อาจถูกระบุด้วยลำดับเชิงเส้นของวัตถุ โดยที่ความสัมพันธ์ "≤" เป็นจริงเมื่อใดก็ตามที่วัตถุแรกอยู่ก่อนวัตถุที่สองในลำดับ อัลกอริทึมการเรียงลำดับแบบเปรียบเทียบอาจใช้เพื่อแปลงลำดับสมบูรณ์เป็นลำดับในลักษณะนี้ การขยายเชิงเส้นของลำดับบางส่วนคือลำดับทั้งหมดที่เข้ากันได้กับลำดับบางส่วน ในแง่ที่ว่า ถ้าx  ≤  yในลำดับบางส่วนแล้ว x  ≤  yในลำดับทั้งหมดด้วยเช่นกัน

เราสามารถกำหนดลำดับบางส่วนจาก DAG ใดๆ ได้โดยให้เซตของวัตถุเป็นจุดยอดของ DAG และกำหนดให้x  ≤  yเป็นจริงสำหรับจุดยอดxและy ใดๆ เมื่อใดก็ตามที่มีเส้นทางทิศทางจากxไปยังyนั่นคือ เมื่อใดก็ตามที่yสามารถเข้าถึงได้จากxด้วยคำจำกัดความเหล่านี้ ลำดับเชิงโทโพโลยีของ DAG จึงเหมือนกับการขยายเชิงเส้นของลำดับบางส่วนนี้ ในทางกลับกัน ลำดับบางส่วนใดๆ ก็สามารถกำหนดได้ว่าเป็นความสัมพันธ์ของการเข้าถึงได้ใน DAG วิธีหนึ่งในการทำเช่นนี้คือการกำหนด DAG ที่มีจุดยอดสำหรับวัตถุทุกชิ้นในเซตที่มีลำดับบางส่วน และมีขอบxyสำหรับวัตถุทุกคู่ที่x  ≤  yอีกวิธีหนึ่งในการทำเช่นนี้คือการใช้การลดแบบถ่ายทอดของลำดับบางส่วน โดยทั่วไปแล้ว วิธีนี้จะสร้าง DAG ที่มีขอบน้อยลง แต่ความสัมพันธ์ของการเข้าถึงได้ใน DAG เหล่านี้ยังคงเป็นลำดับบางส่วนเดียวกัน โดยการใช้โครงสร้างเหล่านี้ เราสามารถใช้อัลกอริธึมการเรียงลำดับเชิงโทโพโลยีเพื่อค้นหาส่วนขยายเชิงเส้นของลำดับบางส่วนได้

ตามนิยามแล้ว วิธีแก้ปัญหาการจัดตารางเวลาที่รวมถึงกราฟลำดับความสำคัญถือเป็นวิธีแก้ปัญหาที่ถูกต้องสำหรับการเรียงลำดับเชิงโทโพโลยี (โดยไม่คำนึงถึงจำนวนเครื่องจักร) อย่างไรก็ตาม การเรียงลำดับเชิงโทโพโลยีเพียงอย่างเดียวไม่เพียงพอที่จะแก้ปัญหาการเพิ่มประสิทธิภาพการจัดตารางเวลาได้อย่างเหมาะสม อัลกอริทึมของ Hu เป็นวิธีการที่นิยมใช้ในการแก้ปัญหาการจัดตารางเวลาที่ต้องใช้กราฟลำดับความสำคัญและเกี่ยวข้องกับเวลาในการประมวลผล (โดยมีเป้าหมายคือการลดเวลาเสร็จสิ้นที่มากที่สุดในบรรดางานทั้งหมด) เช่นเดียวกับการเรียงลำดับเชิงโทโพโลยี อัลกอริทึมของ Hu ไม่ใช่วิธีเดียวและสามารถแก้ไขได้โดยใช้ DFS (โดยการหาความยาวเส้นทางที่มากที่สุดแล้วจึงกำหนดงาน)

• tsortโปรแกรม Unix สำหรับการเรียงลำดับเชิงโทโพโลยี
• ชุดเส้นโค้งป้อนกลับ (Feedback arc set ) คือชุดของขอบที่เมื่อลบออกแล้วจะทำให้กราฟย่อยที่เหลือสามารถเรียงลำดับตามโครงสร้างได้
• อัลกอริทึมส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาของ Tarjanเป็นอัลกอริทึมที่ให้รายการส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาในกราฟ โดยเรียงลำดับตามโครงสร้างทางโทโพโลยี
• ลำดับก่อนโทโพโลยี

• DE Knuth , The Art of Computer Programming , เล่ม 1, ส่วนที่ 2.2.3 ซึ่งนำเสนออัลกอริทึมสำหรับการเรียงลำดับเชิงโทโพโลยีของการเรียงลำดับบางส่วน และประวัติโดยย่อ
• Bertrand Meyer , Touch of Class: Learning to Program Well with Objects and Contracts , Springer , 2009, บทที่ 15, การคิดค้นและออกแบบอัลกอริทึม: การเรียงลำดับเชิงทอพอโลยีโดยใช้ภาษาโปรแกรมสมัยใหม่ เพื่อการนำเสนอเชิงการสอนโดยละเอียดเกี่ยวกับการเรียงลำดับเชิงทอพอโลยี (โดยใช้รูปแบบหนึ่งของอัลกอริทึมของ Kahn) โดยคำนึงถึงการออกแบบโครงสร้างข้อมูล การออกแบบ API และข้อกังวลด้านวิศวกรรมซอฟต์แวร์

• พจนานุกรมอัลกอริธึมและโครงสร้างข้อมูลของ NIST: การเรียงลำดับเชิงทอพอโลยี
• ไวส์สไตน์, เอริค ดับเบิลยู. , "การเรียงลำดับเชิงทอพอโลยี" , MathWorld