双向图

如果在任意两个顶点之间存在两个不相交的顶点路径，则无向图被称为双向图。换句话说，我们可以说任意两个顶点之间都有一个循环。

可以说，如果图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:
该图是一个双向图。

算法

isArticulation （开始，访问，光盘，低位，父级）

输入： 起始顶点，用来标记何时访问节点的访问数组，光盘将保留该顶点的发现时间，而低位将保留有关子树的信息。父级将保留当前顶点的父级。

输出-如果找到任何铰接点，则为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（图）

输入：给定的图形。

输出-如果图形是双向连接，则为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 << "该图是一个双向图。";
   else
      cout << "该图不是双向图。";
}

输出结果

该图是一个双向图。