第四周作业——无向图的DFS算法

墨蓝 2024-02-17 14:27 14阅读 0赞

![SouthEast][]

对上面图的DFS算法java代码：（实现遍历的顺序打印，以及判断连通分量的数量）

package four.suanfa.whp;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileOutputStream;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    public class GraphDFS {
    
    	/**
    	 * @王海平
    	 */
    	static int visited[];
    	static int vertex[];//图的节点数组
    	static int v;//图的节点的数目
    	static int e;//图的边的数目
    	static int arc_all[][];
    	static ArrayList<Integer> result=  new ArrayList<Integer>();
    	static int number=0;
    	
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		String path = "txt/tinyG.txt";
    		ArrayList<Integer> list = read(path);
    		// 调用产生邻接矩阵的函数
    		arc_all = MGraph(list);
    		System.out.println("深度优先节点访问顺序:");
    		// 深度优先调用,我们默认从0开始
    		DFS_init();
    		DFS(0);
    		int max=1;
    		while(max<vertex[vertex.length-1])
    		{
    			number=number+1;
    			for(int i=0;i<result.size();i++)
    			{
    				if(max<result.get(i))
    				{
    					max=result.get(i);
    				}	
    			}
    			if(max==vertex[vertex.length-1])
    			{
    				break;
    			}else
    			{	
    				DFS(max+1);
    			}
    				
    		};
    		System.out.println("");
    		System.out.println("连通分量的个数：");
    		System.out.println(number);
    		
    
    		
    		//写入tinyG_matrix.txt
    	}
    	//创建是否访问的记录数组和记录图节点的数组
    	public static void DFS_init(){
    		//创建一个数组用于记录是否已经访问并且初始化为0
    		visited=new int[v];
    		for(int i=0;i<visited.length;i++){
    			visited[i]=0;
    		}
    		vertex=new int[v];//初始化节点
    		for(int i=0;i<v;i++){
    			vertex[i]=i;
    		}
    		
    	}
    	//深度优先算法
    	public static void DFS(int n){	
    		visited[n]=1;
    		result.add(vertex[n]); //添加到结果中
    		System.out.print(vertex[n]+" ");
    		for(int j=0;j<v;j++)
    		{
    			if(arc_all[n][j]==1&&visited[j]==0){
    				DFS(j);
    			}
    		}
    	}
    	// 构造图的邻接矩阵函数
    	public static int[][] MGraph(ArrayList<Integer> list) {
    
    		// list数组中的前两个数据分别是图的顶点数目和边的数目
    		v = list.get(0);
    		e = list.get(1);
    		// 创建一个二维数组arc来存储邻接矩阵
    		int arc[][] = new int[v][e];
    		// 初始化邻接矩阵
    		for (int i = 0; i < v; i++) {
    			for (int j = 0; j < v; j++) {
    				arc[i][j] = 0;
    			}
    		}
    		//给邻接矩阵赋值，1表示边存在关系
    		for (int k = 0; k < e; k++) {
    			for (int q = 2; q < list.size() - 2; q = q + 2) {
    				arc[list.get(q)][list.get(q + 1)] = 1;
    				arc[list.get(q + 1)][list.get(q)] = 1;
    			}
    		}
    		return arc;
    
    	}
    
    	// 写入tinyG_matrix.txt
    	public static void write(int[][] arc) {
    		File f = new File("txt/tinyG_matrix.txt");
    		FileOutputStream fou = null;
    		String a="",b="";
    		try {
    
    			fou = new FileOutputStream(f, false);// true,设置可追加
    			for (int i = 0; i < arc.length; i++) {
    				for (int j = 0; j < arc[0].length; j++) {
    					a =a+String.valueOf(arc[i][j]);
    				}
    				a=a+"\t\n";
    			}
    			fou.write(a.getBytes());
    			
    		} catch (Exception e) {
    			// TODO: handle exception
    			e.printStackTrace();
    		} finally {
    			try {
    				fou.close();
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    	}
    
    	// 读取文件到Arraylist 数组
    	public static ArrayList read(String path) {
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		BufferedReader input = null;
    		try {
    			FileReader in = new FileReader(path);
    			input = new BufferedReader(in);
    			String ss;
    			try {
    				while ((ss = input.readLine()) != null) {
    					String[] s = (ss.split(" "));
    					for (int i = 0; i < s.length; i++) {
    						list.add(Integer.parseInt(s[i].trim())); // 将String
    																	// s中的内容添加到动态数组中
    					}
    
    				}
    			} catch (IOException e) {
    				// TODO 自动生成的 catch 块
    				e.printStackTrace();
    			}
    			in.close();
    			input.close();
    		} catch (Exception e) {
    			// TODO 自动生成的 catch 块
    			e.printStackTrace();
    		}
    
    		return list;
    	}
    
    }

运行结果：

![SouthEast 1][]

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3ad2a50e58e1442bbc7ceb31487be77d.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/0f78cc2e45694740b091491ec08c4940.png