数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学双连通图
如果任意两点之间存在两条顶点不相交的通路，则将一个无向图称为双连通图。换句话说，我们可以说两点之间存在一个环。
我们可以说如果一个图是连通的，且没有关节点或割点存在，则该图是一个双连通图。
为了解决这个问题，我们将使用 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)
输入： 起始顶点、标记节点何时访问的访问数组、disk 将保存节点的发现时间，而 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)
输入：给定的图。
输出 − 如果图是双连通的则为真。
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.
更新日期： 16-Jun-2020
3K+ 浏览
广告