এই প্রোগ্রামে আমরা মূলত একটি ফিডব্যাক আর্ক সেট (Feedback Arc Set) খুঁজে বের করব যেটিতে এমন এজগুলো থাকে যেগুলো গ্রাফ থেকে সরিয়ে দেওয়া হলে, গ্রাফটি একটি ডিরেক্টেড एসাইক্লিক গ্রাফ (DAG) এ রূপান্তরিত হয়।
অ্যালগরিদম
শুরু ফাংশন checkCG(int n) : n: ভের্টেক্সের সংখ্যা। arr: struct graph ভেরিয়েবল। cnt = 0 এবং size = (n-1) ইনিশিয়ালাইজ করুন। For i = 0 to n-1 if (cnt == size) return 0 if (arr[i].ptr == NULL) cnt বাড়ান। for j = 0 to n-1 while (arr[j].ptr != NULL) if ((arr[j].ptr)->des == (arr[i].ptr)->des) (arr[j].ptr)->des = -1 arr[i].ptr = (arr[i].ptr)->next সমাপ্ত সমাপ্ত সমাপ্ত সমাপ্ত visited[n + 1] ইনিশিয়ালাইজ করুন For i = 0 to n-1 while (arr[i].ptr != NULL) Print (arr[i].ptr)->des visited[i] = 1 for j = 0 to n-1 while (arr[j].ptr != NULL) print (arr[j].ptr)->des if (visited[arr[j].v] == 1) print arr[i].v << " - " << arr[j].v সমাপ্ত arr[j].ptr = (arr[j].ptr)->next সমাপ্ত সমাপ্ত arr[i].ptr = (arr[i].ptr)->next সমাপ্ত সমাপ্ত return 1 শেষ
উদাহরণ
#include<iostream> using namespace std; int c = 0; struct ad_list { int des; ad_list *next; }*np = NULL, *np1 = NULL, *p = NULL, *q = NULL; struct Graph { int v; ad_list *ptr; } array[6]; void addRevEdge(int sr, int des) //গ্রাফে রিভার্স এজ যোগ করুন { np1 = new ad_list; np1->des = sr; np1->next = NULL; if (arr[des].ptr == NULL) { arr[des].ptr = np1; q = arr[des].ptr; q->next = NULL; } else { q = arr[des].ptr; while (q->next != NULL) { q = q->next; } q->next = np1; } } void addEd(int sr, int des) //গ্রাফে এজ যোগ করুন { np = new ad_list; np->des = des; np->next = NULL; if (arr[sr].ptr == NULL) { arr[sr].ptr = np; p = arr[sr].ptr; p->next = NULL; } else { p = arr[sr].ptr; while (p->next != NULL) { p = p->next; } p->next = np; } } void print_graph(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)->des << " "; arr[i].ptr = (arr[i].ptr)->next; } cout << endl; } } //গ্রাফটি ডিরেক্টেড এসাইক্লিক গ্রাফ (DAG) কিনা তা চেক করতে। int checkCG(int n) { int cnt = 0; int size = n - 1; for (int i = 0; i < n; i++) { if (cnt == size) { return 0; } if (arr[i].ptr == NULL) { cnt++; for (int j = 0; j < n; j++) { while (arr[j].ptr != NULL) { if ((arr[j].ptr)->des == (arr[i].ptr)->des) { (arr[j].ptr)->des = -1; } arr[i].ptr = (arr[i].ptr)->next; } } } } cout<<"after checking dag"; int visited[n + 1]; for (int i = 0; i < n; i++) { while (arr[i].ptr != NULL) { cout << (arr[i].ptr)->des << " "; visited[i] = 1; for (int j = 0; j < n; j++) { while (arr[j].ptr != NULL) { cout << (arr[j].ptr)->des << " "; if (visited[arr[j].v] == 1) { cout << arr[i].v << " - " << arr[j].v; } arr[j].ptr = (arr[j].ptr)->next; } cout << endl; } arr[i].ptr = (arr[i].ptr)->next; } cout << endl; } return 1; } int main() { int n = 5; cout << "Number of vertices: " << n << endl; for (int i = 0; i < n; i++) { arr[i].v = i; arr[i].ptr = NULL; } addEd(1, 2); addEd(2, 1); addEd(0, 1); addEd(2, 3); addEd(2, 0); addEd(5, 4); addEd(4, 2); print_graph(n); cout << "Feedback arc Set: "; if (checkCG(n) == 0) cout << " None"; }
আউটপুট
নোডের সংখ্যা: 5 Adjacency List of 0: 1 Adjacency List of 1: 2 Adjacency List of 2: 1 3 0 Adjacency List of 3: Adjacency List of 4: 2 Feedback arc Set: None
