数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 程序用于查找图的顶点连通性
为了找出某个图的顶点连通性，我们需要找出该图的割点。如果某个点（以及与其连接的边）能够断开图，则它就是图的割点。对于一个不连通的无向图来说，割点如果被移除，则连接部分的数量会增加。
算法
Begin We use dfs here to find articulation point: In DFS, a vertex w is articulation point if one of the following two conditions is satisfied. 1) w is root of DFS tree and it has at least two children. 2) w is not root of DFS tree and it has a child x such that no vertex in subtree rooted with w has a back edge to one of the ancestors of w in the tree. End
示例
#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list<int> *adj;
//declaration of functions
void APT(int v, bool visited[], int dis[], int low[],
int par[], bool ap[]);
public:
G(int n); //constructor
void addEd(int w, int x);
void AP();
};
G::G(int n) {
this->n = n;
adj = new list<int>[n];
}
//add edges to the graph
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::APT(int w, bool visited[], int dis[], int low[], int
par[], bool ap[]) {
static int t=0;
int child = 0; //initialize child count of dfs tree is 0.
//mark current node as visited
visited[w] = true;
dis[w] = low[w] = ++t;
list<int>::iterator i;
//Go through all adjacent vertices
for (i = adj[w].begin(); i != adj[w].end(); ++i) {
int x = *i; //x is current adjacent
if (!visited[x]) {
child++;
par[x] = w;
APT(x, visited, dis, low, par, ap);
low[w] = min(low[w], low[x]);
// w is an articulation point in following cases :
// w is root of DFS tree and has two or more children.
if (par[w] == N && child> 1)
ap[w] = true;
// If w is not root and low value of one of its child is more than discovery value of w.
if (par[w] != N && low[x] >= dis[w])
ap[w] = true;
}
else if (x != par[w]) //update low value
low[w] = min(low[w], dis[x]);
}
}
void G::AP() {
// Mark all the vertices as unvisited
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;
}
// Call the APT() function to find articulation points in DFS tree rooted with vertex 'i'
for (int i = 0; i < n; i++)
if (visited[i] == false)
APT(i, visited, dis, low, par, ap);
//print the articulation points
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
更新于：2019 年 7 月 30 日
628 次浏览
广告