# **Bridge Detection Algorithm**
In an undirected connected graph, a bridge is an edge that if cut, the graph will no longer be connected. For example, every edge in a (undirected) tree is a bridge edge. As another example, a simple cycle graph does not have any edge.

Devise an efficient algorithm to identify all bridge edges in an undirected connected graph.
# **Algorithm**
The following algorithm uses the function bridge_detection(G) to do a depth-first search traversal on the graph while keeping two arrays. The first array keeps track of the discovery time of the ```u``` vertex, while the second array has the lowest discovery time reachable from ```u```, including edges.

fun bridge_detection(G){
    var time = 0;
    
    for(e in vertex G){
        if(!visited[u]){
            FDS(u, visited, disc, low, parent, time);
        }
    }
}

fun DFS(u){
    visited[u] = true;
    
    disc[u] = low[u] = time++;
    
    for(v in adj[u]){
        if(!visited[v]){
            parent[v] = u;
            DFS(v);
            low[u] = min(low[u], low[v]);
            
            if(low[v] > disc[u]){
            print(u, v);
            }
        }
        
        else if(v != parent[u]){
            low[u] = min(low[u], disc[v]);
        }
    }
}

# **Correctness Proof**
**Goal:** the function bridge_detection(G) will correctly find all bridge edges in an undirected connected graph

**Base Cases:**
* vertex ```u``` has no parent: if there is no back edge from v or its descendants to u for any single edge (u,v) --> low[v] > disc[u] must be true, marking (u,v) correctly as a bridge

**Inductive Hypothesis:**
Assume that for all nodes discovered before ```u```, the algorithm will correctly identify all bridge edges in an undirected connected graph by computing the discovery time of x.

* for every neighbor v --> if v is not visited, recurse DFS(v), update low[u] to equal min(low[u], low[v]). If low[v] > disc[u], there is no back edge from v or the descendants to u, making (u, v) a bridge
* if v IS visited and is not the parent of u --> update low[u] to equal min(low[u], disc[v]) to account for back edges

Thus, by induction, the algorithm correctly computes and finds all bridge edges in an undirected connected graph.

# **Time Complexity**
Each vertex and edge is visited exactly once in DFS

* n --> # of vertices
* m --> # of edges

Thus,
* T(n) = O(n + m)