数据结构——图简介（java代码实现邻接矩阵）

淩亂°似流年 2023-02-12 14:22 12阅读 0赞

图：图是一种数据结构，其中节点可以具有一个或者多个相邻元素，俩个节点的连接称为边，节点也称为顶点。

图的表示方式

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1…n个点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
邻接表

1.  邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
2.  邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
**图的邻接矩阵代码实现：**

import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Graph {
    	private ArrayList<String> vertexList; // 存放顶点集合
    	private int[][] edges; // 矩阵
    	private int num; // 边的数目
    
    	public Graph(int n) {
    		edges = new int[n][n];
    		vertexList = new ArrayList<String>(n);
    		num = 0;
    	}
    
    	// 插入节点
    	public void addVer(String vertex) {
    		vertexList.add(vertex);
    	}
    
    	// 添加边
    	public void addNum(int v1, int v2, int weight) {
    		// v1和v2指的是点的下标。weight表示权值
    		edges[v1][v2] = weight;
    		edges[v2][v1] = weight;
    		num++;
    	}
    
    	// 返回节点的个数
    	public int nodeNum() {
    		return vertexList.size();
    	}
    
    	// 返回边一共有多少条
    	public int edgeNum() {
    		return num;
    	}
    
    	// 通过索引返回值
    	public String getValue(int i) {
    		return vertexList.get(i);
    	}
    
    	// 返回v1和v2的权值
    	public int getWeight(int v1, int v2) {
    		return edges[v1][v2];
    	}
    
    	// 显示图对应的矩阵
    	public void show() {
    		for (int[] link : edges) {
    			System.err.println(Arrays.toString(link));
    		}
    	}
    
    	public static void main(String[] args) {
    		int n = 5; // 节点的个数
    		String vertexString[] = { "A", "B", "C", "D", "F" };
    		// 创建图对象
    		Graph gp = new Graph(5);
    		// 向图对象添加节点
    		for (String value : vertexString) {
    			gp.addVer(value);
    		}
    		// 添加边AB AC AD AE BC BD CE DE
    		gp.addNum(0, 1, 1);
    		gp.addNum(0, 2, 1);
    		gp.addNum(0, 3, 1);
    		gp.addNum(0, 4, 1);
    		gp.addNum(1, 2, 1);
    		gp.addNum(1, 3, 1);
    		gp.addNum(2, 4, 1);
    		gp.addNum(3, 4, 1);
    		// 显示图的矩阵
    		gp.show();
    	}
    }

对上图的实现到最后打印出来矩阵，可以看到与上图构建的矩阵是相同的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526142500955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200526143411310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200526151001424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70