গ্রাফে আর্টিকুলেশন পয়েন্ট (কাট ভার্টেক্স) হলো এমন একটি পয়েন্ট যেটি রিমুভ করলে (এবং এর মাধ্যমে যাওয়া এজগুলো) গ্রাফ ডিসকানেক্টেড হয়ে যায়। ডিসকানেক্টেড আনডিরেক্টেড গ্রাফে আর্টিকুলেশন পয়েন্ট হলো এমন ভার্টেক্স যেটি রিমুভ করলে কানেক্টেড কম্পোনেন্টের সংখ্যা বাড়ে।
অ্যালগরিদম
Begin
আর্টিকুলেশন পয়েন্ট বের করতে DFS ব্যবহার করুন:
DFS-এ একটি ভার্টেক্স w আর্টিকুলেশন পয়েন্ট হলে নিচের দুটি শর্তে যেকোনো একটি সত্য হয়:
1) w হলো DFS ট্রির রুট এবং এর কমপক্ষে দুটি চাইল্ড আছে।
2) w DFS ট্রির রুট নয় এবং এর একটি চাইল্ড x আছে যাতে x-র সাবট্রির কোনো ভার্টেক্স w-এর অ্যানসেস্টরের সাথে ব্যাক এজ থাকে না।
End
উদাহরণ
#include <iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list *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[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::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
