{"id":26294,"date":"2017-10-26T20:53:30","date_gmt":"2017-10-26T15:23:30","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26294"},"modified":"2017-10-26T20:53:30","modified_gmt":"2017-10-26T15:23:30","slug":"calgorithm-biconnected-components","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/calgorithm-biconnected-components\/","title":{"rendered":"C++ Algorithm &#8211; Biconnected Components"},"content":{"rendered":"<p>A biconnected component is a maximal biconnected subgraph.<span id=\"more-133356\"><\/span><\/p>\n<p>Biconnected Graph is already discussed here. In this article, we will see how to find biconnected component in a graph using algorithm by John Hopcroft and Robert Tarjan.<\/p>\n<p>In above graph, following are the biconnected components:<\/p>\n<ul>\n<li>4\u20132 3\u20134 3\u20131 2\u20133 1\u20132<\/li>\n<li>8\u20139<\/li>\n<li>8\u20135 7\u20138 5\u20137<\/li>\n<li>6\u20130 5\u20136 1\u20135 0\u20131<\/li>\n<li>10\u201311<\/li>\n<\/ul>\n<p>Algorithm is based on Disc and Low Values discussed in Strongly Connected Components Article.<\/p>\n<p>Idea is to store visited edges in a stack while DFS on a graph and keep looking for Articulation Points (highlighted in above figure). As soon as an Articulation Point u is found, all edges visited while DFS from node u onwards will form one biconnected component. When DFS completes for one connected component, all edges present in stack will form a biconnected component.<br \/>\nIf there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p><strong>C++ Programming:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ A C++ program to find biconnected components in a given undirected graph<br\/>#include&lt;iostream&gt;<br\/>#include &lt;list&gt;<br\/>#include &lt;stack&gt;<br\/>#define NIL -1<br\/>using namespace std;<br\/>int count = 0;<br\/>class Edge<br\/>{<br\/>    public:<br\/>    int u;<br\/>    int v;<br\/>    Edge(int u, int v);<br\/>};<br\/>Edge::Edge(int u, int v)<br\/>{<br\/>    this-&gt;u = u;<br\/>    this-&gt;v = v;<br\/>}<br\/>  <br\/>\/\/ A class that represents an directed graph<br\/>class Graph<br\/>{<br\/>    int V;    \/\/ No. of vertices<br\/>    int E;    \/\/ No. of edges<br\/>    list&lt;int&gt; *adj;    \/\/ A dynamic array of adjacency lists<br\/>   <br\/>    \/\/ A Recursive DFS based function used by BCC()<br\/>    void BCCUtil(int u, int disc[], int low[],<br\/>                 list&lt;Edge&gt; *st, int parent[]);<br\/>public:<br\/>    Graph(int V);   \/\/ Constructor<br\/>    void addEdge(int v, int w);   \/\/ function to add an edge to graph<br\/>    void BCC();    \/\/ prints strongly connected components<br\/>};<br\/>   <br\/>Graph::Graph(int V)<br\/>{<br\/>    this-&gt;V = V;<br\/>    this-&gt;E = 0;<br\/>    adj = new list&lt;int&gt;[V];<br\/>}<br\/>   <br\/>void Graph::addEdge(int v, int w)<br\/>{<br\/>    adj[v].push_back(w);<br\/>    E++;<br\/>}<br\/>   <br\/>\/\/ A recursive function that finds and prints strongly connected<br\/>\/\/ components using DFS traversal<br\/>\/\/ u --&gt; The vertex to be visited next<br\/>\/\/ disc[] --&gt; Stores discovery times of visited vertices<br\/>\/\/ low[] -- &gt;&gt; earliest visited vertex (the vertex with minimum<br\/>\/\/             discovery time) that can be reached from subtree<br\/>\/\/             rooted with current vertex<br\/>\/\/ *st -- &gt;&gt; To store visited edges<br\/>void Graph::BCCUtil(int u, int disc[], int low[], list&lt;Edge&gt; *st,<br\/>                    int parent[])<br\/>{<br\/>    \/\/ A static variable is used for simplicity, we can avoid use<br\/>    \/\/ of static variable by passing a pointer.<br\/>    static int time = 0;<br\/>   <br\/>    \/\/ Initialize discovery time and low value<br\/>    disc[u] = low[u] = ++time;<br\/>    int children = 0;<br\/>   <br\/>    \/\/ Go through all vertices adjacent to this<br\/>    list&lt;int&gt;::iterator i;<br\/>    for (i = adj[u].begin(); i != adj[u].end(); ++i)<br\/>    {<br\/>        int v = *i;  \/\/ v is current adjacent of &#039;u&#039;<br\/>   <br\/>        \/\/ If v is not visited yet, then recur for it<br\/>        if (disc[v] == -1)<br\/>        {<br\/>            children++;<br\/>            parent[v] = u;<br\/>            \/\/store the edge in stack<br\/>            st-&gt;push_back(Edge(u,v));<br\/>            BCCUtil(v, disc, low, st, parent);<br\/>   <br\/>            \/\/ Check if the subtree rooted with &#039;v&#039; has a<br\/>            \/\/ connection to one of the ancestors of &#039;u&#039;<br\/>            \/\/ Case 1 -- per Strongly Connected Components Article<br\/>            low[u]  = min(low[u], low[v]);<br\/>  <br\/>            \/\/If u is an articulation point,<br\/>            \/\/pop all edges from stack till u -- v<br\/>            if( (disc[u] == 1 &amp;&amp; children &gt; 1) ||<br\/>                (disc[u] &gt; 1 &amp;&amp; low[v] &gt;= disc[u]) )<br\/>            {<br\/>                while(st-&gt;back().u != u || st-&gt;back().v != v)<br\/>                {<br\/>                    cout &lt;&lt; st-&gt;back().u &lt;&lt; &quot;--&quot; &lt;&lt; st-&gt;back().v &lt;&lt; &quot; &quot;;<br\/>                    st-&gt;pop_back();<br\/>                }<br\/>                cout &lt;&lt; st-&gt;back().u &lt;&lt; &quot;--&quot; &lt;&lt; st-&gt;back().v;<br\/>                st-&gt;pop_back();<br\/>                cout &lt;&lt; endl;<br\/>                count++;<br\/>            }<br\/>        }<br\/>   <br\/>        \/\/ Update low value of &#039;u&#039; only of &#039;v&#039; is still in stack<br\/>        \/\/ (i.e. it&#039;s a back edge, not cross edge).<br\/>        \/\/ Case 2 -- per Strongly Connected Components Article<br\/>        else if(v != parent[u] &amp;&amp; disc[v] &lt; low[u])<br\/>        {<br\/>            low[u]  = min(low[u], disc[v]);<br\/>            st-&gt;push_back(Edge(u,v));<br\/>        }<br\/>    }<br\/>}<br\/>   <br\/>\/\/ The function to do DFS traversal. It uses BCCUtil()<br\/>void Graph::BCC()<br\/>{<br\/>    int *disc = new int[V];<br\/>    int *low = new int[V];<br\/>    int *parent = new int[V];<br\/>    list&lt;Edge&gt; *st = new list&lt;Edge&gt;[E];<br\/>   <br\/>    \/\/ Initialize disc and low, and parent arrays<br\/>    for (int i = 0; i &lt; V; i++)<br\/>    {<br\/>        disc[i] = NIL;<br\/>        low[i] = NIL;<br\/>        parent[i] = NIL;<br\/>    }<br\/>   <br\/>    for (int i = 0; i &lt; V; i++)<br\/>    {<br\/>        if (disc[i] == NIL)<br\/>            BCCUtil(i, disc, low, st, parent);<br\/>          <br\/>        int j = 0;<br\/>        \/\/If stack is not empty, pop all edges from stack<br\/>        while(st-&gt;size() &gt; 0)<br\/>        {<br\/>            j = 1;<br\/>            cout &lt;&lt; st-&gt;back().u &lt;&lt; &quot;--&quot; &lt;&lt; st-&gt;back().v &lt;&lt; &quot; &quot;;<br\/>            st-&gt;pop_back();<br\/>        }<br\/>        if(j == 1)<br\/>        {<br\/>            cout &lt;&lt; endl;<br\/>            count++;<br\/>        }<br\/>    }<br\/>}<br\/>  <br\/>\/\/ Driver program to test above function<br\/>int main()<br\/>{<br\/>    Graph g(12);<br\/>    g.addEdge(0,1);g.addEdge(1,0);<br\/>    g.addEdge(1,2);g.addEdge(2,1);<br\/>    g.addEdge(1,3);g.addEdge(3,1);<br\/>    g.addEdge(2,3);g.addEdge(3,2);<br\/>    g.addEdge(2,4);g.addEdge(4,2);<br\/>    g.addEdge(3,4);g.addEdge(4,3);<br\/>    g.addEdge(1,5);g.addEdge(5,1);<br\/>    g.addEdge(0,6);g.addEdge(6,0);<br\/>    g.addEdge(5,6);g.addEdge(6,5);<br\/>    g.addEdge(5,7);g.addEdge(7,5);<br\/>    g.addEdge(5,8);g.addEdge(8,5);<br\/>    g.addEdge(7,8);g.addEdge(8,7);<br\/>    g.addEdge(8,9);g.addEdge(9,8);<br\/>    g.addEdge(10,11);g.addEdge(11,10);<br\/>    g.BCC();<br\/>    cout &lt;&lt; &quot;Above are &quot; &lt;&lt; count &lt;&lt; &quot; biconnected components in graph&quot;;<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>4--2 3--4 3--1 2--3 1--2\r\n8--9\r\n8--5 7--8 5--7\r\n6--0 5--6 1--5 0--1 \r\n10--11\r\nAbove are 5 biconnected components in graph\r\n<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C++ Algorithm &#8211; Biconnected Components -Graph Algorithm &#8211; A biconnected component is a maximal biconnected subgraph. Biconnected Graph is already discussed <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,74168,73906],"tags":[78213,78211,78212,78214,78208,78207,78206,78209,78215,78210,78216],"class_list":["post-26294","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-dfs-and-bfs","category-graph-algorithms","tag-biconnected-components-and-articulation-points-ppt","tag-biconnected-components-definition","tag-biconnected-components-of-an-undirected-graph","tag-biconnected-components-of-an-undirected-graph-ppt","tag-biconnected-components-pdf","tag-biconnected-graph-example","tag-biconnected-subgraph","tag-biconnectivity-algorithm","tag-biconnectivity-in-data-structure","tag-connected-components-in-daa","tag-what-is-articulation-point"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26294","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26294"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26294\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}