এই প্রোগ্রামে আমরা গ্রাফের এজ কানেক্টিভিটি বের করব। একটি গ্রাফের এজ কানেক্টিভিটি মানে সেটি একটি ব্রিজ, অর্থাৎ সেটি রিমুভ করলে গ্রাফ ডিসকানেক্টেড হয়ে যাবে। ডিসকানেক্টেড আনডিরেক্টেড গ্রাফে ব্রিজ রিমুভ করলে কানেক্টেড কম্পোনেন্টের সংখ্যা বাড়ে।
ফাংশন ও সিউডোকোড
Begin
Function connections() - রিকারসিভ ফাংশন কানেকশন বের করতে:
A) বর্তমান নোডকে ভিজিটেড মার্ক করুন।
B) টাইম এবং লো ভ্যালু ইনিশিয়ালাইজ করুন।
C) এই নোডের সকল অadyacent ভার্টেক্স traverser করুন।
D) চেক করুন সাবট্রি x-এর কোনো অ্যানসেস্টর w-র সাথে কানেকশন আছে কিনা। যদি x-র থেকে পৌঁছানো লোయেস্ট ভার্টেক্স DFS ট্রি-এ w-এর নিচে থাকে, তবে w-x একটি কানেকশন।
E) প্যারেন্ট ফাংশন কলের জন্য w-এর লো ভ্যালু আপডেট করুন।
End
Begin
Function Con() - connections() ব্যবহার করে:
A) সকল ভার্টেক্সকে অনভিজিটেড মার্ক করুন।
B) par, visited, এবং connections ইনিশিয়ালাইজ করুন।
C) গ্রাফের এজগুলোর মধ্যে কানেকশন প্রিন্ট করুন।
End
উদাহরণ
#include <iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list *adj;
void connections(int n, bool visited[], int disc[], int low[], int par[]);
public:
G(int n);
void addEd(int w, int x);
void Con();
};
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::connections(int w, bool visited[], int dis[], int low[], int par[]) {
static int t = 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]) {
par[x] = w;
connections(x, visited, dis, low, par);
low[w] = min(low[w], low[x]);
if (low[x] > dis[w])
cout << w << " " << x << endl;
} else if (x != par[w])
low[w] = min(low[w], dis[x]);
}
}
void G::Con() {
bool *visited = new bool[n];
int *dis = new int[n];
int *low = new int[n];
int *par = new int[n];
for (int i = 0; i < n; i++) {
par[i] = N;
visited[i] = false;
}
for (int i = 0; i < n; i++)
if (visited[i] == false)
connections(i, visited, dis, low, par);
}
int main() {
cout << "\nConnections in first graph \n";
G g1(5);
g1.addEd(1, 2);
g1.addEd(3, 2);
g1.addEd(2, 1);
g1.addEd(0, 1);
g1.addEd(1, 4);
g1.Con();
return 0;
}
আউটপুট
Connections in first graph 2 3 1 2 1 4 0 1
