Java数据结构之邻接矩阵

太过爱你忘了你带给我的痛 2022-02-01 11:29 298阅读 0赞

# 基本概念 #

图的存储结构需要保存顶点的值及与顶点相关联的顶点和边的信息。  
假设图G=(V,E)具有n个顶点，则可以构建矩阵A\[n\]\[n\]来保存图中的数据关系，称A\[n\]\[n\]为邻接矩阵。定义如下：  
![在这里插入图片描述][20190514161855165.PNG_pic_center]  
如果图G=(V,E)为网，且wij为边上权值，则定义如下：  
![在这里插入图片描述][2019051416210261.PNG_pic_center]

> 从邻接矩阵的定义可以得知：
> 
> 1.  无向图的邻接矩阵为对称阵，无向图的第i行或第i列非0元素的个数为第i个顶点的度。
> 2.  有向图不一定为对称阵，有向图的第i行非0和无穷元素的个数为第i个元素的出度，第i行的非0和无穷元素的个数为第i个元素的入度。

# 邻接矩阵类描述 #

package cho6;
    
    import java.util.Scanner;
    //相关接口定义参见页底
    public class MGraph implements IGraph {
    	public enum graphKind {//构建图的枚举类型
    		UDG, DG, UDN, DN
    	};
    
    	private graphKind kind;
    	private int vNum, eNum;//保存顶点数和边数
    	private Object[] v;//保存顶点的数组
    	private int[][] e;//保存边的数组——邻接矩阵
    	int visited[];
    
    	public MGraph() {
    		this(null, 0, 0, null, null);
    	}
    
    	public MGraph(graphKind kind) {
    		this(kind, 0, 0, null, null);
    	}
    
    	public MGraph(graphKind kind, int vNum, int eNum, Object[] v, int[][] e) {
    		this.kind = kind;
    		this.vNum = vNum;
    		this.eNum = eNum;
    		this.v = v;
    		this.e = e;
    	}
    
    	/**
    	 * 创建无向图
    	 */
    	private void createUDG() {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入顶点数");
    		vNum = sc.nextInt();//顶点数
    		System.out.println("输入边数");
    		eNum = sc.nextInt();//边数
    		v = new Object[vNum];// 构造顶点集
    		System.out.println("输入各顶点");
    		for (int i = 0; i < vNum; i++) {
    			v[i] = sc.next();
    		}
    		e = new int[vNum][vNum];// 构造边集
    		System.out.println("输入边关系");
    		for (int i = 0; i < eNum; i++) {
    			int m = locateVex(sc.next());
    			int n = locateVex(sc.next());
    			e[m][n] = e[n][m] = 1;
    		}
    //		sc.close();
    	}
    
    	/**
    	 * 创建有向图
    	 */
    	private void createDG() {
    		Scanner sc = new Scanner(System.in);
    		vNum = sc.nextInt();
    		eNum = sc.nextInt();
    		for(int i=0;i<vNum;i++) {
    			v[i] = sc.next();
    		}
    		e = new int[vNum][vNum];
    		for(int i=0;i<eNum;i++) {
    			int m = locateVex(sc.next());
    			int n = locateVex(sc.next());
    			e[m][n] = 1;
    		}
    //		sc.close();
    	}
    	
    	/**
    	 * 创建无向网
    	 */
    	private void createUDN() {
    		Scanner sc = new Scanner(System.in);
    		if(v==null) {
    			vNum = sc.nextInt();
    			eNum = sc.nextInt();
    			v = new Object[vNum];
    			for(int i=0;i<vNum;i++) {
    				v[i] = sc.next();
    			}
    			e = new int[vNum][vNum];
    			for(int i=0;i<vNum;i++) {
    				for(int j=0;j<vNum;j++) {
    					e[i][j] = Integer.MAX_VALUE;
    				}
    			}
    			for(int i=0;i<eNum;i++) {
    				int m = locateVex(sc.next());
    				int n = locateVex(sc.next());
    				e[m][n] = e[n][m] = sc.nextInt();
    			}
    		}
    //		sc.close();
    	}
    	
    	/**
    	 * 创建有向网
    	 */
    	private void createDN() {
    		Scanner sc = new Scanner(System.in);
    		vNum = sc.nextInt();
    		eNum = sc.nextInt();
    		v = new Object[vNum];
    		for(int i=0;i<vNum;i++) {
    			v[i] = sc.next();
    		}
    		e = new int[vNum][vNum];
    		for(int i=0;i<vNum;i++) {
    			for(int j=0;j<vNum;j++) {
    				e[i][j] = Integer.MAX_VALUE;
    			}
    		}
    		for(int i=0;i<eNum;i++) {
    			int m = locateVex(sc.next());
    			int n= locateVex(sc.next());
    			e[m][n] = sc.nextInt();
    		}
    //		sc.close();
    	}
    	
    	@Override
    	public void createGraph() {
    		switch(kind) {
    			case UDG:
    				createUDG();
    				break;
    			case DG:
    				createDG();
    				break;
    			case UDN:
    				createUDN();
    				break;
    			case DN:
    				createDN();
    				break;
    		}
    	}
    
    	//获取顶点数
    	public int getVNum() {
    		return vNum;
    	}
    
    	//获取边数
    	public int getENum() {
    		return eNum;
    	}
    
    	//返回位置i的顶点值
    	public Object getVex(int i) {
    		return v[i];
    	}
    	
    	//返回邻接数组
    	public int[][] getE() {
    		return e;
    	}
    
    	/**
    	 * 获取元素x在顶点集v中的位置
    	 */
    	public int locateVex(Object x) {
    		for(int i=0;i<v.length;i++) {
    			if(v[i].equals(x))
    				return i;
    		}
    		return -1;
    	}
    
    	/**
    	 * 查找第一个邻接点
    	 * 查找顶点i的第一个邻接点的位置
    	 * @param int i 顶点在顶点集中的位置i
    	 * @return int 返回第一个邻接点的位置  
    	 */
    	public int firstAdj(int i) throws Exception{
    		if(i<0||i>vNum)
    			throw new Exception("第" + i + "个顶点不存在！");
    		for(int j=0;j<vNum;j++) {
    			if(e[i][j]!=0&&e[i][j]<Integer.MAX_VALUE)
    				return j;
    		}
    		return -1;
    	}
    
    	/**
    	 * 查找下一个邻接点
    	 * 第j个顶点是第i个顶点的邻接点，，查找第j个顶点之后的第i个顶点的下一个邻接点。
    	 * @param int i 顶点在顶点集中的位置i
    	 * @param int j 顶点在顶点集中的位置j
    	 */
    	public int nextAdj(int i, int j) {
    		if(j == vNum-1)
    			return -1;
    		for(int k=j+1;k<vNum;k++) {
    			if(e[i][k]!=0&&e[i][k]<Integer.MAX_VALUE)
    				return k;
    		}
    		return -1;
    	}
    	
    	/**
    	 * 获取邻接矩阵中的指定权值
    	 * @param i 邻接矩阵第i行
    	 * @param j 邻接矩阵第j列
    	 * @return	返回邻接矩阵第i行，第j列的权值
    	 */
    	public int getArcs(int i, int j) {
    		return e[i][j];
    	}
    }

### 参考接口 ###

> [IGraph][]

# 邻接矩阵性能分析 #

1.  由于邻接矩阵采用数组结构，故增删操作需要移动大量元素，效率低下，并且数组容量有限，当扩充容量时需要复制全部元素。
2.  由于邻接矩阵在存储没有邻接关系的顶点时也会用0或无穷表示，因此在存储一个完全图或稠密图时，存储效率较高；在存储一个稀疏图时，存储效率较低。

[20190514161855165.PNG_pic_center]: /images/20220201/a4ae9ead33fc4ba59cedbfd88f0c4857.png
[2019051416210261.PNG_pic_center]: /images/20220201/b3f0bc0473a94328b8b17df164d79177.png
[IGraph]: https://blog.csdn.net/weixin_44270248/article/details/90202819