{"id":26307,"date":"2017-10-26T20:57:47","date_gmt":"2017-10-26T15:27:47","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26307"},"modified":"2017-10-26T20:57:47","modified_gmt":"2017-10-26T15:27:47","slug":"java-algorithm-biconnected-components","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-biconnected-components\/","title":{"rendered":"Java 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>Java Programming:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ A Java program to find biconnected components in a given<br\/>\/\/ undirected graph<br\/>import java.io.*;<br\/>import java.util.*;<br\/> <br\/>\/\/ This class represents a directed graph using adjacency<br\/>\/\/ list representation<br\/>class Graph<br\/>{<br\/>    private int V, E; \/\/ No. of vertices &amp; Edges respectively<br\/>    private LinkedList&lt;Integer&gt; adj[];    \/\/ Adjacency List<br\/> <br\/>    \/\/ Count is number of biconnected components. time is<br\/>    \/\/ used to find discovery times<br\/>    static int count = 0, time = 0;<br\/> <br\/>    class Edge<br\/>    {<br\/>        int u;<br\/>        int v;<br\/>        Edge(int u, int v)<br\/>        {<br\/>            this.u = u;<br\/>            this.v = v;<br\/>        }<br\/>    };<br\/> <br\/>    \/\/Constructor<br\/>    Graph(int v)<br\/>    {<br\/>        V = v;<br\/>        E = 0;<br\/>        adj = new LinkedList[v];<br\/>        for (int i=0; i&lt;v; ++i)<br\/>            adj[i] = new LinkedList();<br\/>    }<br\/> <br\/>    \/\/Function to add an edge into the graph<br\/>    void addEdge(int v,int w)<br\/>    {<br\/>        adj[v].add(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 BCCUtil(int u, int disc[], int low[], LinkedList&lt;Edge&gt;st,<br\/>                 int parent[])<br\/>    {<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\/>        Iterator&lt;Integer&gt; it = adj[u].iterator();<br\/>        while (it.hasNext())<br\/>        {<br\/>            int v = it.next();  \/\/ 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\/> <br\/>                \/\/ store the edge in stack<br\/>                st.add(new 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\/>                if (low[u] &gt; low[v])<br\/>                    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.getLast().u != u || st.getLast().v != v)<br\/>                    {<br\/>                        System.out.print(st.getLast().u + &quot;--&quot; +<br\/>                                         st.getLast().v + &quot; &quot;);<br\/>                        st.removeLast();<br\/>                    }<br\/>                    System.out.println(st.getLast().u + &quot;--&quot; +<br\/>                                       st.getLast().v + &quot; &quot;);<br\/>                    st.removeLast();<br\/> <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\/>                if (low[u]&gt;disc[v])<br\/>                    low[u]=disc[v];<br\/>                st.add(new Edge(u,v));<br\/>            }<br\/>        }<br\/>    }<br\/> <br\/>    \/\/ The function to do DFS traversal. It uses BCCUtil()<br\/>    void BCC()<br\/>    {<br\/>        int disc[] = new int[V];<br\/>        int low[] = new int[V];<br\/>        int parent[] = new int[V];<br\/>        LinkedList&lt;Edge&gt; st = new LinkedList&lt;Edge&gt;();<br\/> <br\/>        \/\/ Initialize disc and low, and parent arrays<br\/>        for (int i = 0; i &lt; V; i++)<br\/>        {<br\/>            disc[i] = -1;<br\/>            low[i] = -1;<br\/>            parent[i] = -1;<br\/>        }<br\/> <br\/>        for (int i = 0; i &lt; V; i++)<br\/>        {<br\/>            if (disc[i] == -1)<br\/>                BCCUtil(i, disc, low, st, parent);<br\/> <br\/>            int j = 0;<br\/> <br\/>            \/\/ If stack is not empty, pop all edges from stack<br\/>            while (st.size() &gt; 0)<br\/>            {<br\/>                j = 1;<br\/>                System.out.print(st.getLast().u + &quot;--&quot; +<br\/>                                 st.getLast().v + &quot; &quot;);<br\/>                st.removeLast();<br\/>            }<br\/>            if (j == 1)<br\/>            {<br\/>                System.out.println();<br\/>                count++;<br\/>            }<br\/>        }<br\/>    }<br\/> <br\/>    public static void main(String args[])<br\/>    {<br\/>        Graph g = new Graph(12);<br\/>        g.addEdge(0,1);<br\/>        g.addEdge(1,0);<br\/>        g.addEdge(1,2);<br\/>        g.addEdge(2,1);<br\/>        g.addEdge(1,3);<br\/>        g.addEdge(3,1);<br\/>        g.addEdge(2,3);<br\/>        g.addEdge(3,2);<br\/>        g.addEdge(2,4);<br\/>        g.addEdge(4,2);<br\/>        g.addEdge(3,4);<br\/>        g.addEdge(4,3);<br\/>        g.addEdge(1,5);<br\/>        g.addEdge(5,1);<br\/>        g.addEdge(0,6);<br\/>        g.addEdge(6,0);<br\/>        g.addEdge(5,6);<br\/>        g.addEdge(6,5);<br\/>        g.addEdge(5,7);<br\/>        g.addEdge(7,5);<br\/>        g.addEdge(5,8);<br\/>        g.addEdge(8,5);<br\/>        g.addEdge(7,8);<br\/>        g.addEdge(8,7);<br\/>        g.addEdge(8,9);<br\/>        g.addEdge(9,8);<br\/>        g.addEdge(10,11);<br\/>        g.addEdge(11,10);<br\/> <br\/>        g.BCC();<br\/> <br\/>        System.out.println(&quot;Above are &quot; + g.count +<br\/>                           &quot; biconnected components in graph&quot;);<br\/>    }<br\/>}<br\/>\/\/ This code is contributed by Aakash Hasija<\/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>Java 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":[69969,1,74168,73906,2139],"tags":[78259,78213,78211,78212,78214,78208,78260,78207,78209,78210,78261],"class_list":["post-26307","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-java","tag-biconnected-components-algorithm","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-components-ppt","tag-biconnected-graph-example","tag-biconnectivity-algorithm","tag-connected-components-in-daa","tag-how-to-find-biconnected-components-of-a-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26307","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=26307"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26307\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}