กราฟอะไซคลิกแบบกำหนดทิศทาง
Directed Acyclic Graph (DAG) เป็นกราฟประเภทหนึ่งซึ่งเป็นไปไม่ได้ที่จะกลับมาที่โหนดเดิมโดยการเคลื่อนที่ผ่านขอบ
- Directed : หมายถึง ทิศทาง (ทิศทางเฉพาะ)
- Acyclic: หมายถึงไม่อยู่ในวงจร
- กราฟ : แผนภาพแสดงความสัมพันธ์ระหว่างปริมาณตัวแปร
ในทฤษฎีกราฟ กราฟคือโครงสร้างที่ประกอบด้วย โหนด ที่เชื่อมต่อกันด้วย ขอบ คุณสามารถมอง โหนดเป็นจุด และ ขอบเป็นเส้น ที่ลากจากจุดหนึ่งไปยังอีกจุดหนึ่ง
มีทิศทาง หมายความว่าขอบของกราฟเคลื่อนที่ไปในทิศทางเดียวเท่านั้น โดยที่ขอบในอนาคตจะขึ้นอยู่กับทิศทางก่อนหน้า
ตัวอย่างเช่น หากคุณสร้างกราฟขั้นตอนการปรุงอาหารและการรับประทานอาหารที่ประกอบด้วยข้าวและไก่ งานที่เกี่ยวข้องจะต้องได้รับ "การเรียงลำดับ" เชิงทอพอโลยี (หรือจัดเรียงตามทอพอโลยี) ก่อนที่คุณจะกินอาหารได้ คุณต้องเตรียมอาหารก่อน ดังนั้นขอบจะต้องมุ่งตั้งแต่การเตรียมอาหารไปจนถึงการกิน แต่ก่อนที่คุณจะเตรียมอาหารได้ คุณต้องซื้อวัตถุดิบเสียก่อน ดังนั้นขอบต้องเปลี่ยนจากงานก่อนหน้านี้ไปสู่งานทีหลังเสียก่อน สมมุติว่าซื้อข้าวในงานแยกจากไก่ ก็จะมีขอบ 2 ฝั่งสำหรับงานซื้อของที่ไม่เกี่ยวกัน แต่จะมาบรรจบกันที่งานเตรียมอาหาร
อะไซคลิก หมายความว่าเป็นไปไม่ได้ที่จะเริ่มที่จุดหนึ่งของกราฟแล้วกลับมาที่จุดนั้นโดยไปตามขอบ ในขณะที่วงจรกลับมายังจุดเริ่มต้นเดิมเหมือนวงกลม กราฟอะไซคลิกยังคงเคลื่อนที่ในทิศทางเชิงเส้นและไม่เคยวนกลับไปที่จุดเริ่มต้น หากต้องการดำเนินการต่อด้วยตัวอย่างก่อนหน้าของอาหารค่ำไก่กับข้าว คุณไม่สามารถเลื่อนกราฟจากการซื้อข้าวไปเป็นการเตรียมอาหารไปจนถึงการซื้อไก่ได้ เนื่องจากจะต้องย้อนกลับไปทั่วทั้งกราฟ เป็นไปไม่ได้ที่จะเตรียมไก่หากคุณยังไม่ได้ซื้อ
