Chương trình C ++ để tạo phần mở rộng tuyến tính ngẫu nhiên cho DAG

Ở đây chúng ta sẽ xem cách tạo Phần mở rộng Tuyến tính Ngẫu nhiên của Đồ thị Vòng có Hướng dẫn (DAG). Phần mở rộng Tuyến tính về cơ bản là sắp xếp theo cấu trúc liên kết của DAG. Chúng ta hãy xem biểu đồ như dưới đây -

Việc sắp xếp tôpô cho một đồ thị xoay chiều có hướng là thứ tự tuyến tính của các đỉnh. Đối với mọi cạnh u-v của đồ thị có hướng, đỉnh u sẽ đến trước đỉnh v theo thứ tự.

Như chúng ta biết rằng đỉnh nguồn sẽ đến sau đỉnh đích, vì vậy chúng ta cần sử dụng một ngăn xếp để lưu trữ các phần tử trước đó. Sau khi hoàn thành tất cả các nút, chúng tôi có thể chỉ cần hiển thị chúng từ ngăn xếp.

Đầu vào

Đầu ra

Các nút sau thứ tự được sắp xếp theo cấu trúc liên kết - 5 4 2 3 1 0

Thuật toán

topoSort (u, đã thăm, ngăn xếp)

Đầu vào - Đỉnh bắt đầu u, Một mảng để theo dõi nút nào được truy cập hay không. Một ngăn xếp để lưu trữ các nút.

Đầu ra - Sắp xếp các đỉnh theo trình tự tôpô trong ngăn xếp.

Begin
   mark u as visited
   for all vertices v which is adjacent with u, do
      if v is not visited, then
         topoSort(c, visited, stack)
      done
      push u into stack
End

performanceTopologicalSorting (Graph)

Đầu vào - Đồ thị mạch hở có hướng đã cho.

Đầu ra - Trình tự các nút.

Begin
   initially mark all nodes as unvisited
   for all nodes v of the graph, do
      if v is not visited, then
         topoSort(i, visited, stack)
      done
      pop and print all elements from the stack
End

Ví dụ

#include<iostream>
#include<stack>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 0},
   {0, 0, 0, 1, 0, 0},
   {0, 1, 0, 0, 0, 0},
   {1, 1, 0, 0, 0, 0},
   {1, 0, 1, 0, 0, 0}
};
void topoSort(int u, bool visited[], stack<int> &stk) {
   visited[u] = true; //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]){ //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }
   stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
   stack<int> stk;
   bool vis[NODE];
   for(int i = 0; i<NODE; i++)
      vis[i] = false; //initially all nodes are unvisited
   for(int i = 0; i<NODE; i++)
      if(!vis[i]) //when node is not visited
         topoSort(i, vis, stk);
   while(!stk.empty()) {
      cout << stk.top() << " ";
      stk.pop();
   }
}
main() {
   cout << "Nodes after topological sorted order: ";
   performTopologicalSort();
}

Đầu ra

Nodes after topological sorted order: 5 4 2 3 1 0