Java数据结构之邻接表

谁践踏了优雅 2022-02-01 13:47 610阅读 0赞

# 基本概念 #

邻接表是由一个顺序存储结构的顶点表和多个链式存储的边表组成的。

# 邻接表类描述 #

### 边结点类 ###

package cho6;
    /**
     * 邻接表边结点类
     * @author asus
     *
     */
    public class ArcNode {
    	public int adjVex;//存放与当前顶点邻接的顶点在图中的位置
    	public int value;//边的权值
    	public ArcNode nextArc;//指向下一个边结点
    	public ArcNode() {
    		this(-1,0,null);
    	}
    	public ArcNode(int adjVex) {
    		this(adjVex,0,null);
    	}
    	public ArcNode(int adjVex,int value) {
    		this(adjVex,value,null);
    	}
    	public ArcNode(int adjVex,int value,ArcNode nextArc) {
    		this.adjVex = adjVex;
    		this.value = value;
    		this.nextArc = nextArc;
    	}
    }

### 顶点结点类 ###

package cho6;
    /**
     * 顶点结点类
     * @author asus
     *
     */
    public class VNode {
    	public Object data;//数据域，存放顶点值
    	public ArcNode firstArc;//指针域，指向第一个边结点
    	public VNode(){
    		this(null,null);
    	}
    	public VNode(Object data) {
    		this(data,null);
    	}
    	public VNode(Object data, ArcNode firstNode) {
    		this.data = data;
    		this.firstArc = firstNode;
    	}
    }

### 邻接表类 ###

package cho6;
    
    import java.util.Scanner;
    
    /**
     * 邻接表类
     * @author asus
     *
     */
     //相关接口定义参见页底
    public class ALGraph implements IGraph {
    	public enum graphKind {//构建图的枚举类型
    		UDG, DG, UDN, DN
    	};
    
    	private graphKind kind;
    	private int vNum, eNum;//保存顶点数和边数
    	private VNode[] v;//保存顶点的数组
    
    	public VNode[] getV() {
    		return v;
    	}
    
    	public void setV(VNode[] v) {
    		this.v = v;
    	}
    
    	public ALGraph() {
    		this(null, 0, 0, null);
    	}
    
    	public ALGraph(graphKind kind, int vNum, int eNum, VNode[] v) {
    		this.kind = kind;
    		this.vNum = vNum;
    		this.eNum = eNum;
    		this.v = v;
    	}
    	/**
    	 * 创建无向图
    	 */
    	private void createUDG() {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入顶点数");
    		vNum = sc.nextInt();//顶点数
    		System.out.println("输入边数");
    		eNum = sc.nextInt();//边数
    		v = new VNode[vNum];// 构造顶点集
    		System.out.println("输入各顶点");
    		for (int i = 0; i < vNum; i++) {
    			v[i] = new VNode(sc.next());
    		}
    		System.out.println("输入边关系");
    		for (int i = 0; i < eNum; i++) {
    			int u = locateVex(sc.nextInt());
    			int v = locateVex(sc.nextInt());
    			addArc(u,v,1);
    			addArc(v,u,1);
    		}
    	}
    
    	/**
    	 * 创建有向图
    	 */
    	private void createDG() {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入顶点数");
    		vNum = sc.nextInt();//顶点数
    		System.out.println("输入边数");
    		eNum = sc.nextInt();//边数
    		v = new VNode[vNum];// 构造顶点集
    		System.out.println("输入各顶点");
    		for (int i = 0; i < vNum; i++) {
    			v[i] = new VNode(sc.next());
    		}
    		System.out.println("输入边关系");
    		for (int i = 0; i < eNum; i++) {
    			int u = locateVex(sc.nextInt());
    			int v = locateVex(sc.nextInt());
    			addArc(u,v,1);
    		}
    	}
    	
    	/**
    	 * 创建无向网
    	 */
    	private void createUDN() {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入顶点数");
    		vNum = sc.nextInt();//顶点数
    		System.out.println("输入边数");
    		eNum = sc.nextInt();//边数
    		v = new VNode[vNum];// 构造顶点集
    		System.out.println("输入各顶点");
    		for (int i = 0; i < vNum; i++) {
    			v[i] = new VNode(sc.next());
    		}
    		System.out.println("输入边关系");
    		for (int i = 0; i < eNum; i++) {
    			int u = locateVex(sc.nextInt());
    			int v = locateVex(sc.nextInt());
    			int k = sc.nextInt();
    			addArc(u,v,k);
    			addArc(v,u,k);
    		}
    	}
    	
    	/**
    	 * 创建有向网
    	 */
    	private void createDN() {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入顶点数");
    		vNum = sc.nextInt();//顶点数
    		System.out.println("输入边数");
    		eNum = sc.nextInt();//边数
    		v = new VNode[vNum];// 构造顶点集
    		System.out.println("输入各顶点");
    		for (int i = 0; i < vNum; i++) {
    			v[i] = new VNode(sc.next());
    		}
    		System.out.println("输入边关系");
    		for (int i = 0; i < eNum; i++) {
    			int u = locateVex(sc.nextInt());
    			int v = locateVex(sc.nextInt());
    			int k = sc.nextInt();
    			addArc(u,v,k);
    		}
    	}
    
    	@Override
    	public void createGraph() {
    		switch (kind) {
    		case UDG:
    			createUDG();
    			break;
    		case DG:
    			createDG();
    			break;
    		case UDN:
    			createUDN();
    			break;
    		case DN:
    			createDN();
    			break;
    		}
    	}
    
    	//通过邻接矩阵创建邻接表
    	public void createGraph(int[][] matrix) {
    		vNum = matrix.length;
    		v = new VNode[vNum];
    		for(int i=0;i<vNum;i++) {
    			v[i] = new VNode(i);
    		}
    		for(int i=0;i<vNum;i++) {
    			for(int j=0;j<vNum;j++) {
    				if(0 < matrix[i][j] && matrix[i][j] < Integer.MAX_VALUE) {
    					addArc(i,j,matrix[i][j]);
    				}
    			}
    		}
    	}
    	
    	/**
    	 * 在边链表中添加由顶点i指向顶点j的权值为value的边结点，采用头插法
    	 * @param i 指向的顶点
    	 * @param j	被指向的顶点
    	 * @param value 权值
    	 */
    	public void addArc(int i,int j,int value) {
    		ArcNode arc = new ArcNode(j,value);
    		arc.nextArc = v[i].firstArc;
    		v[i].firstArc = arc;
    	}
    	
    	@Override
    	public int getVNum() {
    		return vNum;
    	}
    
    	@Override
    	public int getENum() {
    		return eNum;
    	}
    
    	@Override
    	public Object getVex(int i) {
    		return v[i];
    	}
    
    	/**
    	 * 获取元素x在顶点集v中的位置
    	 */
    	public int locateVex(Object x) {
    		for(int i=0;i<v.length;i++) {
    			if(v[i].equals(x))
    				return i;
    		}
    		return -1;
    	}
    
    	//查找第一个邻接点
    	public int firstAdj(int i) throws Exception{
    		if(i<0||i>vNum)
    			throw new Exception("第" + i + "个顶点不存在！");
    		ArcNode p = v[i].firstArc;
    		if(p!=null)
    			return p.adjVex;
    		return -1;
    	}
    
    	//查找下一个邻接点
    	public int nextAdj(int i, int j) {
    		ArcNode p = v[i].firstArc;
    		for(;p!=null;p=p.nextArc) {
    			if(p.adjVex==j)
    				break;
    		}
    		if(p.nextArc!=null)
    			return p.nextArc.adjVex;
    		return -1;
    	}
    
    	//获取顶点入度
    	public int[] getInDegree() {
    		int[] inDegree = new int[vNum];
    		for(int i=0;i<vNum;i++) {
    			for(ArcNode node = v[i].firstArc;node !=null;node=node.nextArc) {
    				inDegree[node.adjVex]++;
    			}
    		}
    		
    		return inDegree;
    	}
    	
    	//获取顶点出度
    	public int[] getOutDegree() {
    		int[] outDegree = new int[vNum];
    		for(int i=0;i<vNum;i++) {
    			for(ArcNode node = v[i].firstArc;node !=null;node=node.nextArc) {
    				outDegree[i]++;
    			}
    		}
    		
    		return outDegree;
    	}
    }

### 参考接口 ###

> [IGraph][]

# 邻接表性能分析 #

1.  由于邻接矩阵采用链表结构，故增删操作的效率较高，而查找元素需要从顶点一次向后遍历，效率较低。
2.  由于邻接矩阵在存储时只会保存与之邻接的顶点，因此在存储一个完全图或稠密图时，存储效率较低；在存储一个稀疏图时，存储效率较高。

[IGraph]: https://blog.csdn.net/weixin_44270248/article/details/90202819