数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究双连通图
如果任意两顶点之间存在两条点分离路径，则此无向图为双连通图。换句话说，我们可以说任意两个顶点之间都有一个环。
我们可以说图 G 是一个双连通图，如果它是连通的，并且图中不存在割点或割顶。
为了解决这个问题，我们将使用 DFS 遍历。使用 DFS，我们将尝试找出是否存在割点。我们还检查 DFS 是否访问了所有顶点，如果没有，我们可以说这个图是不连通的。
输入和输出
Input: The adjacency matrix of the graph. 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Output: The Graph is a biconnected graph.
算法
isArticulation(start, visited, disc, low, parent)
输入： 起点，已访问数组以标记某个节点是否已访问，disc 将保存顶点的发现时间，low 将保存有关子树的信息。parent 将保存当前顶点的父级。
输出 − 如果找到任何割点，则为 True。
Begin time := 0 //the value of time will not be initialized for next function calls dfsChild := 0 mark start as visited set disc[start] := time+1 and low[start] := time + 1 time := time + 1 for all vertex v in the graph G, do if there is an edge between (start, v), then if v is visited, then increase dfsChild parent[v] := start if isArticulation(v, visited, disc, low, parent) is true, then return ture low[start] := minimum of low[start] and low[v] if parent[start] is φ AND dfsChild > 1, then return true if parent[start] is φ AND low[v] >= disc[start], then return true else if v is not the parent of start, then low[start] := minimum of low[start] and disc[v] done return false End
isBiconnected(graph)
输入：给定的图。
输出 − 如果图是双连通的，则为 True。
Begin initially set all vertices are unvisited and parent of each vertices are φ if isArticulation(0, visited, disc, low, parent) = true, then return false for each node i of the graph, do if i is not visited, then return false done return true End
示例
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
int min(int a, int b) {
return (a<b)?a:b;
}
bool isArticulation(int start, bool visited[], int disc[], int low[], int parent[]) {
static int time = 0;
int dfsChild = 0;
visited[start] = true; //make the first vertex is visited
disc[start] = low[start] = ++time; //initialize discovery time and the low time
for(int v = 0; v<NODE; v++) {
if(graph[start][v]) { //for all vertex v, which is connected with start
if(!visited[v]) {
dfsChild++;
parent[v] = start; //make start node as parent
if(isArticulation(v, visited, disc, low, parent))
return true;
low[start] = min(low[start], low[v]); //when subtree from v is connected to one of parent of start node
if(parent[start] == -1 && dfsChild > 1) { //when u have 2 or more children
return true;
}
if(parent[start] != -1 && low[v]>= disc[start])
return true;
} else if(v != parent[start]) //update low of start for previous call
low[start] = min(low[start], disc[v]);
}
}
return false;
}
bool isBiConnected() {
bool *vis = new bool[NODE];
int *disc = new int[NODE];
int *low = new int[NODE];
int *parent = new int[NODE];
for(int i = 0; i<NODE; i++) {
vis[i] = false; //no node is visited
parent[i] = -1; //initially there is no parent for any node
}
if(isArticulation(0, vis, disc, low, parent)) //when no articulation point is found
return false;
for(int i = 0; i<NODE; i++)
if(!vis[i]) //if any node is unvisited, the graph is not connected
return false;
return true;
}
int main() {
if(isBiConnected())
cout << "The Graph is a biconnected graph.";
else
cout << "The Graph is not a biconnected graph.";
}输出
The Graph is a biconnected graph.
更新于： 2020 年 6 月 16 日
3K+ 次浏览
广告