|
Graflarda eng qisqa yulni topish usullari haqida tushuncha
|
| bet | 2/2 | | Sana | 13.05.2024 | | Hajmi | 416,21 Kb. | | #228874 |
Bog'liq 1 mustaqilGraflarda eng qisqa yulni topish usullari haqida tushuncha
"Yoʻnaltirilgan atsiklik graf" ("Directed Acyclic Graph" yoki "DAG") bu grafik turi, bu turiy xususiyatlariga ega bo'lgan. Quyidagi kiritilmalar yoʻnaltirilgan atsiklik graflarning asosiy turlarini bildiradi:
Yoʻnaltirilgan (Directed): Har bir toʻgʻri tarmoq (edge) bir tochiq yuqoriga yoki pastga yoʻnaladi. Bunda, boshqa yoʻnaltirilgan graflarning bir xususiyati boʻlmagan, yoʻnaltirilgan tarmoqlarga ega boʻlgan ma'lumotlar o'tkaziladi.
Atsiklik (Acyclic): Yoʻnaltirilgan atsiklik grafda uchradigan hamma yoʻlning toʻgʻri, yoʻnalish orqali borishidan qoʻrqishmaslik keltirilgan. Bu atsiklik yoʻnalish yoʻnalishlarni (yoʻl bo'yicha yurishlarni) qaytarish orqali tiklashni ma'nosiz qiladi.
DAGlar o'zlarini bir nechta sohalarida muvaffaqiyatli ishlatadi:
Ma'lumotlar Tahlili: DAGlar ma'lumotlar tahlilida, masalan, bog'liq masalalarni hal qilish, hamda ma'lumotlar tizimini yaxshi nazorat qilish uchun ishlatiladi.
Dasturiy yozuvlar va algoritmlar: Tizimni yaxshi tuzish, dasturlarni samaraliroq va tezroq boshqarish uchun yoʻnaltirilgan atsiklik graflar yaratiladi.
Hamkorlikda Ishlash: Bu turlar, bir-biriga bog'liq ishlar, buyruqlar yoki protsesslarni nazorat qilishda hamkorlikda ishlashda foydalaniladi.
O'rganish algoritmlari: Yoʻnaltirilgan atsiklik graflar, tushunchalar va algoritmlarni oʻrganish uchun foydalaniladi, masalan, topologik tartiblash algoritmi va boshqa algoritm turlarini oʻrganishda.
Topologik saralash usuliga oid masalalar.
Buning uchun biz quydagicha kod yozamiz:
#include
#include
#include
#include
using namespace std;
class Graph {
public:
int vertices;
vector> adjacencyList;
Graph(int v) : vertices(v), adjacencyList(v) {}
void addEdge(int v, int w) {
adjacencyList[v].push_back(w);
}
void topologicalSortUtil(int v, unordered_set& visited, stack& result) {
visited.insert(v);
for (int neighbor : adjacencyList[v]) {
if (visited.find(neighbor) == visited.end()) {
topologicalSortUtil(neighbor, visited, result);
}
}
result.push(v);
}
void topologicalSort() {
stack result;
unordered_set visited;
for (int i = 0; i < vertices; ++i) {
if (visited.find(i) == visited.end()) {
topologicalSortUtil(i, visited, result);
}
}
cout << "Topological Order: ";
while (!result.empty()) {
cout << result.top() << " ";
result.pop(); }
cout << endl;
} };
int main() {
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);
g.topologicalSort();
return 0; }
Kod qismimiz quydagicha boladi:
Ishlashini quydagicha tekshiramiz
|
| |
