无向连通图中的顶点是一个连接点（或切割顶点），如果移除它（以及穿过它的边）会断开图的连接。连接点代表连接网络中的漏洞——单点故障会将网络拆分为两个或多个组件。它们对于设计可靠的网络很有用。
null
对于一个非连通的无向图，连接点是一个顶点移除，这会增加连接组件的数量。
下面是一些连接点被红色包围的示例图。
如何找到给定图形中的所有连接点？ 一种简单的方法是逐个移除所有顶点，然后查看移除顶点是否会导致图断开连接。下面是连通图的简单方法步骤。 1） 对于每个顶点v，执行以下操作 …..a） 从图中删除v …b）查看图表是否保持连接（我们可以使用BFS或DFS） …..c） 将v添加回图表 对于用邻接表表示的图，上述方法的时间复杂度为O（V*（V+E））。我们能做得更好吗？
寻找所有关节点（AP）的O（V+E）算法 其想法是使用DFS（深度优先搜索）。在DFS中，我们以树的形式跟踪顶点，称为DFS树。在DFS树中，一个顶点u是另一个顶点v的父节点，如果v是由u发现的（显然v是图中u的邻接点）。在DFS树中，如果以下两个条件之一为真，则顶点u为连接点。 1) u是DFS树的根，它至少有两个子树。 2) u不是DFS树的根，并且它有一个子v，因此在以v为根的子树中，没有一个顶点具有u的一个祖先（在DFS树中）的后缘。
下图显示了与上述相同的点，另外一点是DFS树中的叶子永远不能成为连接点。
我们使用额外的代码对给定的图进行DFS遍历，以找到连接点（AP）。在DFS遍历中，我们维护一个parent[]数组，其中parent[u]存储顶点u的父元素。在上述两种情况中，第一种情况很容易检测。对于每个顶点，计算子节点。如果当前访问的顶点u为根（父[u]为零），并且有两个以上的子节点，请打印它。
如何处理第二个案件？第二种情况更为棘手。我们维护一个数组disc[]来存储顶点的发现时间。对于每个节点u，我们需要找出最早访问的顶点（发现时间最短的顶点），该顶点可以从以u为根的子树中到达。因此，我们维护一个额外的数组low[]，其定义如下。
low[u] = min(disc[u], disc[w]) where w is an ancestor of u and there is a back edge from some descendant of u to w.
下面是Tarjan寻找关节点算法的实现。
C++
// C++ program to find articulation points in an undirected graph #include <bits/stdc++.h> using namespace std; // A recursive function that find articulation // points using DFS traversal // adj[] --> Adjacency List representation of the graph // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // low[] -- >> earliest visited vertex (the vertex with minimum // discovery time) that can be reached from subtree // rooted with current vertex // parent --> Stores the parent vertex in DFS tree // isAP[] --> Stores articulation points void APUtil(vector< int > adj[], int u, bool visited[], int disc[], int low[], int & time , int parent, bool isAP[]) { // Count of children in DFS Tree int children = 0; // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++ time ; // Go through all vertices adjacent to this for ( auto v : adj[u]) { // If v is not visited yet, then make it a child of u // in DFS tree and recur for it if (!visited[v]) { children++; APUtil(adj, v, visited, disc, low, time , u, isAP); // Check if the subtree rooted with v has // a connection to one of the ancestors of u low[u] = min(low[u], low[v]); // If u is not root and low value of one of // its child is more than discovery value of u. if (parent != -1 && low[v] >= disc[u]) isAP[u] = true ; } // Update low value of u for parent function calls. else if (v != parent) low[u] = min(low[u], disc[v]); } // If u is root of DFS tree and has two or more children. if (parent == -1 && children > 1) isAP[u] = true ; } void AP(vector< int > adj[], int V) { int disc[V] = { 0 }; int low[V]; bool visited[V] = { false }; bool isAP[V] = { false }; int time = 0, par = -1; // Adding this loop so that the // code works even if we are given // disconnected graph for ( int u = 0; u < V; u++) if (!visited[u]) APUtil(adj, u, visited, disc, low, time , par, isAP); // Printing the APs for ( int u = 0; u < V; u++) if (isAP[u] == true ) cout << u << " " ; } // Utility function to add an edge void addEdge(vector< int > adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } int main() { // Create graphs given in above diagrams cout << "Articulation points in first graph " ; int V = 5; vector< int > adj1[V]; addEdge(adj1, 1, 0); addEdge(adj1, 0, 2); addEdge(adj1, 2, 1); addEdge(adj1, 0, 3); addEdge(adj1, 3, 4); AP(adj1, V); cout << "Articulation points in second graph " ; V = 4; vector< int > adj2[V]; addEdge(adj2, 0, 1); addEdge(adj2, 1, 2); addEdge(adj2, 2, 3); AP(adj2, V); cout << "Articulation points in third graph " ; V = 7; vector< int > adj3[V]; addEdge(adj3, 0, 1); addEdge(adj3, 1, 2); addEdge(adj3, 2, 0); addEdge(adj3, 1, 3); addEdge(adj3, 1, 4); addEdge(adj3, 1, 6); addEdge(adj3, 3, 5); addEdge(adj3, 4, 5); AP(adj3, V); return 0; } |
JAVA
// A Java program to find articulation // points in an undirected graph import java.util.*; class Graph { static int time; static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } static void APUtil(ArrayList<ArrayList<Integer> > adj, int u, boolean visited[], int disc[], int low[], int parent, boolean isAP[]) { // Count of children in DFS Tree int children = 0 ; // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices adjacent to this for (Integer v : adj.get(u)) { // If v is not visited yet, then make it a child of u // in DFS tree and recur for it if (!visited[v]) { children++; APUtil(adj, v, visited, disc, low, u, isAP); // Check if the subtree rooted with v has // a connection to one of the ancestors of u low[u] = Math.min(low[u], low[v]); // If u is not root and low value of one of // its child is more than discovery value of u. if (parent != - 1 && low[v] >= disc[u]) isAP[u] = true ; } // Update low value of u for parent function calls. else if (v != parent) low[u] = Math.min(low[u], disc[v]); } // If u is root of DFS tree and has two or more children. if (parent == - 1 && children > 1 ) isAP[u] = true ; } static void AP(ArrayList<ArrayList<Integer> > adj, int V) { boolean [] visited = new boolean [V]; int [] disc = new int [V]; int [] low = new int [V]; boolean [] isAP = new boolean [V]; int time = 0 , par = - 1 ; // Adding this loop so that the // code works even if we are given // disconnected graph for ( int u = 0 ; u < V; u++) if (visited[u] == false ) APUtil(adj, u, visited, disc, low, par, isAP); for ( int u = 0 ; u < V; u++) if (isAP[u] == true ) System.out.print(u + " " ); System.out.println(); } public static void main(String[] args) { // Creating first example graph int V = 5 ; ArrayList<ArrayList<Integer> > adj1 = new ArrayList<ArrayList<Integer> >(V); for ( int i = 0 ; i < V; i++) adj1.add( new ArrayList<Integer>()); addEdge(adj1, 1 , 0 ); addEdge(adj1, 0 , 2 ); addEdge(adj1, 2 , 1 ); addEdge(adj1, 0 , 3 ); addEdge(adj1, 3 , 4 ); System.out.println( "Articulation points in first graph" ); AP(adj1, V); // Creating second example graph V = 4 ; ArrayList<ArrayList<Integer> > adj2 = new ArrayList<ArrayList<Integer> >(V); for ( int i = 0 ; i < V; i++) adj2.add( new ArrayList<Integer>()); addEdge(adj2, 0 , 1 ); addEdge(adj2, 1 , 2 ); addEdge(adj2, 2 , 3 ); System.out.println( "Articulation points in second graph" ); AP(adj2, V); // Creating third example graph V = 7 ; ArrayList<ArrayList<Integer> > adj3 = new ArrayList<ArrayList<Integer> >(V); for ( int i = 0 ; i < V; i++) adj3.add( new ArrayList<Integer>()); addEdge(adj3, 0 , 1 ); addEdge(adj3, 1 , 2 ); addEdge(adj3, 2 , 0 ); addEdge(adj3, 1 , 3 ); addEdge(adj3, 1 , 4 ); addEdge(adj3, 1 , 6 ); addEdge(adj3, 3 , 5 ); addEdge(adj3, 4 , 5 ); System.out.println( "Articulation points in third graph" ); AP(adj3, V); } } |
Python3
# Python program to find articulation points in an undirected graph from collections import defaultdict # This class represents an undirected graph # using adjacency list representation class Graph: def __init__( self , vertices): self .V = vertices # No. of vertices self .graph = defaultdict( list ) # default dictionary to store graph self .Time = 0 # function to add an edge to graph def addEdge( self , u, v): self .graph[u].append(v) self .graph[v].append(u) '''A recursive function that find articulation points using DFS traversal u --> The vertex to be visited next visited[] --> keeps track of visited vertices disc[] --> Stores discovery times of visited vertices parent[] --> Stores parent vertices in DFS tree ap[] --> Store articulation points''' def APUtil( self , u, visited, ap, parent, low, disc): # Count of children in current node children = 0 # Mark the current node as visited and print it visited[u] = True # Initialize discovery time and low value disc[u] = self .Time low[u] = self .Time self .Time + = 1 # Recur for all the vertices adjacent to this vertex for v in self .graph[u]: # If v is not visited yet, then make it a child of u # in DFS tree and recur for it if visited[v] = = False : parent[v] = u children + = 1 self .APUtil(v, visited, ap, parent, low, disc) # Check if the subtree rooted with v has a connection to # one of the ancestors of u low[u] = min (low[u], low[v]) # u is an articulation point in following cases # (1) u is root of DFS tree and has two or more children. if parent[u] = = - 1 and children > 1 : ap[u] = True #(2) If u is not root and low value of one of its child is more # than discovery value of u. if parent[u] ! = - 1 and low[v] > = disc[u]: ap[u] = True # Update low value of u for parent function calls elif v ! = parent[u]: low[u] = min (low[u], disc[v]) # The function to do DFS traversal. It uses recursive APUtil() def AP( self ): # Mark all the vertices as not visited # and Initialize parent and visited, # and ap(articulation point) arrays visited = [ False ] * ( self .V) disc = [ float ( "Inf" )] * ( self .V) low = [ float ( "Inf" )] * ( self .V) parent = [ - 1 ] * ( self .V) ap = [ False ] * ( self .V) # To store articulation points # Call the recursive helper function # to find articulation points # in DFS tree rooted with vertex 'i' for i in range ( self .V): if visited[i] = = False : self .APUtil(i, visited, ap, parent, low, disc) for index, value in enumerate (ap): if value = = True : print (index,end = " " ) # Create a graph given in the above diagram g1 = Graph( 5 ) g1.addEdge( 1 , 0 ) g1.addEdge( 0 , 2 ) g1.addEdge( 2 , 1 ) g1.addEdge( 0 , 3 ) g1.addEdge( 3 , 4 ) print ( "Articulation points in first graph " ) g1.AP() g2 = Graph( 4 ) g2.addEdge( 0 , 1 ) g2.addEdge( 1 , 2 ) g2.addEdge( 2 , 3 ) print ( "Articulation points in second graph " ) g2.AP() g3 = Graph ( 7 ) g3.addEdge( 0 , 1 ) g3.addEdge( 1 , 2 ) g3.addEdge( 2 , 0 ) g3.addEdge( 1 , 3 ) g3.addEdge( 1 , 4 ) g3.addEdge( 1 , 6 ) g3.addEdge( 3 , 5 ) g3.addEdge( 4 , 5 ) print ( "Articulation points in third graph " ) g3.AP() # This code is contributed by Neelam Yadav |
C#
// A C# program to find articulation // points in an undirected graph using System; using System.Collections.Generic; // This class represents an undirected graph // using adjacency list representation public class Graph { private int V; // No. of vertices // Array of lists for Adjacency List Representation private List< int >[] adj; int time = 0; static readonly int NIL = -1; // Constructor Graph( int v) { V = v; adj = new List< int >[v]; for ( int i = 0; i < v; ++i) adj[i] = new List< int >(); } // Function to add an edge into the graph void addEdge( int v, int w) { adj[v].Add(w); // Add w to v's list. adj[w].Add(v); // Add v to w's list } // A recursive function that find articulation points using DFS // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree // ap[] --> Store articulation points void APUtil( int u, bool [] visited, int [] disc, int [] low, int [] parent, bool [] ap) { // Count of children in DFS Tree int children = 0; // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++time; // Go through all vertices adjacent to this foreach ( int i in adj[u]) { int v = i; // v is current adjacent of u // If v is not visited yet, then make it a child of u // in DFS tree and recur for it if (!visited[v]) { children++; parent[v] = u; APUtil(v, visited, disc, low, parent, ap); // Check if the subtree rooted with v has // a connection to one of the ancestors of u low[u] = Math.Min(low[u], low[v]); // u is an articulation point in following cases // (1) u is root of DFS tree and has two or more children. if (parent[u] == NIL && children > 1) ap[u] = true ; // (2) If u is not root and low value of one of its child // is more than discovery value of u. if (parent[u] != NIL && low[v] >= disc[u]) ap[u] = true ; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = Math.Min(low[u], disc[v]); } } // The function to do DFS traversal. // It uses recursive function APUtil() void AP() { // Mark all the vertices as not visited bool [] visited = new bool [V]; int [] disc = new int [V]; int [] low = new int [V]; int [] parent = new int [V]; bool [] ap = new bool [V]; // To store articulation points // Initialize parent and visited, and // ap(articulation point) arrays for ( int i = 0; i < V; i++) { parent[i] = NIL; visited[i] = false ; ap[i] = false ; } // Call the recursive helper function to find articulation // points in DFS tree rooted with vertex 'i' for ( int i = 0; i < V; i++) if (visited[i] == false ) APUtil(i, visited, disc, low, parent, ap); // Now ap[] contains articulation points, print them for ( int i = 0; i < V; i++) if (ap[i] == true ) Console.Write(i + " " ); } // Driver method public static void Main(String[] args) { // Create graphs given in above diagrams Console.WriteLine( "Articulation points in first graph " ); Graph g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.AP(); Console.WriteLine(); Console.WriteLine( "Articulation points in Second graph" ); Graph g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.AP(); Console.WriteLine(); Console.WriteLine( "Articulation points in Third graph " ); Graph g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.AP(); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // A Javascript program to find articulation points in an undirected graph // This class represents an undirected graph using adjacency list // representation class Graph { // Constructor constructor(v) { this .V = v; this .adj = new Array(v); this .NIL = -1; this .time = 0; for (let i=0; i<v; ++i) this .adj[i] = []; } //Function to add an edge into the graph addEdge(v, w) { this .adj[v].push(w); // Add w to v's list. this .adj[w].push(v); //Add v to w's list } // A recursive function that find articulation points using DFS // u --> The vertex to be visited next // visited[] --> keeps track of visited vertices // disc[] --> Stores discovery times of visited vertices // parent[] --> Stores parent vertices in DFS tree // ap[] --> Store articulation points APUtil(u, visited, disc, low, parent, ap) { // Count of children in DFS Tree let children = 0; // Mark the current node as visited visited[u] = true ; // Initialize discovery time and low value disc[u] = low[u] = ++ this .time; // Go through all vertices adjacent to this for (let i of this .adj[u]) { let v = i; // v is current adjacent of u // If v is not visited yet, then make it a child of u // in DFS tree and recur for it if (!visited[v]) { children++; parent[v] = u; this .APUtil(v, visited, disc, low, parent, ap); // Check if the subtree rooted with v has a connection to // one of the ancestors of u low[u] = Math.min(low[u], low[v]); // u is an articulation point in following cases // (1) u is root of DFS tree and has two or more children. if (parent[u] == this .NIL && children > 1) ap[u] = true ; // (2) If u is not root and low value of one of its child // is more than discovery value of u. if (parent[u] != this .NIL && low[v] >= disc[u]) ap[u] = true ; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = Math.min(low[u], disc[v]); } } // The function to do DFS traversal. It uses recursive function APUtil() AP() { // Mark all the vertices as not visited let visited = new Array( this .V); let disc = new Array( this .V); let low = new Array( this .V); let parent = new Array( this .V); let ap = new Array( this .V); // To store articulation points // Initialize parent and visited, and ap(articulation point) // arrays for (let i = 0; i < this .V; i++) { parent[i] = this .NIL; visited[i] = false ; ap[i] = false ; } // Call the recursive helper function to find articulation // points in DFS tree rooted with vertex 'i' for (let i = 0; i < this .V; i++) if (visited[i] == false ) this .APUtil(i, visited, disc, low, parent, ap); // Now ap[] contains articulation points, print them for (let i = 0; i < this .V; i++) if (ap[i] == true ) document.write(i+ " " ); } } // Driver method // Create graphs given in above diagrams document.write( "Articulation points in first graph <br>" ); let g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.AP(); document.write( "<br>" ); document.write( "Articulation points in Second graph <br>" ); let g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.AP(); document.write( "<br>" ); document.write( "Articulation points in Third graph <br>" ); let g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.AP(); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Articulation points in first graph0 3Articulation points in second graph1 2Articulation points in third graph1
时间复杂性： 上面的函数是带有附加数组的简单DFS。因此，对于图的邻接表表示，时间复杂度与DFS相同，DFS是O（V+E）。
参考资料： https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf http://www.slideshare.net/TraianRebedea/algorithm-design-and-complexity-course-8 http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L25-Connectivity.htm 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
