यहां हम देखेंगे कि डायरेक्टेड एसाइक्लिक ग्राफ (DAG) का रैंडम लीनियर एक्सटेंशन कैसे बनाया जाता है। रैखिक विस्तार मूल रूप से डीएजी की टोपोलॉजिकल सॉर्टिंग है। आइए मान लें कि ग्राफ नीचे जैसा है -
एक निर्देशित चक्रीय ग्राफ के लिए स्थलीय छँटाई शिखरों का रैखिक क्रम है। निर्देशित ग्राफ़ के प्रत्येक किनारे u-v के लिए, शीर्ष u क्रम में vertex v से पहले आएगा।
जैसा कि हम जानते हैं कि स्रोत शीर्ष गंतव्य शीर्ष के बाद आएगा, इसलिए हमें पिछले तत्वों को संग्रहीत करने के लिए एक स्टैक का उपयोग करने की आवश्यकता है। सभी नोड्स को पूरा करने के बाद, हम उन्हें केवल स्टैक से प्रदर्शित कर सकते हैं।
इनपुट
| 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 |
आउटपुट
टोपोलॉजिकल क्रमबद्ध क्रम के बाद नोड्स - 5 4 2 3 1 0
एल्गोरिदम
topoSort(u, विज़िट किया गया, स्टैक)
इनपुट - स्टार्ट वर्टेक्स यू, ट्रैक रखने के लिए एक सरणी जो नोड का दौरा किया गया है या नहीं। नोड्स को स्टोर करने के लिए एक स्टैक।
आउटपुट - स्टैक में टोपोलॉजिकल अनुक्रम में शीर्षों को क्रमबद्ध करना।
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
परफॉर्म टोपोलॉजिकलसॉर्टिंग(ग्राफ)
इनपुट - दिया गया निर्देशित चक्रीय ग्राफ।
आउटपुट - नोड्स का क्रम।
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
उदाहरण
#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();
} आउटपुट
Nodes after topological sorted order: 5 4 2 3 1 0