Untitled Document

Function

vector<Edge<T> > bridge();

Get the bridges of the graph. A bridge is any edge that when removed increases the number of connected components.

Parameters

None

Return value

Return a vector which contain all bridges of the graph.

Example

#include "HKUAL_graph.h"
#include <iostream>
#include <vector>
using namespace std;
using namespace HKUAL;

int main(){
    Graph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addVertex("D");
    g.addVertex("E");
    g.addVertex("F");
	
    g.addEdge("A","D");
    g.addEdge("A","E");
    g.addEdge("B","D");
    g.addEdge("C","D");
    g.addEdge("C","E");
    vector<Edge<string> > v = g.bridge();
    for (int i = 0; i < v.size(); i++)
       cout << v[i].X << ' ' << v[i].Y << endl;
    return 0;
}

Output

D B

Time Complexity

, for is number of edges and is total number of vertices.

Graph::bridge

Parameters

Return value