depthfirstdigraph.txt

用java语言深度优先回溯法实现有向图的强连通分量

import java.io.*;


public class Ndfs{
	
//	有向图顶点个数
	int vertexNumber;
	
	//声明变量在构造函数时定义数组变量
	///Vector<Boolean>  visited =new Vector<Boolean>();   //访问结点标识数组
	boolean visited[]=new boolean[100];
	//Vector<Integer> pos=new Vector<Integer>();//标志访问节点的序号  
     int pos[]=new int[100];
	//访问序号
	int visitedNumber=1;
	
    //定义构造函数，输入节点数
	public Ndfs(int graphVertexNumber) {
		//图的顶点个数赋值
		vertexNumber=graphVertexNumber;
	
	}
	
	
	//创建原有向图的邻接矩阵
	void creatGraAdjMatrix(int GA[][]) throws IOException
	{
		int i,j;
		BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
		   @SuppressWarnings("unused")
		String str;
		   
			
		System.out.println("请输入边，有关系输入1 无关系输入0");
		for(i=0;i<vertexNumber;i++)
			   for(j=0;j<vertexNumber;j++)
			   {
			     str=buf.readLine();
			     if(str.equals("quit"))
			    	 break;
			     GA[i][j]=Integer.parseInt(str); 
			     
			     }
		
	}
	
	
	//创建反向图的邻接矩阵;GA表示原图的邻接矩阵；GT表示反向图的邻接矩阵
	void creatRevGraAdjMatrix(int GA[][],int[][] GT) 
	{
		int i,j;
		
		for(i=0;i<vertexNumber;i++)
			   for(j=0;j<vertexNumber;j++)
			            GT[i][j]=GA[j][i]; 
			     
	}
	
	//深度优先遍历,标识各节点的访问序号
	void DFS(int[][] GA ,int i)
	{
		int j;
		//visited.setElementAt(true, i);
		visited[i]=true;
		for(j=0;j<vertexNumber;j++)
			if(GA[i][j]==1 && !visited[j])
				DFS(GA,j);	
		pos[visitedNumber++]=i;//标定访问节点序号	
        
	}
	
	//深度优先遍历反向图
	void DFSRevGrph(int[][] GT ,int i)
	{
		int j;
		//visited.setElementAt(true, i);
		visited[i]=true;
		for(j=0;j<vertexNumber;j++)
			if(GT[i][j]==1 && !visited[j])
				DFSRevGrph(GT,j);	       
	}
	
	//深度优先搜索有向图中所有节点；主要目的对图中顶点标号
	void DepthFirstSearch(int A[][])
	{
		int i;
		for(i=0;i<vertexNumber;i++)
			visited[i]=false;
		
		for(i=0;i<vertexNumber;i++)
			 if(!visited[i]) DFS(A,i);//某个节点没有访问则访问节点
			  
			
	}
	
	//深度优先遍历反向图
	void DFST(int[][] GT)
	{
		int j;
		int i;
		
		//Vector<Boolean> flagPrint= new Vector<Boolean>();//标记打印过的节点
		boolean flagPrint[]=new boolean[100];
		for(i=0;i<vertexNumber;i++)
			{
			  visited[i]=false;
			  flagPrint[i]=false;
			}
		
		for(j=vertexNumber;j>0;j--)
			
			 if(!visited[pos[j]])
				{  
				   DFSRevGrph(GT,pos[j]);//深度优先遍历反向图
				    for(i=0;i<vertexNumber;i++)
				    	if( !flagPrint[i] && visited[i])
				    	{
				    		System.out.print(i+" ");
				    		flagPrint[i]=true;
				    	}
				    
                  System.out.println();//换行另一类结点
				}
			
	}
	
//	打印矩阵
 void printMatrix(int A[][])
   {
   	int i,j;
   	
   	for(i=0;i<A.length;i++)
   		{
   		 for(j=0;j<A[i].length;j++)
   			 System.out.print(A[i][j]+" ");
    	      System.out.println();
   		}
   		System.out.println();	
   }
	 
	 
	 public static void main(String[] args)throws IOException{
		   
		   //输入结点个数
		   int vertex_number;
		  		   	   
		   BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
		   @SuppressWarnings("unused")
		   String str;
		   
		   System.out.println("请输入结点数");
		   str=buf.readLine();
		   vertex_number=Integer.parseInt(str);
		    //构造可达矩阵类
		   Ndfs C=new Ndfs(vertex_number);
		   
		   // 建立邻接矩阵
		   int GA[][]=new int[C.vertexNumber][C.vertexNumber];                             
		   C.creatGraAdjMatrix(GA);
		   
		   System.out.println("邻接矩阵GA：");
	      //打印显示邻接矩阵DSM
		   C.printMatrix(GA); 
		   
		   
		   //创建反向图可达矩阵
		   int GT[][]=new int[C.vertexNumber][C.vertexNumber]; 
		   C.creatRevGraAdjMatrix(GA, GT);  
		   
		   //打印可达矩阵
		   System.out.println("反向图邻接矩阵GT：");
		   C.printMatrix(GT);
		   
		  //深度优先遍历原图
		 C.DepthFirstSearch(GA);
		 
		 //深度优先遍历反向图
		 System.out.println("有向图强连通分量：");
		 C.DFST(GT);
		   
		   
			   }//end main
}