การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS
เรียกใช้ DFS และใส่แต่ละโหนดลงสแตกหลังสำรวจเพื่อนบ้านครบแล้ว จากนั้นนำโหนดออกจากสแตกเพื่อสร้างลำดับเชิงทอพอโลยีที่ถูกต้อง
การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
แนวคิดการเรียงลำดับเชิงทอพอโลยีด้วย DFS
อัลกอริทึมการเรียงลำดับเชิงทอพอโลยีแบบคลาสสิกตัวที่สองใช้ DFS พร้อมการประมวลผลแบบหลังลำดับ หลังจากสำรวจโหนดข้างเคียงทั้งหมดของโหนดหนึ่ง (รวมถึงโหนดลูกหลานของโหนดเหล่านั้น) จนเสร็จสมบูรณ์แล้ว ให้ใส่โหนดนั้นลงในสแตก เมื่อประมวลผลโหนดทั้งหมดแล้ว ให้ pop จากสแตกเพื่ออ่านลำดับเชิงทอพอโลยี โหนดที่ถูกใส่ลงในสแตกหลังจากสำรวจสิ่งที่โหนดนั้นต้องพึ่งพาทั้งหมดแล้ว ย่อมมาเป็น อันดับแรก ในลำดับ ดังนั้นลำดับหลังที่ย้อนกลับจึงเป็นการเรียงลำดับเชิงทอพอโลยี
สัญชาตญาณเบื้องหลังลำดับหลัง
พิจารณากราฟการพึ่งพาซึ่งวิชา A ต้องเรียนวิชา B ก่อน เมื่อ DFS เยี่ยมชม A ระบบจะเรียกซ้ำเข้าไปที่ B ก่อน B ไม่มีวิชาที่ต้องเรียนก่อน จึงเสร็จสิ้นก่อนและถูกใส่ลงในสแตกก่อน จากนั้น A จึงเสร็จสิ้นและถูกใส่ลงในสแตก เมื่อ pop จากสแตก ผลลัพธ์จะให้ A อยู่ก่อน B แต่เราจะย้อนกลับลำดับในตอนท้าย จึงได้ B อยู่ก่อน A นั่นคือให้เรียน B ก่อน แล้วจึงเรียน A การใส่โหนดลงในสแตกตามลำดับหลังจะใส่สิ่งที่ต้องพึ่งพาก่อนสิ่งที่พึ่งพาสิ่งนั้น ดังนั้นสแตกที่ย้อนกลับจึงเป็นลำดับเชิงทอพอโลยีที่ถูกต้อง
DFS สามสีสำหรับตรวจจับวัฏจักร
ใช้สถานะสำหรับโหนดที่เยี่ยมชมแล้วสามสถานะ ได้แก่ WHITE (0) = ยังไม่เคยเยี่ยมชม, GREY (1) = กำลังประมวลผลอยู่ (อยู่ในสแตกการเรียกใช้ DFS) และ BLACK (2) = ประมวลผลเสร็จสมบูรณ์แล้ว เส้นเชื่อมย้อนกลับ ซึ่งเป็นเส้นเชื่อมไปยังโหนด GREY บ่งชี้ว่ามีวัฏจักร ส่วนเส้นเชื่อมไปยังโหนด BLACK ถือว่าปลอดภัย (เนื่องจากโหนดเหล่านั้นถูกสำรวจจนเสร็จสมบูรณ์แล้ว) วิธีการใช้สามสีนี้ตรวจจับวัฏจักรทั้งหมดในกราฟมีทิศทางได้อย่างถูกต้อง
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)การใช้งานการเรียงลำดับเชิงทอพอโลยีด้วย DFS แบบเต็มรูปแบบ
ใช้ DFS แบบเรียกซ้ำที่กำหนดสีให้โหนด ใส่โหนดลงในสแตกตามลำดับหลัง และคืนค่าเท็จเมื่อตรวจพบวัฏจักร หลังจากเยี่ยมชมโหนดทั้งหมดแล้ว สแตกที่ย้อนกลับจะให้ลำดับเชิงทอพอโลยี
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))DFS แบบวนซ้ำเพื่อหลีกเลี่ยงสแตกโอเวอร์โฟลว์
ขีดจำกัดการเรียกซ้ำของ Python (ค่าเริ่มต้นคือ 1000) เป็นข้อกังวลสำหรับกราฟขนาดใหญ่ การใช้ DFS แบบวนซ้ำร่วมกับสแตกที่สร้างขึ้นโดยตรงช่วยหลีกเลี่ยงปัญหานี้ เคล็ดลับคือ ให้ใส่ (node, False) ลงไปก่อน เมื่อ pop ออกมาพร้อมค่า False ให้ใส่ (node, True) ลงไป (หมายความว่า “จะกลับมาที่นี่หลังจากสำรวจเสร็จ”) จากนั้นใส่โหนดข้างเคียงที่ยังไม่เคยเยี่ยมชมทั้งหมดพร้อมค่า False เมื่อ pop ออกมาพร้อมค่า True ให้กำหนดสีเป็น BLACK และใส่โหนดนั้นลงในสแตกผลลัพธ์
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]การเปรียบเทียบ DFS กับอัลกอริทึมคาห์น
ทั้งสองวิธีใช้เวลา O(V + E) ความแตกต่างสำคัญคือ อัลกอริทึมคาห์น (BFS) จะสร้างโหนดตามลำดับที่สิ่งที่ต้องพึ่งพาเสร็จเร็วที่สุดโดยธรรมชาติ และตรวจจับวัฏจักรได้ง่ายกว่า (ตรวจสอบความยาว) ส่วน DFS แบบลำดับหลัง ทำงานแบบเรียกซ้ำและตรวจจับเส้นเชื่อมย้อนกลับได้โดยตรง ควรเลือกใช้อัลกอริทึมคาห์นเมื่อต้องการผลลัพธ์ตามลำดับไปข้างหน้าโดยไม่ต้องย้อนกลับลำดับ ส่วน DFS เหมาะเมื่อจำเป็นต้องใช้ลำดับหลังทั้งหมดเพื่อวัตถุประสงค์อื่น (เช่น การตรวจจับ SCC) ทั้งสองวิธีเป็นคำตอบที่ยอมรับได้ในการสัมภาษณ์งาน
ลำดับหลังบนต้นไม้เทียบกับ DAG
ในต้นไม้ ลำดับหลังจะเยี่ยมชมต้นไม้ย่อยด้านซ้าย → ต้นไม้ย่อยด้านขวา → ราก ส่วนใน DAG การเยี่ยมชมด้วย DFS ตามลำดับหลังจะเยี่ยมชมสิ่งที่โหนดหนึ่งต้องพึ่งพาทั้งหมดก่อนประมวลผลโหนดนั้นเอง ซึ่งเป็นแนวคิดเดียวกันที่ขยายไปสู่โหนดก่อนหน้าหลายโหนดและโครงสร้างกราฟที่กำหนดได้อย่างอิสระ รากของต้นไม้ DFS (โหนดเริ่มต้น) จะถูกใส่ลงในสแตกเป็นโหนดสุดท้ายในกลุ่มลูกหลานของตน จึงปรากฏเป็นโหนดแรกในสแตกที่ย้อนกลับ ซึ่งเป็นตำแหน่งเชิงทอพอโลยีที่ถูกต้องสำหรับโหนดที่ไม่มีโหนดก่อนหน้า
พจนานุกรมภาษาต่างดาว (LeetCode 269)
พจนานุกรมภาษาต่างดาว: กำหนดรายการคำศัพท์ในภาษาต่างดาวที่เรียงลำดับไว้ แล้วหาลำดับของอักขระ เปรียบเทียบคำที่อยู่ติดกันทีละอักขระเพื่อหาความแตกต่างจุดแรก ซึ่งจะให้เส้นเชื่อม c1 → c2 ที่หมายความว่า c1 มาก่อน c2 รวบรวมเส้นเชื่อมทั้งหมดแล้วใช้การเรียงลำดับเชิงทอพอโลยีเพื่อสร้างลำดับอักขระของภาษาต่างดาว หากมีวัฏจักร ลำดับนั้นจะไม่ถูกต้อง
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'การเรียงลำดับเชิงทอพอโลยีภายใต้ข้อจำกัด
โจทย์บางข้อขอให้สร้างการเรียงลำดับเชิงทอพอโลยีที่ตรงตามข้อจำกัดเพิ่มเติม เช่น ต้องรักษาลำดับสัมพัทธ์ของสมาชิกจากรายการเดิมไว้ ให้ผสานอัลกอริทึมคาห์นเข้ากับคิวลำดับความสำคัญแบบกำหนดเองหรือการเรียงลำดับล่วงหน้า โดยรักษาลำดับสัมพัทธ์เดิมของสมาชิกด้วยการเรียงลำดับแบบคงเสถียรภาพกับสมาชิกในคิวแต่ละขั้นตอน รูปแบบที่มีข้อจำกัดเหล่านี้ใช้ทดสอบความเข้าใจเชิงลึกเกี่ยวกับความยืดหยุ่นของอัลกอริทึม
การสังเกตโจทย์ที่เป็นปัญหาการเรียงลำดับเชิงทอพอโลยี
วลีสัญญาณในโจทย์สัมภาษณ์ที่บ่งชี้ว่าควรใช้การเรียงลำดับเชิงทอพอโลยี ได้แก่ “กำหนดสิ่งที่ต้องพึ่งพา”, “สิ่งที่ต้องทำก่อน”, “การจัดลำดับงาน”, “ลำดับการสร้าง”, “งานทั้งหมดจะเสร็จได้หรือไม่” และ “หาลำดับที่ถูกต้อง” หากโจทย์เกี่ยวข้องกับการจัดลำดับสิ่งของที่บางอย่างต้องมาก่อนอย่างอื่น ให้สร้างกราฟมีทิศทางแล้วใช้การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมคาห์นหรือ DFS การตรวจจับวัฏจักรมักเป็นข้อกำหนดเพิ่มเติมในโจทย์เดียวกัน
การเปรียบเทียบผลลัพธ์จาก DFS และอัลกอริทึมคาห์น
DFS และอัลกอริทึมคาห์นอาจสร้างลำดับเชิงทอพอโลยีที่ถูกต้องแตกต่างกันสำหรับกราฟเดียวกัน ทั้งสองลำดับถูกต้อง เพราะ DAG หนึ่งกราฟอาจมีลำดับเชิงทอพอโลยีที่ถูกต้องได้หลายแบบ ในการตรวจสอบความถูกต้อง ให้ตรวจว่าในทุกเส้นเชื่อม u → v ของกราฟนั้น u ปรากฏก่อน v ในลำดับผลลัพธ์ สำหรับโจทย์สัมภาษณ์ที่กำหนดลำดับเฉพาะ (เช่น ต้องการลำดับที่เล็กที่สุดตามพจนานุกรม) ให้ใช้อัลกอริทึมคาห์นร่วมกับมินฮีป เพราะ DFS แบบลำดับหลังไม่ได้สร้างลำดับที่เล็กที่สุดตามพจนานุกรมโดยธรรมชาติ
ตรวจสอบอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์เขียนโปรแกรมจากบทเรียนนี้
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า การเรียงลำดับเชิงทอพอโลยีด้วย DFS ตามลำดับหลังจะใส่โหนดลงในสแตกหลังจากสำรวจสิ่งที่โหนดนั้นต้องพึ่งพาทั้งหมดแล้ว, การกำหนดเครื่องหมายสามสี (WHITE/GREY/BLACK) ตรวจจับวัฏจักรผ่านเส้นเชื่อมย้อนกลับไปยังโหนด GREY และ การย้อนกลับสแตกตามลำดับหลังจะให้ลำดับเชิงทอพอโลยีที่ถูกต้อง ต่อไปเราจะนำการเรียงลำดับเชิงทอพอโลยีไปใช้โดยตรงกับโจทย์ตารางเรียน I และ II
คำถามที่พบบ่อย
บทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS”
เรียกใช้ DFS และใส่แต่ละโหนดลงสแตกหลังสำรวจเพื่อนบ้านครบแล้ว จากนั้นนำโหนดออกจากสแตกเพื่อสร้างลำดับเชิงทอพอโลยีที่ถูกต้อง คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- อัลกอริทึมของ Kahn: การเรียงลำดับเชิงทอพอโลยีด้วย BFS
- การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS
- ตารางเรียน I และ II
- องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju