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

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

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

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

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

กราฟกำกับ

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

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

การพึ่งพาของแต่ละโหนด (การสั่งซื้อเชิงเส้น)

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

นี่คือขั้นตอนในการทำเช่นนี้:

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

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

ขั้นตอน 3) จากนั้นให้ลบเส้นเชื่อมขาออกจากโหนดนั้น การทำเช่นนี้จะทำให้จำนวนเส้นเชื่อมขาเข้าสำหรับโหนดถัดไปลดลง

การเรียงลำดับเชิงโทโพโลยีกำหนดให้โครงสร้างข้อมูลกราฟต้องไม่มีวงจร กราฟจะถือว่าเป็น DAG หากเป็นไปตามข้อกำหนดเหล่านี้:

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

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

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

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

ต่อไปนี้คือขั้นตอนของอัลกอริธึมของคานห์:

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

หมายเหตุ

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

ต่อไปนี้คือจำนวนอินพุตและจำนวนเอาต์พุตของกราฟด้านบน:

ขั้นตอน 2) ค้นหาโหนดที่มีดีกรีขาเข้าเป็นศูนย์ หรือไม่มีเส้นเชื่อมขาเข้าที่ชี้ไปยังโหนดนั้น โหนดที่มีดีกรีขาเข้าเป็นศูนย์ หมายความว่าไม่มีเส้นเชื่อมใดชี้ไปยังโหนดนั้น โหนด “A” มีดีกรีขาเข้าเป็นศูนย์ ซึ่งหมายความว่าไม่มีเส้นเชื่อมใดชี้ไปยังโหนด “A” ดังนั้น เราจะดำเนินการดังต่อไปนี้:

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

ขั้นตอน 3) เราต้องหาโหนดที่มีค่า indegree เป็นศูนย์ ในตัวอย่างนี้ “B” และ “C” มี indegree เป็นศูนย์ เราสามารถเลือกโหนดใดโหนดหนึ่งก็ได้ สมมติว่าเราเลือก “B” แล้วลบออกจากกราฟ จากนั้นอัปเดตค่า indegree ของโหนดอื่นๆ หลังจากดำเนินการเหล่านี้แล้ว กราฟและคิวของเราจะมีลักษณะดังต่อไปนี้:

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

ขั้นตอน 5) เราจะเห็นว่าโหนด “D” และ “F” มีดีกรีขาเข้าเป็นศูนย์ เราจะเลือกโหนดหนึ่งแล้วใส่เข้าไปในคิว เริ่มจากเอา “D” ออกก่อน จากนั้นจำนวนดีกรีขาเข้าของโหนด “E” จะเป็น 1 ตอนนี้จะไม่มีโหนดเชื่อมจาก D ไป E แล้ว เราต้องทำแบบเดียวกันกับโหนด “F” และผลลัพธ์ของเราจะเป็นดังนี้:

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

ชื่อเล่น Code สำหรับการเรียงลำดับเชิงทอพอโลยี

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

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 0 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 สร้างวงจร ถ้าสังเกตดู จะไม่มีโหนดใดที่มีค่าดีกรีขาเข้าเป็นศูนย์ ตามอัลกอริทึมของคาน หากเราวิเคราะห์กราฟข้างต้น:

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

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

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

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

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

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

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

ความซับซ้อนของอัลกอริทึมมีสองประเภท ได้แก่:

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

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

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

เรามาลองทำความเข้าใจความซับซ้อนนี้กัน:

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

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

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

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

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

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

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

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

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

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

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

คำถามที่พบบ่อย