資料結構
網路
關係型資料庫管理系統
作業系統
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+ 次瀏覽
廣告