C ++程序查找要切割以使图形断开连接的最小边数
在此程序中，我们需要找到图的边缘连通性。图的图的边缘连通性意味着它是一个桥，将其删除将断开连接。随着断开的无向图中的桥的去除，连接组件的数量增加。
函数和伪代码
Begin Function connections() is a recursive function to find out the connections: A) Mark the current node un visited. B) Initialize time and low value C) Go through all vertices adjacent to this D) Check if the subtree rooted with x has a connection to one of the ancestors of w. 如果从x下的子树可到达的最低顶点是 below u in DFS tree, then w-x has a connection. E) Update low value of w for parent function calls. End
的功能和伪代码Con()
Begin Function Con() that uses connections(): A)将所有顶点标记为未访问. B) Initialize par and visited, and connections. C) Print the connections between the edges in the graph. End
示例
#include<iostream>
#include <list>
#define N -1
using namespace std;
class G
{
//功能声明
int n;
list<int> *adj;
void connections(int n, bool visited[], int disc[], int
low[],
int par[]);
public:
G(int n); //constructor
void addEd(int w, int x);
void Con();
};
G::G(int n)
{
this->n= n;
adj = new list<int> [n];
}
//在图上添加边
void G::addEd(int w, int x)
{
adj[x].push_back(w); //add u to v's list
adj[w].push_back(x); //add v to u's list
}
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<int>::iterator i;
for (i = adj[w].begin(); i != adj[w].end(); ++i) {
int x = *i; //x is current adjacent
if (!visited[x]) {
par[x] = w;
connections(x, visited, dis, low, par);
low[w] = min(low[w], low[x]);
//如果从x下的子树可到达的最低顶点是
below w in DFS tree, then w-x is a connection
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;
}
//call the function connections() to find edge
connections
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