深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构】图的存储结构—邻接矩阵

2023-05-18

int 顶点 邻接矩阵
目录图的类型&存储结构的介绍邻接矩阵—无向图、有向图的邻接矩阵定义—网的邻接矩阵的定义邻接矩阵：类的描述邻接矩阵：基本操作1）创建图2）创建无向网 3）创建有向网4）顶点定位5）查询第一个邻接点6）查找下一个邻接点创作不易，不妨点赞💚评论❤️收藏💙一下💟作者简介：大家好呀！我

目录

图的类型&存储结构的介绍

邻接矩阵

— 无向图、有向图的邻接矩阵定义

— 网的邻接矩阵的定义

邻接矩阵：类的描述

邻接矩阵：基本操作

1）创建图

2）创建无向网

 3）创建有向网

4）顶点定位

5）查询第一个邻接点

6）查找下一个邻接点

创作不易，不妨点赞💚评论❤️收藏💙一下

💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️    
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！

               专栏

        【安利Java零基础】

        【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀！~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努力努力呀！💪
————————————————
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

 前言

由于图的结构比较复杂，任意两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。这一点同其他数据结构（如线性表、树）不同。

因为图中的顶点具有相对概念，没有固定的位置，且顶点和顶点之间通过添加和删除边，维持着不同的关系。考虑图的定义，图是由顶点和边组成的。所以，分别考虑如何存储顶点和边。图常用的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。那么对于一般情况下该怎么存储图的数据结构呢？这里我们主要分两个章节详细介绍两种常用的图存储结构 — 邻接矩阵、邻接表

图的类型&存储结构的介绍

  • 图的类型主要有4种：无向图、有向图、无向网和有向网。
  • 可以用枚举表示为：
  1. public enum GraphKind{
  2.     UDG,//无向图(UnDirected Graph)
  3.     DG,//有向图(Directed Graph)
  4.     UDN,//无向网(UnDirected Network)
  5.     DN,//有向网(Directed Network)
  6. }

图有多种存储结构，每种存储结构都能表示上面的4种的类型。图的存储结构除了存储图中各个顶点的信息外，还需要存储与顶点相关的边的信息。

常见图的存储结构：

  • 邻接矩阵

  • 邻接表

  • 邻接多重表

  • 十字链表

邻接矩阵

— 无向图、有向图的邻接矩阵定义

逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

图的邻接矩阵：用来表示顶点之间相邻关系的矩阵。

  • 图G=(V, E)具有n(n >= 1)个顶点,顶点的顺序依次为{v0,v1,...,vn-1}

  • 设图A=（V，E）有n个顶点，则关于顶点数据的一维数组为：

  • 则图G的邻接矩阵A是一个n阶方阵，定义如下：

特点1：无向图 的邻接矩阵一定是对称 的，而 有向图 的邻接矩阵不一定对称。

因此，用 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零，副对角线不一定为0，有向图则不一定如此。

邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只需存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素压缩存储，故只需1+2+...+(n-1)=n(n-1)/2个单元。

特点2：无向图邻接矩阵的 第i行（或第i列）非零元素的个数 正好是第i个顶点的度。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)”

无向图，没有方向，所有两个顶点连线必定是相互的。因此行或列的非零元素个数必定一样。则找顶点的度时，看行或列都可以。

特点3：

  • 有向图顶点的度【行表示出度，列表示入度】
    1. 顶点v的入边数目是该顶点的入度，记为ID(v);
    2. 顶点v的出边数目是该顶点的出度，记为OD(v);
    3. 顶点v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)

有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。

特点4：用邻接矩阵表示图，很容易看出确定图中任意两个顶点是否有边相连。

无向图的邻接矩阵是对称的，一般可以采用压缩存储。

— 网的邻接矩阵的定义

网(network)：带权的图

 图与网的区别：

                1. 权值：网里面对应的边是有权值的，用以表示边的某种属性比如距离等。而图的边是没有权值的

                2. 表示零元素的形式不同：不管是无向图还是有向图表示零元素时，都用0代替表示；而在网中，表示零元素则是用无穷大∞ 表示。

无向网的邻接矩阵：

 有向网的邻接矩阵 ：

邻接矩阵：类的描述

  1. public class MGraph implements IGraph {
  2. public final static int INFINITY = Integer.MAX_VALUE;
  3. private GraphKind kind;//图的种类标志
  4. private int vexNum, arcNum;//图的当前顶点数和边数
  5. private Object[] vexs;//顶点集
  6. private int[][] arcs;//邻接矩阵（边集）
  7.     
  8.     public void createGraph(){}//创建图
  9.     private void createUDG() {}//创建无向图
  10.     private void createDG() {}//创建有向图
  11.     private void createUDN() {}//创建无向网
  12.     private void createDN() {}//创建有向网
  13.     
  14. public int getVexNum() {//返回定点数
  15. return vexNum;
  16. }
  17. public int getArcNum() {//返回边数
  18. return arcNum;
  19. }
  20.     
  21.     // 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1
  22.     public int locateVex(Object vex) {}
  23.     // 返回v表示结点的值，0 <= v <= vexNum
  24.     public Object getVex(int v) throws Exception {}
  25.     // 返回v的第一个邻接点，若v没有邻接点则返回-1。其中 0 <= v <= vexNum
  26.     public int firstAdjVex(int v) throws Exception {}
  27.     // 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1。其中 0 <= v,w <= vexNum
  28.     public int nextAdjVex(int v, int w) throws Exception {}
  29. }

邻接矩阵：基本操作

1）创建图

  1. // 创建图
  2. public void createGraph() {
  3.         // 获得用户输入的图的类型
  4. Scanner sc = new Scanner(System.in);
  5. System.out.println("请输入图的类型：");
  6. GraphKind kind = GraphKind.valueOf(sc.next()); //通过字符串获得对应枚举类型
  7. switch (kind) {   //根据不同的枚举值，选择不同的图或网的创建
  8. case UDG:
  9. createUDG();// 构建无向图
  10. return;
  11. case DG:
  12. createDG();// 构建有向图
  13. return;
  14. case UDN:
  15. createUDN();// 构建无向网
  16. return;
  17. case DN:
  18. createDN();// 构建有向网
  19. return;
  20. }
  21. }

2）创建无向网

  • 输入图的顶点、边及权值构造无向图，步骤：

    1. 输入顶点数或边数

    2. 根据图的顶点数构建邻接矩阵

    3. 根据图的边数，确定输入边的数目

    4. 根据输入每条边的顶点再邻接矩阵相应位置保存每条边的权值。

  • 代码

  1. private void createUDN() {
  2.     //初始化变量
  3.     Scanner sc = new Scanner(System.in);
  4.     System.out.println("请分别输入图的顶点数、图的边数:");
  5.     vexNum = sc.nextInt();//顶点数n
  6.     arcNum = sc.nextInt();//边数e
  7.  
  8.     //输入图中各顶点
  9.     vexs = new Object[vexNum];//顶点集对应的数组
  10.     System.out.println("请分别输入图的各个顶点:");
  11.     for (int v = 0; v < vexNum; v++)//通过循环依次输入各个顶点
  12.         vexs[v] = sc.next();
  13.     //定义邻接矩阵
  14.     arcs = new int[vexNum][vexNum];
  15.     // 初始化邻接矩阵
  16.     for (int v = 0; v < vexNum; v++)
  17.         for (int u = 0; u < vexNum; u++)
  18.             arcs[v][u] = INFINITY;//初始为无穷大
  19.  
  20.     //输入边信息
  21.     System.out.println("请输入各个边的两个顶点及其权值:");
  22.     for (int k = 0; k < arcNum; k++) {
  23.         int v = locateVex(sc.next()); //顶点
  24.         int u = locateVex(sc.next()); //顶点
  25.         arcs[v][u] = arcs[u][v] = sc.nextInt();  //权值, 对称
  26.     }
  27. }

 3）创建有向网

  1. // 构建有向网
  2. private void createDN() {
  3. Scanner sc = new Scanner(System.in);
  4. System.out.println("请分别输入图的顶点数、图的边数：");
  5. vexNum = sc.nextInt();
  6. arcNum = sc.nextInt();
  7. vexs = new Object[vexNum];
  8. System.out.println("请分别输入图的各个顶点：");
  9. for (int v = 0; v < vexNum; v++)
  10. //构造顶点向量
  11. vexs[v] = sc.next();
  12.  
  13. arcs = new int[vexNum][vexNum];
  14. for (int v = 0; v < vexNum; v++)
  15. // 初始化邻接矩阵
  16. for (int u = 0; u < vexNum; u++)
  17. arcs[v][u] = INFINITY;
  18.  
  19. System.out.println("请输入各个边的两个顶点及其权值：");
  20. for (int k = 0; k < arcNum; k++) {
  21. int v = locateVex(sc.next());
  22. int u = locateVex(sc.next());
  23. arcs[v][u] = sc.nextInt();//仅设置顶点v-->顶点u，不是对称的，只需要设置一个
  24. }
  25. }

4）顶点定位

  • 根据顶点信息vex，取得其在顶点数组中的位置，若图中无此顶点，则返回-1。

  • 代码：

  1. // 根据顶点信息vex，取得其在顶点数组中的位置，若图中无此顶点，则返回-1。
  2. public int locateVex(Object vex) {
  3. // 遍历顶点数组
  4. for (int v = 0; v < vexNum; v++)
  5. if (vexs[v].equals(vex))
  6. return v;
  7. return -1;
  8. }

  • 时间复杂度：O(n)

5）查询第一个邻接点

步骤：

  • 判断v的合法性

  • 顶点v的索引号，对应邻接矩阵的第v行，遍历第v行，查找是否有非0、非无穷大值的元素

  • 代码：

  1. // 已知图中的一个顶点v，返回v的第一个邻接点，如果v没有连接点，则返回-1，其中0 <= v < vexNum
  2. public int firstAdjVex(int v) throws Exception {
  3. if (v < 0 || v >= vexNum)
  4. throw new Exception("第" + v + "个顶点不存在!");
  5.  
  6. for (int j = 0; j < vexNum; j++)
  7. if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
  8. return j;
  9.  
  10. return -1;
  11. }

  • 时间复杂度：O(n)

6）查找下一个邻接点

步骤：

  • 判断v的合法性

  • 从邻接矩阵第v行第w+1列开始遍历查找是否有非0、非无穷大值的元素

  • 代码：

  1. public int nextAdjVex(int v, int w) throws Exception {
  2. if (v < 0 || v >= vexNum)
  3. throw new Exception("第" + v + "个顶点不存在!");
  4.  
  5. for (int j = w + 1; j < vexNum; j++)
  6. if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
  7. return j;
  8.  
  9. return -1;
  10. }
  • 时间复杂度：O(n)

写到最后

四季轮换，已经数不清凋零了多少， 愿我们往后能向心而行，一路招摇胜！

🐋 你的支持认可是我创作的动力

💟 创作不易，不妨点赞💚评论❤️收藏💙一下

😘 感谢大佬们的支持，欢迎各位前来不吝赐教

想要了解更多吗？没时间解释了，快来点一点！

路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主路遥叶子擅长数据结构,安利Java零基础,spring,等方面的知识,路遥叶子关注spring,java,maven,elementui,vue.js,mysql,数据结构领域.https://blog.csdn.net/zsy3757486?spm=1010.2135.3001.5343

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览46509 人正在系统学习中
欢迎一起共同探讨学习Java知识
微信名片
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪