একটি গ্রাফের ভার্টেক্স কানেক্টিভিটি বের করতে হলে আমাদের সেই গ্রাফের আর্টিকুলেশন পয়েন্ট (Articulation Points) বের করতে হবে। একটি গ্রাফে আর্টিকুলেশন পয়েন্ট (কাট ভার্টেক্স) হলো একটি পয়েন্ট যেটি যদি রিমুভ করা হয় (এবং তার মাধ্যমে যাওয়া এজগুলো), তবে গ্রাফটি ডিসকানেক্টেড হয়ে যায়। একটি ডিসকানেক্টেড আনডিরেক্টেড গ্রাফের জন্য আর্টিকুলেশন পয়েন্ট হলো একটি ভার্টেক্স যেটি রিমুভ করলে কানেক্টেড কম্পোনেন্টের সংখ্যা বেড়ে যায়।
আলগরিদম
Begin
আমরা এখানে DFS ব্যবহার করি আর্টিকুলেশন পয়েন্ট খুঁজে বের করতে:
DFS-এ, একটি ভার্টেক্স w আর্টিকুলেশন পয়েন্ট যদি নিচের দুটি শর্তে যেকোনো একটি সन्तুষ্ট হয়।
1) w হলো DFS ট্রির রুট এবং এর কমপক্ষে দুটি চাইল্ড আছে।
2) w DFS ট্রির রুট নয় এবং এর একটি চাইল্ড x আছে এমন যে w-র সাথে রুট করা সাবট্রির কোনো ভার্টেক্সের w-এর আনসেস্টরের সাথে ব্যাক এজ নেই।
End
উদাহরণ
#include <iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list<int> *adj;
void APT(int v, bool visited[], int dis[], int low[], int par[], bool ap[]);
public:
G(int n); // কনস্ট্রাক্টর
void addEd(int w, int x);
void AP();
};
G::G(int n) {
this->n = n;
adj = new list<int>[n];
}
void G::addEd(int w, int x) {
adj[x].push_back(w);
adj[w].push_back(x);
}
void G::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) {
static int t = 0;
int child = 0;
visited[w] = true;
dis[w] = low[w] = ++t;
list<int>::iterator i;
for (i = adj[w].begin(); i != adj[w].end(); ++i) {
int x = *i;
if (!visited[x]) {
child++;
par[x] = w;
APT(x, visited, dis, low, par, ap);
low[w] = min(low[w], low[x]);
if (par[w] == N && child > 1)
ap[w] = true;
if (par[w] != N && low[x] >= dis[w])
ap[w] = true;
}
else if (x != par[w])
low[w] = min(low[w], dis[x]);
}
}
void G::AP() {
bool *visited = new bool[n];
int *dis = new int[n];
int *low = new int[n];
int *par = new int[n];
bool *ap = new bool[n];
for (int i = 0; i < n; i++) {
par[i] = N;
visited[i] = false;
ap[i] = false;
}
for (int i = 0; i < n; i++)
if (visited[i] == false)
APT(i, visited, dis, low, par, ap);
for (int i = 0; i < n; i++)
if (ap[i] == true)
cout << i << " ";
}
int main() {
cout << "\nArticulation points in first graph \n";
G g1(5);
g1.addEd(1, 2);
g1.addEd(3, 1);
g1.addEd(0, 2);
g1.addEd(2, 3);
g1.addEd(0, 4);
g1.AP();
return 0;
}
আউটপুট
Articulation points in first graph 0 2
