main.java

一个计算数据结构中图论的强连通分支问题的算法

import java.io.*;
import java.util.*;


public class Main {
	public static int n_Num;
	public static int Current_Component = 0;
	public static int DFS_N = 0;
	public static Node[] n = new Node[100];//所有点数组
	public static ArrayList<Node> stack = new ArrayList<Node>();//充当堆栈
	public static ArrayList<Edge> edges = new ArrayList<Edge>();//储存所有边
	public static TreeSet<Integer> component = new TreeSet<Integer> ();//储存经过排序的结点
	
	public static void main(String[] args){
		int i;
		Input();
		for (i = 0;i < n_Num;i++){
			n[i] = new Node();
			n[i].DFS_Number=0;
			n[i].Component=0;
			n[i].Num=i;
		}
		
		//计算出与每个结点有关联的结点list
		for (int t = 0;t < edges.size();t++){
			n[edges.get(t).v].next.add(edges.get(t).w);
		}
		Current_Component = 0;
		DFS_N = n_Num;
		
		for (i = 0; i < n_Num; i++){
			if(n[i].DFS_Number==0){
				SCC(n[i]);
			}
		}
		
		Output(component);
	}
	
	public static void SCC(Node v){
		v.DFS_Number = DFS_N;
		DFS_N -=1;
		stack.add(v);
		v.High = v.DFS_Number;
		
		for (int i = 0; i < v.next.size(); i++)
		{
			int w = v.next.get(i);
			if (n[w].DFS_Number == 0){
				SCC(n[w]);
				v.High=Max(v.High,n[w].High);
			} else
				if(n[w].DFS_Number>v.DFS_Number & n[w].Component == 0){
					v.High = Max(v.High,n[w].DFS_Number);
				
				}
		}
		if (v.High == v.DFS_Number){
			Current_Component+=1;
			
			while (stack.get(stack.size()-1).Num != v.Num)
			{
				n[stack.get(stack.size()-1).Num].Component = Current_Component;
				component.add(ConvertToCode(n[stack.get(stack.size()-1).Num]));
				stack.remove(stack.size()-1);
			}
			n[stack.get(stack.size()-1).Num].Component = Current_Component;
			component.add(ConvertToCode(n[stack.get(stack.size()-1).Num]));
			stack.remove(stack.size()-1);
		}
	}
	
	//将结点转化为以分支号为十位和结点号为个位的数，方便在Set中排序
	public static int ConvertToCode(Node n){
		return n.Component*10+n.Num;
	}
	
	//读文件
	public static void Input(){
		String data = "data4.dat";
		try{
			FileInputStream inpStream = new FileInputStream(new File(data));
			InputStreamReader inpData =new InputStreamReader(inpStream);
			BufferedReader reader=new BufferedReader(inpData);
			int v,w = 0;
			String str = "",line = "";
			String [] str_tmps = new String[2];
			if ((line = reader.readLine()) != null) {
				str = line;
			}
			n_Num = Integer.parseInt(str);
			while(1==1){
				if ((line = reader.readLine()) != null) {
					str = line;
				}
				else{break;}
				str = str.substring(1, str.length()-1);
				str_tmps = str.split(",");
				v = Integer.parseInt(str_tmps[0]);
				w = Integer.parseInt(str_tmps[1]);
				edges.add(new Edge(v,w));
			}
		}catch(IOException e){
			System.out.print("文件读取错误!\n");
		}
		finally{System.out.print("文件读取成功!\n");}
	}
	
	//写文件
	public static void Output(TreeSet<Integer> set){
		try
		{
			PrintWriter p = new PrintWriter(new File("result4.dat"));
			p.println(Current_Component);
			//利用Iterator遍历TreeSet
			Iterator<Integer> it=set.iterator();
			String str = "(";
			int current_num = 0,code = 0;
			for(int i = 1;i <= Current_Component;i++){
				while(it.hasNext()){
					code=it.next();
					current_num++;
					if (code/10 == i){
						str += code%(10*i)+",";
					}
					else{//遍历到下一个分支的结点时
						str = str.substring(0, str.length()-1);
						str += ")";
						p.println(str);
						str = "("+code%(10*(i+1))+",";
						break;
					}
					
				}
				//若迭代器遍历完毕
				if (code/10 == Current_Component & current_num == n_Num){
					str = str.substring(0, str.length()-1);
					str += ")";
					p.println(str);
				}
			}
			p.close();
		}
		catch(Exception e)
		{
			System.out.print("输出结果到result.txt时发生错误!\n");
		}
		finally{
			System.out.print("输出结果成功!\n");
		}
	}
	public static int Max(int x,int y){
		return (x>y)?x:y;
	}
	
}