資料結構
網路
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+ 瀏覽
廣告