第五周作业——有向图邻接表表示及反向

「爱情、让人受尽委屈。」 2024-02-17 14:28 6阅读 0赞

1. **有向图中反向图构造**。对[tinyDG.txt][]（http://pan.baidu.com/s/1o6jWtcA）文件所表示的图，输出其邻接表表示 与 反向图的邻接表表示。**类名**：**GraphReverse**。**博文标题：第五周作业——有向图邻接表表示及反向图构造**

![SouthEast][]

有向图的邻接表表示

源码：（包括三个类）

Vertex 类
    package fiv.suanfa.whp;
    
    public class Vertex {
    
    	int data;
    	Edge adj;
    }
    Edge 类
    package fiv.suanfa.whp;
    public class Edge {
    
    	int dest;
    	Edge link;
    
    	Edge(int D)
    	{
    		dest=D;
    		link=null;
    	}
    
    }
    
    
    
    GraphReverse类
    package fiv.suanfa.whp;
    
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    public class GraphReverse {
    
    	/**
    	 * @Author 王海平
    	 */
    	public static void main(String args []){
    		String path = "txt/tinyDG.txt";
    		ArrayList<Integer> list = read(path);
    		
    		int vn=list.get(0);//图的顶点数
    		int en=list.get(1);//图的边数
    		int b[][] = new int[list.get(1)][2];
    		int v[] = new int[list.size()];//顶点数组
    		for(int i=0;i<vn;i++){//顶点数组初始化
    			v[i]=i;
    		}
    		
    			//反向图的邻接表
    
    			/*int k=(list.get(1)+1)*2-1; //最后一个
    			
    			for(int i=0;i<list.get(1);i++){
    				for(int j=0;j<2;j++){	
    						b[i][j]=list.get(k);
    						k--;
    				}
    			}*/
    		//图的邻接表
    		int k=2; //最后一个
    		//将一位数组的值加入到二维数组中
    		for(int i=0;i<list.get(1);i++){
    			for(int j=0;j<2;j++){	
    					b[i][j]=list.get(k);
    					k++;
    			}
    		}
    		GraphReverse G=new GraphReverse();
    		G.Graphadj(vn, v, en, b);
    		G.display();
    	}
    	
    	
    	static int DefalutSize=20;
    	private Vertex NodeTable[];//顶点表
    	private int NumVertices=0;
    	private int NumEdges=0;
    	
    	public void Graphadj(int vn,int v[],int en,int e[][]){
    		//形参：顶点数 顶点数组 边数 边节点数组 
    
    		//创建顶点表
    		NodeTable=new Vertex[vn];
    		//输入顶点
    		for(int i=0;i<vn;i++){
    			InsertVertex(v[i]);
    		}
    		//输入边
    		for(int i=0;i<en;i++)
    		{
    			InsertEdge(e[i][0],e[i][1]);
    		}
    	}
    	
    	//增加结点
    	public boolean InsertVertex(int vertex)
    	{
    		Vertex t=new Vertex();
    		t.data=vertex;
    		t.adj=null;
    		NodeTable[NumVertices]=t;
    		NumVertices++;
    		return true;
    	}
    	//增加边
    	public boolean InsertEdge(int v1,int v2){
    		if(v1>NumVertices||v1<0)
    			return false;
    		if(v2>NumVertices||v2<0)
    			return false;
    		//生成一个边结点
    		Edge E=new Edge(v2);
    		
    		Edge p=NodeTable[v1].adj;
    		if(p==null)
    			NodeTable[v1].adj=E;
    		else{
    			while(p.link!=null) p=p.link;
    			p.link=E;
    		}
    		NumEdges++;
    		return true;
    	}
    	
    	public void display(){
    		Edge p;
    		for(int i=0;i<NumVertices;i++){
    			System.out.print(NodeTable[i].data+":");
    			p=NodeTable[i].adj;
    			while(p!=null)
    			{
    				System.out.print(p.dest+" ");
    				
    				p=p.link;
    			}
    			System.out.println();
    			
    		}
    	}
    	
    	// 读取文件到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][]

如果我们将GraphReverse类中的注释代码解注释，让后将相应的地方加注释，运行可以得到相应反向图邻接表的结果：

反向图结果:

![SouthEast 2][]

[tinyDG.txt]: http://pan.baidu.com/s/1o6jWtcA
[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e2712934edea49c9ad02aedaf7e4436a.png
[SouthEast 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c9a982f44ab54846a120942206baf64b.png
[SouthEast 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ccbc6e09cf264d38848c7d4ada715d7c.png