একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ (ডিএজি) হল একটি গ্রাফ যা নির্দেশিত এবং চক্র ছাড়াই অন্যান্য প্রান্তগুলিকে সংযুক্ত করে। এই গ্রাফের প্রান্তগুলি একদিকে যায়। গ্রাফটি DAG কিনা তা পরীক্ষা করার জন্য এটি একটি C++ প্রোগ্রাম।
অ্যালগরিদম
Begin Function checkDAG(int n): intialize count = 0 intialize size = n - 1 for i = 0 to n-1 if (count == size) return 1 done if (arr[i].ptr == NULL) increment count for j = 0 to n-1 while (arr[j].ptr != NULL) if ((arr[j].ptr)->d == (arr[i].ptr)->d) (arr[j].ptr)->d = -1 done arr[i].ptr = (arr[i].ptr)->next done done done done return 0 End
উদাহরণ কোড
#include<iostream>
using namespace std;
int c = 0;
struct ad_list { //A structure of type adj_list
int d;
ad_list *next;
}
*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Gr { //A structure of type Gr
int v;
ad_list *ptr;
}
arr[6];
void addRevEdge(int s, int d) { //add reverse edges in the graph
np1 = new ad_list;
np1->d = s;
np1->next = NULL;
if (arr[d].ptr == NULL) {
arr[d].ptr = np1;
q = arr[d].ptr;
q->next = NULL;
} else {
q = arr[d].ptr;
while (q->next != NULL) {
q = q->next;
}
q->next = np1;
}
}
void addEdge(int s, int d) { // add edges in the graph
np = new ad_list;
np->d = d;
np->next = NULL;
if (arr[s].ptr == NULL) {
arr[s].ptr = np;
p = arr[s].ptr;
p->next = NULL;
} else {
p = arr[s].ptr;
while (p->next != NULL) {
p = p->next;
}
p->next = np;
}
}
void print_g(int n) {
for (int i = 0; i < n; i++) {
cout << "Adjacency List of " << arr[i].v << ": ";
while (arr[i].ptr != NULL) {
cout << (arr[i].ptr)->d<< " ";
arr[i].ptr = (arr[i].ptr)->next;
}
cout << endl;
}
}
int checkDAG(int n) {
int count = 0;
int size = n - 1;
for (int i = 0; i < n; i++) {
if (count == size) {
return 1;
}
if (arr[i].ptr == NULL) {
count++;
for (int j = 0; j < n; j++) {
while (arr[j].ptr != NULL) {
if ((arr[j].ptr)->d == (arr[i].ptr)->d) {
(arr[j].ptr)->d = -1;
}
arr[i].ptr = (arr[i].ptr)->next;
}
}
}
}
return 0;
}
int main() {
int v = 4;
cout << "Number of vertices: " << v << endl;
for (int i = 0; i < v; i++) {
arr[i].v = i;
arr[i].ptr = NULL;
}
addEdge(1, 0);
addEdge(3, 1);
addEdge(2, 1);
addEdge(0, 3);
addEdge(4, 1);
print_g(v);
cout << "The given graph is 'Directed Acyclic Graph' :";
if (checkDAG(v) == 1)
cout << " yes";
else
cout << " no";
} আউটপুট
Number of vertices: 4 Adjacency List of 0: 3 Adjacency List of 1: 0 Adjacency List of 2: 1 Adjacency List of 3: 1 The given graph is 'Directed Acyclic Graph' : yes
