无向图双向连通.txt

无向图的双向连通

*
* Nodirectgrah.java
* 
* Created on 2007-12-3, 19:05:37
* 
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package nodirectgraph;
import java.util.*;
/**
*
* @author Administrator
*/
public class Nodirectgrah {
    Vector<graph> node=new Vector<graph>();
    Vector<String> backedge=new Vector<String>();
    Vector<String> preedge=new Vector<String>();
    Vector<String> edge=new Vector<String>();
    Vector<String> temp=new Vector<String>();
    String t="";
    public Nodirectgrah()
    {
        chu();
        cdfnumber();
        cbackedge();
        clow();
        display();
    }
    void chu()
    {
        edge.add("A B");
        edge.add("A C");
        edge.add("A D");
        edge.add("A E");
        edge.add("D B");
        edge.add("E B");
        edge.add("D E");
        edge.add("C F");
        edge.add("C G");
        edge.add("F G");
    }
    
       boolean isinedge(String s1,String s2)
    {
       boolean b=false;
       String[] newString= s2.split(" ");
       if(s1.compareTo(newString[0])==0)b=true;
       if(s1.compareTo(newString[1])==0)b=true;
       return b;
    }
    //计算dfnumber
    void cdfnumber()
    {
        int x=0;
        graph p=new graph();
        p.dfnumber=1;
        p.low=1;
        p.name="A";
        node.add(p);
        for(;x<node.size();x++)
        {
            for(int j=0;j<edge.size();j++)
            {
                if(isinedge(node.get(x).name,edge.get(j))&&isedgeexist(edge.get(j))==1)
                {
                    temp.add(edge.get(j));
                }
            }
            
            while(temp.size()>0)
            {
                if(isedgeexist(temp.get(temp.size()-1))==1)
                {
                    preedge.add(temp.get(temp.size()-1));
                    String te=new String(t);
                    graph q=new graph();
                    q.low=9999;
                    q.name=te; 
                    q.dfnumber=node.size()+1;
                    node.add(q);
                    break; 
                    
                }
                else temp.remove(temp.size()-1);
            }
           
        }
    }
    
    //找出后向边
    void cbackedge()
    {  int f;
        for(int i=0;i<edge.size();i++)
        { f=0;
            for(int j=0;j<preedge.size();j++)
            {
                if(edge.get(i).compareTo(preedge.get(j))==0)
                        f=1;
            }
            if(f==0)backedge.add(edge.get(i));
        }
    }
    //计算low
    void clow()
    {
        for(int k=0;k<node.size();k++)
        {
        for(int i=1;i<node.size();i++)
        {
            int min=node.get(i).low<node.get(i).dfnumber?node.get(i).low:node.get(i).dfnumber;
            for(int j=0;j<backedge.size();j++)
            {
                if(sub(node.get(i).name,backedge.get(j))==true)
                {
                   String[] newString= backedge.get(j).split(" ");
                   if(node.get(i).name.compareTo(newString[0])!=0)
                       if(min>getlow(newString[0]))min=getlow(newString[0]);
                   if(node.get(i).name.compareTo(newString[1])!=0)
                       if(min>getlow(newString[1]))min=getlow(newString[1]);
                }
            }
            for(int m=0;m<preedge.size();m++)
            if(min>childlow(node.get(i).name,preedge.get(m)))min=childlow(node.get(i).name,preedge.get(m));
            node.get(i).low=min;
        }
        }
    }
    int childlow(String s1,String s2)
    {
        int y=9999;
        if(sub(s1,s2))
        {
            String[] newString=s2.split(" ");
            if(s1.compareTo(newString[0])!=0&&getdfnumber(s1)<getdfnumber(newString[0]))y=getlow(newString[0]);
            else if(getdfnumber(s1)<getdfnumber(newString[1])) y=getlow(newString[1]);
        }
        return y;
    }
    //得到node i的low 值
    int getlow(String s)
    {
        int l=9999;
        for(int i=0;i<node.size();i++)
        {
            if((s.compareTo(node.get(i).name))==0)
                l=node.get(i).low;
        }
        return l; 
    }
    int getdfnumber(String s)
    {
        int l=9999;
        for(int i=0;i<node.size();i++)
        {
            if((s.compareTo(node.get(i).name))==0)
                l=node.get(i).dfnumber;
        }
        return l; 
    }

    int isedgeexist(String s)
    {
        int b=0;
        String str="";
        String[] newString= s.split(" ");
        if(isexist(newString[0])){b++;str=newString[1];}
        if(isexist(newString[1])){b++;str=newString[0];}
        if(b==1)
        {
            String z=new String(str);t=z;
        }    
        return b;
    }
    
    
    boolean isexist(String s)
    {
        boolean b=false;
        for(int i=0;i<node.size();i++)
            if(node.get(i).name.compareTo(s)==0)b=true;
        return b;
    }
    //判断字符串中是否存在子串
    boolean sub(String subs,String s)
    {
       boolean b=false;
       String [] newstring=s.split(" ");
       if(newstring[0].compareTo(subs)==0)b =true;
       else if(newstring[1].compareTo(subs)==0)b=true;
       return b;
    }
    void display()
    {
        System.out.println("node dfnumber low");
        for(int i=0;i<node.size();i++)
            System.out.println(node.get(i).name+"\t"+node.get(i).dfnumber+"\t"+node.get(i).low);
    }
    class graph
    {
        int flag=0;
        int dfnumber;
        int low=9999;
        String name;
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        new Nodirectgrah();
    }
}