Code: |
public static boolean isBiconnected(Graph G){ int n=G.order(); // number or vertices boolean biCon = true; // is G biconnected? //Arrays needed for DFS int preOrder[] = new int[n]; int postOrder[] = new int[n]; int low[] = new int[n]; //this stores info when a back arc is discovered //Call DFS on G GraphAlgs.DFS(G, 0, preOrder, postOrder); //Compare the timestamps for (int i=0;i<n;i++){ low[i]=preOrder[i]; for (int j=0;j<n;j++){ low[i]=Math.min(low[i],preOrder[j]); if (low[j]<preOrder[i]) low[i]=Math.min(low[i],low[j]); else if (low[j]>=preOrder[i]) { //found articulation point, set boolean and break biCon = false; break; } } } //a back arc //(preOrder[i]<preOrder[j]&& postOrder[j]<postOrder[i]) return biCon; } |
Code: |
public static boolean isBiconnected(Graph G){
int n=G.order(); int preOrder[] = new int[n]; int postOrder[] = new int[n]; boolean biCon = true; Graph Gbak = G; for (int i=0;i<n;i++){ GraphAlgs.DFS(G, 0, preOrder, postOrder); G.removeVertex(i); //n=n-1; // preOrder = new int[n]; //postOrder = new int[n]; G = Gbak; if (GraphAlgs.isConnected(G)) biCon=true; else biCon=false; } return biCon; } |
output generated using printer-friendly topic mod, All times are GMT + 2 Hours