7.3.4邻接多重表
十字链表对有向图的存储结构进行了优化
在无向表的应用中，关注的重点是顶点，邻接表是好的选择
如果关注的是边的操作，就需要更简单的方式
对边表结点结构重新定义
其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。
ilink 指向依附顶点ivex的下一条边
jlink 指向依附顶点jvex的下一条边
下图告诉我们它有4个顶点和5条边，显然，我们就应该先将4个顶点和5条边的边表结点画出来。由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的,不过为了绘图方便,都将ivex值设置得与一旁的顶点下标相同。
好，我们来分析这个图
firstedge是指针域，指向边表的第一个结点，ivex和jvex是依附于边的顶点坐标的下标（注意是顶点坐标的下标），比如图中的0和1，那么它们就代表顶点V0和顶点V1中间的那条边
那么ilink和jlink是什么呢？
ilink指的是ivex依附顶点的下一条边
jlink指的是jvex依附顶点下一条边
实例如图所示：
看上面的连线，firstedge指向一条边，顶点下标和ivex的值相同，继续，顶点V0有三个边跟它有关v0v1,v0v2,v0v3
所以连线5,6满足指向下一条依附于顶点的v0的边的目标，ilink指向的结点的jvex一定要和它本身的ivex值相同。连线7就是指v1，v0这条边，它是相当于顶点v1指向v1，v2边后的下一条。v2有三条依附，所以在连线3后就有了8跟9.连线10的就是顶点v3在连线4后下一条边。
图上共5条边所以有10条连线，符合预期
邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。 这样对边的操作就方便多了，若要删除左图的(V0,V2) 这条边，只需要将右图的⑥⑨的链接指向改为^即
可。各种基本操作的实现也和邻接表是相似的
7.3.5边集数组
边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end) 和权(weight)组成
实例如下：
这个结构很好理解，看图就能看懂
7.4图的遍历
图的遍历是和树的遍历类似，我们希望从图中某一顶点出 发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍(Traversing Graph)。
7.4.1深度优先遍历
深度优先遍历（Deep_First_Search），称为简称DFS。
主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
实例如下，序号代表的是遍历的顺序
从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9
此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历
同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7
从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了
这好像就是树的前序前序遍历啊实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。
7.4.2广度优先遍历
广度优先遍历(Breadth_ First Search)， 又称为广度优先搜索，简称BFS
指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点
它这个遍历类似图中的层序遍历
DFS 一般是解决连通性问题，而 BFS 一般是解决最短路径问题
C语言实现代码就先不写了，之后会更新Java相关的代码实现，敬请期待
7.5最小生成树
引用文章：图解：什么是最小生成树？ - 知乎 (zhihu.com)
7.5.1生成树的定义
一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。
可以看到一个包含3个顶点的完全图可以产生3颗生成树。对于包含n个顶点的无向完全图最多包含 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UhDPoCzY-1637250894565)(https://www.zhihu.com/equation?tex=n%5E%7Bn-2%7D)] 颗生成树。比如上图中包含3个顶点的无向完全图，生成树的个数为： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sOPQgGlo-1637250894567)(https://www.zhihu.com/equation?tex=3%5E%7B3-2%7D%3D3)].
7.5.2生成树的属性
一个连通图可以有多个生成树；
一个连通图的所有生成树都包含相同的顶点个数和边数；
生成树当中不存在环；
移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性；
在生成树中添加一条边会构成环。
对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；
对于包含n个顶点的无向完全图最多包含 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WKgCBBcZ-1637250894568)(https://www.zhihu.com/equation?tex=n%5E%7Bn-2%7D)] 颗生成树。
生成树我们知道了，下面我们来看看最小生成树
所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树
通过定义我们知道，最小生成树其实是和带权图联系到一起的，如果是非带权图，那他们只存在生成树，我们来看看例子
上图中，原来的带权图可以生成左侧的两个最小生成树，这两颗最小生成树的权值之和最小，且包含原图中的所有顶点。
那么如何从图中得到最小生成树呢？
最小生成树算法有很多，其中最经典的就是克鲁斯卡尔（Kruskal）算法和 普里姆（Prim）算法，也是我们考试、面试当中经常遇到的两个算法。
7.5.3Kruskal算法
贪心算法一般按如下步骤进行：
①建立数学模型来描述问题
②把求解的问题分成若干个子问题
③对每个子问题求解，得到子问题的局部最优解
④把子问题的解局部最优解合成原来解问题的一个解
克鲁斯卡尔算法（Kruskal）是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。
第一步：将图中所有的边按照权值进行非降序排列；
第二步：从图中所有的边中选择可以构成最小生成树的边。
选择权值最小的边 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gEIwcwlA-1637250894572)(https://www.zhihu.com/equation?tex=V_4-V_7)]：没有环形成，则添加：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-63KGTZQp-1637250894573)(https://typora-1259403628.cos.ap-nanjing.myqcloud.com/image-20211118093755931.png)]
此时已经包含了图中顶点个数9减1条边，算法停止。
下面我们来用代码实现
int Find(int *parent, int f) { while( parent[f] > 0 ) { f = parent[f]; } return f; } // Kruskal算法生成最小生成树 void MiniSpanTree_Kruskal(MGraph G) { int i, n, m; Edge edges[MAGEDGE]; // 定义边集数组 int parent[MAXVEX]; // 定义parent数组用来判断边与边是否形成环路 int eCount = 0; for( i=0; i < G.numVertexes; i++ ) { parent[i] = 0; } for( i=0; i < G.numEdges; i++ ) { n = Find(parent, edges[i].begin); // 4 2 0 1 5 3 8 6 6 6 7 m = Find(parent, edges[i].end); // 7 8 1 5 8 7 6 6 6 7 7 if( n != m ) // 如果n==m，则形成环路，不满足！ { parent[n] = m; // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中 printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight); ++eCount; if( eCount == (G.numVertexes-1)){ break; } } } }
时间复杂度分析
O(ElogE)或者O(ElogV)，其中E代表图中的边的数目，V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环，判断添加一条边是否构成环最坏情况下需要O(logV)，关于这个复杂度等到景禹给你们谈并查集的时候再分析；因此，总的时间复杂度为O(ElogE + ElogV)，其中E的值最大为V(V-1)/2，因此O(logV) 等于 O(logE)。因此，总的时间复杂度为O(ElogE) 或者O(ElogV)。
