การเรียงลำดับโทโพโลยี: Python, C++ ตัวอย่างอัลกอริทึม

อัลกอริธึมการเรียงลำดับทอพอโลยีคืออะไร?

การเรียงลำดับทอพอโลยีเรียกอีกอย่างว่าอัลกอริทึมของคาห์นและเป็นอัลกอริทึมการเรียงลำดับยอดนิยม การใช้กราฟกำกับเป็นอินพุต การเรียงลำดับทอพอโลยีจะเรียงลำดับโหนดเพื่อให้แต่ละโหนดปรากฏก่อนโหนดที่ชี้ไป

อัลกอริธึมนี้ใช้กับ DAG (Directed Acyclic Graph) เพื่อให้แต่ละโหนดปรากฏในอาร์เรย์ที่ได้รับคำสั่งก่อนที่โหนดอื่นทั้งหมดจะชี้ไป อัลกอริทึมนี้ปฏิบัติตามกฎบางอย่างซ้ำๆ จนกว่าการเรียงลำดับจะเสร็จสิ้น

เพื่อให้เข้าใจง่ายขึ้น ลองดูตัวอย่างต่อไปนี้:

ที่นี่เราจะเห็นได้ว่า "A" ไม่มีระดับ หมายถึงขอบที่ชี้ไปยังโหนด “B” และ “C” มีข้อกำหนดเบื้องต้นสำหรับโหนด “A” จากนั้น “E” มีข้อกำหนดเบื้องต้นสำหรับโหนด “D” และ “F” โหนดบางส่วนต้องอาศัยโหนดอื่น

นี่คือการแสดงกราฟด้านบนอีกรูปแบบหนึ่ง:

ดังนั้น เมื่อเราส่ง DAG (Directed Acyclic Graph) ไปยังการเรียงลำดับทอพอโลยี มันจะให้อาร์เรย์ที่มีการเรียงลำดับเชิงเส้นแก่เรา โดยที่องค์ประกอบแรกไม่มีการพึ่งพา

ตัวอย่างนี้แสดงกราฟที่มีวงจร:

ต่อไปนี้เป็นขั้นตอนในการดำเนินการนี้:

ขั้นตอน 1) ค้นหาโหนดที่มีขอบขาเข้าเป็นศูนย์ โหนดที่มีองศาเป็นศูนย์

ขั้นตอน 2) จัดเก็บโหนดที่มีระดับเป็นศูนย์ในคิวหรือสแต็ก และลบโหนดออกจากกราฟ

ขั้นตอน 3) จากนั้นลบขอบขาออกออกจากโหนดนั้น

นี่จะเป็นการลดจำนวนหน่วยเป็นองศาสำหรับโหนดถัดไป

การเรียงลำดับทอพอโลยีกำหนดให้โครงสร้างข้อมูลกราฟไม่มีวงจรใดๆ

กราฟจะถือเป็น DAG หากเป็นไปตามข้อกำหนดเหล่านี้:

• โหนดตั้งแต่หนึ่งโหนดขึ้นไปที่มีค่า indegree เป็นศูนย์
• กราฟไม่มีวงจรใดๆ

ตราบใดที่ยังมีโหนดในกราฟและกราฟยังคงเป็น DAG เราจะดำเนินการสามขั้นตอนข้างต้น มิฉะนั้น อัลกอริทึมจะตกอยู่ในการพึ่งพาแบบวนซ้ำ และอัลกอริทึมของ Kahn จะไม่สามารถค้นหาโหนดที่มีองศาเป็นศูนย์ได้

การเรียงลำดับโทโพโลยีทำงานอย่างไร

ที่นี่เราจะใช้ “อัลกอริทึมของคาห์น” สำหรับการเรียงลำดับแบบโทโพโลยี สมมติว่าเรามีกราฟดังต่อไปนี้:

ต่อไปนี้เป็นขั้นตอนสำหรับอัลกอริทึมของคาห์น:

ขั้นตอน 1) คำนวณ indegree หรือ incoming edge ของโหนดทั้งหมดในกราฟ

หมายเหตุ

• Indegree หมายถึงขอบที่ชี้ไปที่โหนด
• Outdegree หมายถึงขอบกำกับที่มาจากโหนด

นี่คือระดับ indegree และ outdegree ของกราฟด้านบน:

ขั้นตอน 2) ค้นหาโหนดที่มีองศาเป็นศูนย์หรือขอบขาเข้าเป็นศูนย์

โหนดที่มีค่า indegree เป็นศูนย์หมายความว่าไม่มีขอบใดมาทางโหนดนั้น โหนด “A” มีองศาเป็นศูนย์ ซึ่งหมายความว่าไม่มีขอบที่ชี้ไปที่โหนด “A”

ดังนั้นเราจะทำการดำเนินการดังต่อไปนี้:

• ลบโหนดนี้และขอบด้านนอก (ขอบขาออก)
• วางโหนดในคิวเพื่อสั่งซื้อ
• อัปเดตการนับในระดับของโหนดเพื่อนบ้านของ “A”

ขั้นตอน 3) เราจำเป็นต้องค้นหาโหนดที่มีค่าเป็นศูนย์ ในตัวอย่างนี้ “B” และ “C” มีระดับเป็นศูนย์

ที่นี่เราสามารถรับอย่างใดอย่างหนึ่งจากสองสิ่งนี้ ลองใช้ "B" แล้วลบออกจากกราฟ

จากนั้นอัพเดตค่า indegree ของโหนดอื่นๆ

หลังจากดำเนินการเหล่านี้แล้ว กราฟและคิวของเราจะมีลักษณะเหมือนต่อไปนี้:

ขั้นตอน 4) โหนด “C” ไม่มีขอบขาเข้า ดังนั้น เราจะลบโหนด “C” ออกจากกราฟแล้วดันเข้าไปในคิว

นอกจากนี้เรายังสามารถลบขอบที่ออกจาก “C” ได้

ตอนนี้กราฟของเราจะมีลักษณะดังนี้:

ขั้นตอน 5) เราจะเห็นได้ว่าโหนด "D" และ "F" มีระดับเป็นศูนย์ เราจะนำโหนดมาวางไว้ในคิว

เอาตัว “D” ออกมาก่อน จากนั้นการนับ indegree สำหรับโหนด “E” จะเป็น 1 ตอนนี้ จะไม่มีโหนดตั้งแต่ D ถึง E

เราจำเป็นต้องทำแบบเดียวกันสำหรับโหนด "F" ผลลัพธ์ของเราจะเป็นดังนี้:

ขั้นตอน 6) indegree (ขอบขาเข้า) และ outdegree (ขอบขาออก) ของโหนด “E” กลายเป็นศูนย์ ดังนั้นเราจึงปฏิบัติตามข้อกำหนดเบื้องต้นทั้งหมดสำหรับโหนด “E” แล้ว

ที่นี่เราใส่ "E" ที่ท้ายคิว ดังนั้นเราจึงไม่มีโหนดเหลืออยู่ ดังนั้นอัลกอริทึมจึงสิ้นสุดที่นี่

รหัสหลอกสำหรับการเรียงลำดับทอพอโลยี

นี่คือรหัสหลอกสำหรับการเรียงลำดับทอพอโลยีในขณะที่ใช้อัลกอริทึมของคาห์น

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

การเรียงลำดับทอพอโลยีสามารถนำไปใช้ได้โดยใช้ DFS (การค้นหาครั้งแรกเชิงลึก) วิธี. อย่างไรก็ตาม วิธีการนั้นเป็นวิธีการแบบเรียกซ้ำ อัลกอริธึมของคาห์นมีประสิทธิภาพมากกว่าวิธี DFS

C++ การดำเนินการเรียงลำดับทอพอโลยี

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

เอาท์พุต

0       1       2       3       5       4

Python การดำเนินการเรียงลำดับทอพอโลยี

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

เอาท์พุต

[0, 1, 2, 3, 5, 4]

กราฟวงจรของอัลกอริทึมการเรียงลำดับทอพอโลยี

ไม่สามารถเรียงลำดับกราฟที่มีวงจรทอพอโลยีได้ เนื่องจากกราฟแบบวนมีการขึ้นต่อกันในลักษณะเป็นวงจร

ตัวอย่างเช่น ตรวจสอบกราฟนี้:

กราฟนี้ไม่ใช่ DAG (Directed Acyclic Graph) เนื่องจาก A, B และ C สร้างวงจร หากคุณสังเกตเห็น ไม่มีโหนดใดที่มีค่าเป็นศูนย์

ตามอัลกอริทึมของคาห์น หากเราวิเคราะห์กราฟด้านบน:

• ค้นหาโหนดที่มีองศาเป็นศูนย์ (ไม่มีขอบที่เข้ามา)
• ลบโหนดนั้นออกจากกราฟแล้วดันไปที่คิว
  อย่างไรก็ตาม ในกราฟด้านบน ไม่มีโหนดที่มีองศาเป็นศูนย์ ทุกโหนดมีค่า in-degree มากกว่า 0
• ส่งคืนคิวว่าง เนื่องจากไม่พบโหนดที่มีหน่วยเป็นองศาเป็นศูนย์

เราสามารถตรวจจับวงจรโดยใช้การสั่งแบบโทโพโลยีด้วยขั้นตอนต่อไปนี้:

ขั้นตอน 1) ดำเนินการเรียงลำดับทอพอโลยี

ขั้นตอน 2) คำนวณจำนวนองค์ประกอบทั้งหมดในรายการเรียงลำดับตามทอพอโลยี

ขั้นตอน 3) หากจำนวนองค์ประกอบเท่ากับจำนวนจุดยอดทั้งหมด จะไม่มีวงจร

ขั้นตอน 4) หากไม่เท่ากับจำนวนจุดยอด แสดงว่ามีอย่างน้อยหนึ่งรอบในโครงสร้างข้อมูลกราฟที่กำหนด

การวิเคราะห์ความซับซ้อนของการเรียงลำดับแบบโทโพโลยี

ความซับซ้อนในอัลกอริทึมมีอยู่ 2 ประเภท ได้แก่

1. ความซับซ้อนของเวลา
2. ความซับซ้อนของอวกาศ

ความซับซ้อนเหล่านี้แสดงด้วยฟังก์ชันที่ทำให้เกิดความซับซ้อนโดยทั่วไป

ความซับซ้อนของเวลา: ความซับซ้อนของเวลาทั้งหมดจะเหมือนกันสำหรับการเรียงลำดับแบบโทโพโลยี มีสถานการณ์ที่แย่ที่สุด ปานกลาง และดีที่สุดสำหรับความซับซ้อนของเวลา

ความซับซ้อนของเวลาสำหรับการเรียงลำดับแบบโทโพโลยีคือ O(E + V) โดยที่ E หมายถึงจำนวนขอบในกราฟ และ V หมายถึงจำนวนจุดยอดในกราฟ

มาทำลายความซับซ้อนนี้กัน:

ขั้นตอน 1) ในตอนแรกเราจะคำนวณหน่วยองศาทั้งหมด ในการทำเช่นนั้น เราต้องผ่านขอบทั้งหมด และเริ่มแรก เราจะกำหนดจุดยอด V ในหน่วยองศาให้เป็นศูนย์ ดังนั้นขั้นตอนเพิ่มเติมที่เราดำเนินการเสร็จสิ้นจะเป็นดังนี้ โอ(วี+อี).

ขั้นตอน 2) เราจะค้นหาโหนดที่มีค่าเป็นศูนย์ เราจำเป็นต้องค้นหาจากเลข V ของจุดยอด ดังนั้นขั้นตอนที่เสร็จสิ้นจะเป็น โอ(วี).

ขั้นตอน 3) สำหรับแต่ละโหนดที่มีองศาเป็นศูนย์ เราจะลบโหนดนั้นและลดองศาลง การดำเนินการนี้สำหรับโหนดทั้งหมดจะใช้เวลา โอ(อี).

ขั้นตอน 4) สุดท้ายเราจะตรวจสอบว่ามีรอบหรือไม่ เราจะตรวจสอบว่าจำนวนองค์ประกอบทั้งหมดในอาร์เรย์ที่เรียงลำดับเท่ากับจำนวนโหนดทั้งหมดหรือไม่ มันจะต้องใช้เวลา O (1).

ดังนั้น เหล่านี้จึงเป็นความซับซ้อนของเวลาแต่ละขั้นตอนของการเรียงลำดับแบบโทโพโลยีหรือการสั่งการแบบโทโพโลยี เราสามารถพูดได้ว่าความซับซ้อนของเวลาจากการคำนวณข้างต้นจะเป็น O( V + E ) โดยที่ O หมายถึงฟังก์ชันความซับซ้อน

ความซับซ้อนของอวกาศ: เราต้องการช่องว่าง O(V) เพื่อรันอัลกอริธึมการเรียงลำดับทอพอโลยี

ขั้นตอนที่เราต้องการพื้นที่สำหรับโปรแกรมมีดังนี้:

• เราต้องคำนวณ indegree ของโหนดทั้งหมดที่มีอยู่ในกราฟ เนื่องจากกราฟมีโหนด V ทั้งหมด เราจึงต้องสร้างอาร์เรย์ขนาด V ดังนั้น พื้นที่ที่ต้องการคือ โอ(วี).
• โครงสร้างข้อมูลคิวถูกใช้เพื่อจัดเก็บโหนดที่มีค่าศูนย์เป็นศูนย์ เราลบโหนดที่มีระดับเป็นศูนย์ออกจากกราฟดั้งเดิมและวางไว้ในคิว สำหรับสิ่งนี้พื้นที่ที่ต้องการคือ โอ(วี).
• อาร์เรย์มีชื่อว่า "คำสั่งซื้อ" นั่นเก็บโหนดตามลำดับทอพอโลยี นั่นก็จำเป็นเช่นกัน โอ(วี) ช่องว่าง

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

ความซับซ้อนของพื้นที่หมายถึง O(V) โดยที่ V หมายถึงจำนวนจุดยอดในกราฟ

การประยุกต์ใช้การเรียงลำดับทอพอโลยี

มีการใช้ประโยชน์อย่างมากสำหรับการเรียงลำดับทอพอโลยี นี่คือบางส่วนของพวกเขา:

• มันถูกใช้เมื่อ Operaระบบติ้ง จำเป็นต้องดำเนินการจัดสรรทรัพยากร
• การหาวงจรในกราฟ เราสามารถตรวจสอบได้ว่ากราฟเป็น DAG หรือไม่ด้วยการเรียงลำดับทอพอโลยี
• การเรียงลำดับประโยคในแอปเติมข้อความอัตโนมัติ
• ใช้สำหรับการตรวจจับ การหยุดชะงัก.
• การจัดกำหนดการประเภทต่างๆ หรือการจัดตารางเวลาหลักสูตรใช้การเรียงลำดับทอพอโลยี
• การแก้ปัญหาการพึ่งพา ตัวอย่างเช่น หากคุณพยายามติดตั้งแพ็คเกจ แพ็คเกจนั้นอาจต้องใช้แพ็คเกจอื่นด้วย การสั่งซื้อทอพอโลยีจะค้นหาแพ็คเกจที่จำเป็นทั้งหมดเพื่อติดตั้งแพ็คเกจปัจจุบัน
• ลินุกซ์ ใช้การเรียงลำดับทอพอโลยีใน "apt" เพื่อตรวจสอบการขึ้นต่อกันของแพ็คเกจ