{"id":27063,"date":"2018-01-02T21:58:23","date_gmt":"2018-01-02T16:28:23","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27063"},"modified":"2018-01-02T21:58:23","modified_gmt":"2018-01-02T16:28:23","slug":"c-programming-bridges-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-bridges-graph\/","title":{"rendered":"C++ programming Bridges in a graph"},"content":{"rendered":"

An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. <\/span>For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.
\nLike Articulation Points<\/a>,bridges represent vulnerabilities in a connected network and are useful for designing reliable networks. For example, in a wired computer network, an articulation point indicates the critical computers and a bridge indicates the critical wires or connections.<\/p>\n

Following are some example graphs with bridges highlighted with red color.<\/p>\n

How to find all bridges in a given graph?<\/strong>
\nA simple approach is to one by one remove all edges and see if removal of a edge causes disconnected graph. Following are steps of simple approach for connected graph.<\/p>\n

1) For every edge (u, v), do following
\n\u2026..a) Remove (u, v) from graph
\n..\u2026b) See if the graph remains connected (We can either use BFS or DFS)
\n\u2026..c) Add (u, v) back to the graph.<\/p>\n

Time complexity of above method is O(E*(V+E)) for a graph represented using adjacency list. Can we do better?<\/p>\n

A O(V+E) algorithm to find all Bridges<\/strong>
\nThe idea is similar to O(V+E) algorithm for Articulation Points<\/a>. We do DFS traversal of the given graph. In DFS tree an edge (u, v) (u is parent of v in DFS tree) is bridge if there does not exit any other alternative to reach u or an ancestor of u from subtree rooted with v. As discussed in the previous post<\/a>, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v. The condition for an edge (u, v) to be a bridge is, \u201clow[v] > disc[u]\u201d<\/em>.<\/p>\n[ad type=”banner”]\n

C++ programming :<\/p>\n

<\/div> 
\/\/ A C++ program to find bridges in a given undirected graph#include<iostream>#include <list>#define NIL -1using namespace std; \/\/ A class that represents an undirected graphclass Graph{    int V;    \/\/ No. of vertices    list<int> *adj;    \/\/ A dynamic array of adjacency lists    void bridgeUtil(int v, bool visited[], int disc[], int low[],                    int parent[]);public:    Graph(int V);   \/\/ Constructor    void addEdge(int v, int w);   \/\/ to add an edge to graph    void bridge();    \/\/ prints all bridges}; Graph::Graph(int V){    this->V = V;    adj = new list<int>[V];} void Graph::addEdge(int v, int w){    adj[v].push_back(w);    adj[w].push_back(v);  \/\/ Note: the graph is undirected} \/\/ A recursive function that finds and prints bridges using\/\/ DFS traversal\/\/ u --> The vertex to be visited next\/\/ visited[] --> keeps tract of visited vertices\/\/ disc[] --> Stores discovery times of visited vertices\/\/ parent[] --> Stores parent vertices in DFS treevoid Graph::bridgeUtil(int u, bool visited[], int disc[],                                   int low[], int parent[]){    \/\/ A static variable is used for simplicity, we can     \/\/ avoid use of static variable by passing a pointer.    static int time = 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 aadjacent to this    list<int>::iterator i;    for (i = adj[u].begin(); i != adj[u].end(); ++i)    {        int v = *i;  \/\/ v is current adjacent of u         \/\/ If v is not visited yet, then recur for it        if (!visited[v])        {            parent[v] = u;            bridgeUtil(v, visited, disc, low, parent);             \/\/ 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 the lowest vertex reachable from subtree             \/\/ under v is  below u in DFS tree, then u-v             \/\/ is a bridge            if (low[v] > disc[u])              cout << u <<" " << v << endl;        }         \/\/ Update low value of u for parent function calls.        else if (v != parent[u])            low[u]  = min(low[u], disc[v]);    }} \/\/ DFS based function to find all bridges. It uses recursive \/\/ function bridgeUtil()void Graph::bridge(){    \/\/ 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];     \/\/ Initialize parent and visited arrays    for (int i = 0; i < V; i++)    {        parent[i] = NIL;        visited[i] = false;    }     \/\/ Call the recursive helper function to find Bridges    \/\/ in DFS tree rooted with vertex 'i'    for (int i = 0; i < V; i++)        if (visited[i] == false)            bridgeUtil(i, visited, disc, low, parent);} \/\/ Driver program to test above functionint main(){    \/\/ Create graphs given in above diagrams    cout << "\\nBridges in first graph \\n";    Graph g1(5);    g1.addEdge(1, 0);    g1.addEdge(0, 2);    g1.addEdge(2, 1);    g1.addEdge(0, 3);    g1.addEdge(3, 4);    g1.bridge();     cout << "\\nBridges in second graph \\n";    Graph g2(4);    g2.addEdge(0, 1);    g2.addEdge(1, 2);    g2.addEdge(2, 3);    g2.bridge();     cout << "\\nBridges in third graph \\n";    Graph g3(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.bridge();     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Bridges in first graph\r\n3 4\r\n0 3\r\n\r\nBridges in second graph\r\n2 3\r\n1 2\r\n0 1\r\n\r\nBridges in third graph\r\n1 6<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C++ programming Bridges in a graph,An edge in an un directed connected graph is a bridge if removing it disconnects the graph.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[78385,73906],"tags":[79021,80897,83824,83825,83829,83819,83820,83823,83828,83822,80896,83827,83826,83821],"class_list":["post-27063","post","type-post","status-publish","format-standard","hentry","category-connectivity","category-graph-algorithms","tag-articulation-points-and-bridges","tag-articulation-points-in-a-graph","tag-bridge-design-pattern-c","tag-bridge-design-pattern-sourcemaking","tag-bridge-dfs","tag-bridge-pattern-c-example","tag-bridge-pattern-real-world-example","tag-c-patterns","tag-check-if-edge-is-bridge","tag-composite-pattern-c","tag-cut-vertex-graph-theory","tag-find-bridges-in-directed-graph","tag-source-making-bridge","tag-when-to-use-bridge-pattern"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27063","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=27063"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27063\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27063"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27063"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27063"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}