【数据结构】图的存储结构

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

               专栏

        【安利Java基础】

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

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

前言

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

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

什么是邻接表？

在图论和计算机科学中，邻接表【Adjacency List】是用来表示有限图的无序表的集合。每个列表描述图中一个顶点的邻域集。这是计算机程序中常用的几种图形表示法之一。

1. 邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

2. 实际上就是一种由链表组成的图形数据结构，对其每一个顶点，都用链表来记录它的出边。

3. 对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表点。

邻接表：定义

对于无向图，n个顶点e条边的无向图的邻接表表示中，有n个顶点表结点和2e个边表结点。

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

1、邻接表是图的一种链式存储方法

2、邻接表由一个顺序存储的顶点表和n个链式存储的边表组成。

顶点表由顶点结点组成
边表：

无向图：由边结点组成的一个单链表，表示所有依附于顶点vi的边。

有向图：由弧结点组成的一个单链表，表示所有以顶点vi为始点的弧。
链式存储结点：
- 图结点由2部分组成：第一个邻接点、下一个邻接点
- 网结点有3部分组成：第一个邻接点、权值、下一个邻接点

无向图：对应的邻接表某行上边结点个数为该行表示结点的度。

如果无向图(网)中有e条边，则对应邻接表有2e个边结点。

无向网邻接表

有向图：

邻接表：边表表示所有以vi为始点的弧。
- 对应的邻接表某行上边结点个数为该结点的出度。
- 在有向图的邻接表中不易找到指向该顶点的弧。

逆邻接表：边表表示所有以vi为终点的弧。

对应的逆邻接表某行上边结点个数为该结点的入度。

如果有向图（网）中有e条边，则对应邻接表有e个边结点。

邻接表：相关类

顶点结点类：

//图的邻接表存储表示中的顶点结点类
public class VNode {public Object data;			//顶点信息public ArcNode firstArc;	//指向第一个依附于该顶点的弧
}

边(弧)结点类：

//图的邻接表存储表示中的边(弧)结点类
public class ArcNode {public int adjVex;			//该弧所指向的顶点位置public int value;			//边(或弧)的权值public ArcNode nextArc;		//指向下一条弧
}

邻接表类

//创建邻接表
public class ALGraph implements IGraph {private GraphKind kind;			//图的种类标志private int vexNum, arcNum;		//图的当前顶点数和边数private VNode[] vexs;			//顶点private void createUDN() {		//创建无向网}private void createDN() {		//创建有向网}// 给定顶点的值vex，返回其在图中的位置，若图中不包含该顶点的，则返回-1public int locateVex(Object vex) {}// 在图中插入边结点public void addArc(int v, int u, int value) {}// 返回v的第一个邻接点，若v没有邻接点则返回-1。其中 0 <= v <= vexNumpublic int firstAdjVex(int v) throws Exception {}// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1。其中 0 <= v,w <= vexNumpublic int nextAdjVex(int v, int w) throws Exception {}
}

邻接表：基本操作

1）创建无向网

步骤：
1. 输入顶点数和边数
2. 构建顶点向量
3. 根据图的边数，确定输入边的数目
4. 根据输入的每条边生成结点，并在相应位置插入边结点
代码

// 无向网的创建算法
private void createUDN() {//初始化变量Scanner sc = new Scanner(System.in);System.out.println("请分别输入图的顶点数、图的边数:");vexNum = sc.nextInt(); //顶点数narcNum = sc.nextInt(); //边数e//输入图中各顶点vexs = new VNode[vexNum];System.out.println("请分别输入图的各顶点:");// 构造顶点向量for (int v = 0; v < vexNum; v++)vexs[v] = new VNode(sc.next());//输入图中各边信息System.out.println("请输入各边的顶点及其权值:");for (int k = 0; k < arcNum; k++) {int v = locateVex(sc.next());   // 弧尾int u = locateVex(sc.next());  	// 弧头int value = sc.nextInt();		// 权值addArc(v, u, value);   //加入边addArc(u, v, value);   //加入边}
}

2）创建有向网

	// 创建有向网private void createDN() {Scanner sc = new Scanner(System.in);System.out.println("请分别输入图的顶点数、图的边数：");vexNum = sc.nextInt();arcNum = sc.nextInt();vexs = new VNode[vexNum];System.out.println("请分别输入图的各顶点：");for (int v = 0; v < vexNum; v++)// 构建顶点向量vexs[v] = new VNode(sc.next());System.out.println("请输入各边的顶点及其权值：");for (int k = 0; k < arcNum; k++) {int v = locateVex(sc.next());// 弧尾int u = locateVex(sc.next());// 弧头int value = sc.nextInt();addArc(v, u, value);		// 一个方向}}

3）顶点定位

// 给定顶点的值vex，返回其在图中的位置，若图中不包含该顶点的，则返回-1public int locateVex(Object vex) {for (int v = 0; v < vexNum; v++)if (vexs[v].data.equals(vex))return v;return -1;}

4）插入边

核心思想：往链式存储的边表头插入一个新结点。

// 在图中插入边结点public void addArc(int v, int u, int value) {ArcNode arc = new ArcNode(u, value);	//u为边的终点，生成边结点arc.nextArc=vexs[v].firstArc;			//v为边的起点，将边结点插入顶点v 的链表表头vexs[v].firstArc=arc;					//生成新表头}

5）第一个邻接点

// 已知图中的一个顶点v，返回v的第一个邻接点，如果v没有连接点，则返回-1，其中0 <= v < vexNumpublic int firstAdjVex(int v) throws Exception {if (v < 0 || v >= vexNum)throw new Exception("第" + v + "个顶点不存在!");VNode vex = vexs[v];if (vex.firstArc != null)return vex.firstArc.adjVex;elsereturn -1;}

6）查询下一个邻接点

public int nextAdjVex(int v, int w) throws Exception {if (v < 0 || v >= vexNum)throw new Exception("第" + v + "个顶点不存在!");VNode vex = vexs[v];ArcNode arcvw = null;// 获得w结点在链表中所在的位置for (ArcNode arc = vex.firstArc; arc != null; arc = arc.nextArc)if (arc.adjVex == w) {arcvw = arc;break;}// 返回w的下一个邻接点if (arcvw != null && arcvw.nextArc != null)return arcvw.nextArc.adjVex;elsereturn -1;}