第四周作业——图的表示

柔情只为你懂 2024-02-17 14:27 11阅读 0赞

1. 图的表示：给定图数据文件（[tinyG.txt][]），计算得到图的邻接矩阵，并把邻接矩阵保存到文件（tinyG\_matrix.txt）中。类名：GraphRepresentation

![Image 1][]![SouthEast][]

源码：

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 GraphRepresentation {
    
    	/**
    	 * @王海平
    	 */
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		String path = "txt/tinyG.txt";
    		ArrayList<Integer> list = read(path);
    		// 调用产生邻接矩阵的函数
    		int[][] arc = MGraph(list);
    		// 控制台打印邻接矩阵
    		for (int i = 0; i < arc.length; i++) {
    			for (int j = 0; j < arc[0].length; j++) {
    				System.out.print(arc[i][j]);
    			}
    			System.out.println("");
    		}
    		//写入tinyG_matrix.txt
    		write(arc);
    	}
    
    	// 构造图的邻接矩阵函数
    	public static int[][] MGraph(ArrayList<Integer> list) {
    
    		// list数组中的前两个数据分别是图的顶点数目和边的数目
    		int v = list.get(0);
    		int 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][]

txt中的结果：

![SouthEast 2][]

[tinyG.txt]: http://pan.baidu.com/s/1i39iR0T
[Image 1]: 
[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f7b24f136a2841e8815403bc1af54049.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/0ac0a15ba9954f58bc3d188195569af1.png
[SouthEast 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e2bcf20639834bf4b0bb18f661ceb18d.png