Topologik saralash. Algoritmning murakkabligini baholash”
![Mana bir misol:
1-tugun 2 va 3-tugunlarga ishora qilganligi sababli, 1-tugun tartiblashda
ulardan oldin paydo bo'ladi. Va 2 va 3 tugunlari 4-tugunga ishora qilganligi
sababli, ular tartiblashda undan oldin paydo bo'ladi.
Shunday qilib, [1, 2, 3, 4, 5] grafikning topologik tartibi bo'ladi.
Grafikda bir nechta to'g'ri topologik tartib bo'lishi mumkinmi? Ha!
Yuqoridagi misolda [1, 3, 2, 4, 5] ham ishlaydi.
Siklik grafiklar
Ushbu yo'naltirilgan grafikni sikl bilan ko'ring:
sikl imkonsiz cheklovlar to'plamini yaratadi - B tartiblashda D dan oldin va
keyin bo'lishi kerak.
Qoida tariqasida, siklik grafiklarda to'g'ri topologik tartiblar mavjud emas.
Algoritm](https://docx.uz/documents/74fb3157-8097-47e6-b99b-e9be5433ed43/page_5.png?v=1)
![Amaliy ish.
// A C++ topologik chop etish uchun dastur// DAGni saralash
#include <bits/stdc++.h>
using namespace std;
// Class grafikni ifodalash uchun
class Graph {
// No. of vertices'
int V;
// Qo'shni ro'yxatlar ro'yxatini o'z ichiga olgan massivga
ko'rsatgich list<int>* adj;
// TopologicalSort tomonidan ishlatiladigan funksiya
void topologicalSortUtil(int v, bool tashrif buyurdi [],
stack<int>& Stack);
public:
// Constructor
Graph(int V);
// grafikga chekka qo'shish funktsiyasi
void addEdge(int v, int w);
// topologik tartibni chop etadi
// to'liq grafik
void topologicalSort();
};
Graph::Graph(int V)](https://docx.uz/documents/74fb3157-8097-47e6-b99b-e9be5433ed43/page_13.png?v=1)
![{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
// Add w to v’s list.
adj[v].push_back(w);
}
// TopologicalSort tomonidan ishlatiladigan rekursiv funksiya
void Graph::topologicalSortUtil(int v, bool tashrif buyurilgan[],
stack<int>& Stack)
{
// Joriy tugunni tashrif buyurilgan deb belgilang.
visited[v] = true;
// Barcha uchlari uchun takrorlang
// bu cho'qqiga qo'shni
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Yig'ish uchun joriy cho'qqini suring
// qaysi do'konlar natijasi
Stack.push(v);
}
// Topologik tartiblash funksiyasi.
// U rekursiv topologicalSortUtil dan foydalanadi ()
void Graph::topologicalSort()
{
stack<int> Stack;
// Barcha uchlarini tashrif buyurilmagan deb belgilang
bool* visited = new bool[V];](https://docx.uz/documents/74fb3157-8097-47e6-b99b-e9be5433ed43/page_14.png?v=1)
![for (int i = 0; i < V; i++)
visited[i] = false;
// Rekursiv yordamchi funksiyani chaqiring
// Topologik saqlash uchun
// Hammasidan boshlab saralash
// uchlari birma-bir
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Stack tarkibini chop etish
while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
delete [] visited;
}
// Haydovchi kodi
int main()
{
// Yuqoridagi diagrammada berilgan grafikni tuzing
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << " Quyida berilganlarning topologik turi keltirilgan "
"graph \n";
// Funktsiya chaqiruvi
g.topologicalSort();
return 0;](https://docx.uz/documents/74fb3157-8097-47e6-b99b-e9be5433ed43/page_15.png?v=1)
Topologik saralash. Algoritmning murakkabligini baholash”