下载文档原格式
数据结构中的树与图算法教程第一章树的基本概念与遍历算法树是一种非线性数据结构，它由若干个节点组成，这些节点以层级的方式连接，形成分支的结构。
树中的一个节点被称为根节点，它没有父节点；其他节点可以有一个或多个父节点，这些节点被称为子节点。
树具有分支，但没有循环。
1.1 具体树的概念在树的结构中，每个节点可以有零个或者多个子节点，但是只能有一个父节点。
树具有层级关系，通过连接节点的边表示。
1.2 树的分类常见的树包括二叉树、二叉搜索树、红黑树等。
其中，二叉树是一种特殊的树结构，它的每个节点最多可以有两个子节点。
1.3 树的遍历算法树的遍历算法主要有前序遍历、中序遍历和后序遍历。
前序遍历是以根节点、左子树、右子树的顺序进行遍历；中序遍历是以左子树、根节点、右子树的顺序进行遍历；后序遍历是以左子树、右子树、根节点的顺序进行遍历。
第二章树的存储结构与常见应用2.1 树的存储结构树的存储结构有两种常见的实现方式，分别是链表实现和数组实现。
链表实现利用指针进行节点的连接，数组实现则使用数组的索引来表示节点之间的关系。
2.2 平衡二叉树平衡二叉树是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1。
平衡二叉树的插入和删除操作都可以通过旋转操作进行平衡。
2.3 哈夫曼树哈夫曼树是一种特殊的二叉树，用于编码和解码数据。
哈夫曼树中出现频率高的字符距离根节点较近，而出现频率低的字符距离根节点较远，以实现编码的高效率。
第三章图的基本概念与遍历算法3.1 图的基本概念图是由节点和边组成的非线性数据结构。
节点表示实体，边表示节点之间的关系。
图可以分为有向图和无向图两种类型，有向图的边是有方向的，无向图的边没有方向。
3.2 图的存储结构图的存储结构有邻接矩阵和邻接表两种常见的方式。
邻接矩阵是一个二维数组，用于表示节点之间的连接关系；邻接表是由链表或者数组实现的，用于表示每个节点相邻节点的信息。
3.3 图的遍历算法图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。
在离散数学中，图是一个由点和边组成的抽象数学模型。
其中，树是一种特殊的图，它是一个无环连通图。
在图论中，树扮演了重要的角色，它具有许多有趣的性质和应用。
而生成树则是树的一个特殊子集，它由给定图中的所有顶点和部分边构成。
本文将介绍图的树的基本概念，并探讨生成树的计数方法。
首先，让我们来看看图的树。
树是一种无环连通图，其中任意两个顶点之间存在唯一一条路径。
它具有以下性质：1.n个顶点的树有n-1条边。
这可以通过归纳法证明：当n=1时，结论成立；假设n=k时成立，那么n=k+1时，只需要添加一个顶点和一条边，即可构成n=k+1个顶点的树。
因此，结论成立。
2.连接树上任意两个顶点的边都是桥。
即如果一条边被删除，那么树就会变成两个或更多个不相连的子树。
3.树是一个高度平衡的结构。
对于一个n个顶点的树，任意两个叶子结点之间的路径长度至多相差1。
4.树的任意两个顶点之间有唯一一条路径，路径长度为顶点之间的边数。
接下来，让我们来讨论生成树的计数方法。
生成树是树的一个特殊子集，它是由给定图中的所有顶点和部分边构成。
生成树的计数在图论中具有重要的意义和应用。
对于一个具有n个顶点的连通图来说，其生成树的个数可以通过Cayley公式计算得到。
Cayley公式是由亚瑟·凯利于1889年提出的，它给出了完全图的生成树数目。
据此，我们可以得到生成树的计数公式为：T = n^(n-2)，其中T表示生成树的个数。
此外，还有一种常见的计数方法是基于度数矩阵和邻接矩阵的矩阵树定理。
矩阵树定理由高斯于1847年提出，它提供了一种计算图的生成树个数的方法。
根据矩阵树定理，一个无向图G的生成树数目等于该图度数矩阵的任意一个(n-1)阶主子式的行列式的值。
其中，度数矩阵是一个对角矩阵，它的对角线上的元素为各个顶点的度数。
邻接矩阵则是一个关于顶点间连接关系的矩阵，其中1表示相邻顶点之间存在边，0表示不存在边。
除了数学方法，还存在一种基于图的遍历的计数方法，称为Kirchhoff矩阵树定理。
图论中的生成树计数算法生成树是图论中重要的概念之一，它是指由给定图的节点组成的树形结构，其中包含了原图中的所有节点，但是边的数量最少。
生成树的计数问题是指在一个给定的图中，有多少种不同的生成树。
生成树计数算法是解决这个问题的关键步骤，本文将介绍一些常见的生成树计数算法及其应用。
1. Kirchhoff矩阵树定理Kirchhoff矩阵树定理是图论中经典的生成树计数方法之一。
该定理是由Kirchhoff在19世纪提出的，它建立了图的Laplacian矩阵与其生成树个数的关系。
Laplacian矩阵是一个$n\times n$的矩阵，其中$n$是图中的节点数。
对于一个连通图而言，Laplacian矩阵的任意一个$n-1$阶主子式，其绝对值等于该图中生成树的个数。
应用示例：假设我们有一个无向连通图，其中每个节点之间的边权均为1。
我们可以通过计算图的Laplacian矩阵的任意一个$n-1$阶主子式的绝对值来得到该图中的生成树个数。
2. Prufer编码Prufer编码是一种编码方法，可用于求解生成树计数问题。
它是基于树的叶子节点的度数的编码方式。
Prufer编码将一个树转换为一个长度为$n-2$的序列，其中$n$是树中的节点数。
通过给定的Prufer序列，可以构造出对应的生成树。
应用示例：假设我们有一个具有$n$个节点的有标号的无根树。
我们可以通过构造一个长度为$n-2$的Prufer序列，然后根据Prufer编码的规则构造出对应的生成树。
3. 生成函数方法生成函数方法是一种利用形式幂级数求解生成树计数问题的方法。
通过将图的生成树计数问题转化为生成函数的乘法运算，可以得到生成函数的一个闭形式表达式，从而求解生成树的个数。
应用示例：假设我们有一个具有$n$个节点的有根树，其中根节点的度数为$d$。
我们可以通过生成函数方法求解出该有根树中的生成树个数。
4. Matrix-Tree定理Matrix-Tree定理是对Kirchhoff矩阵树定理的一种扩展，适用于带权图中生成树计数的问题。
在离散数学中，生成树（Spanning Tree）是一个图（Graph）的子图，它包含图中的所有顶点，并且是一个树（Tree）。
生成树的一个重要性质是它不包含任何环（Cycle）。
求一个给定图的生成树个数是一个经典问题，通常使用矩阵树定理（Matrix Tree Theorem）来解决。
矩阵树定理给出了一个图的生成树个数的计算公式，它基于图的拉普拉斯矩阵（Laplacian Matrix）的行列式。
拉普拉斯矩阵是一个方阵，其大小为图的顶点数，矩阵的元素定义如下：•如果i和j是不同的顶点，则矩阵的第i行第j列的元素是顶点i和j之间的边的权重（如果存在边的话），否则是0。
•对于每个顶点i，矩阵的第i行第i列的元素是顶点i的度（即与顶点i相邻的边的数量）的负值。
矩阵树定理指出，图的生成树个数等于其拉普拉斯矩阵的任何一个n-1阶主子式的行列式值的绝对值。
n是图的顶点数，n-1阶主子式意味着去掉矩阵中的一行和一列后得到的矩阵。
下面是一个简单的例子，说明如何使用矩阵树定理计算生成树的个数：假设有一个包含4个顶点的简单图，其边和权重如下：A -- 2 -- B| |1 3 1| |C -- 4 -- D1 -3 1 00 1 -3 40 0 1 -4主子式的行列式值。
去掉第一行和第一列后，我们得到：1 01 -3 40 1 -4x3矩阵的行列式，我们得到：1 * 1) - (0 * 0) = 12 - 1 = 11过程可能涉及复杂的行列式计算，特别是对于大型图来说。
在实际应用中，通常会使用专门的数学软件或库（如Python中的NumPy或SciPy）来进行这些计算。
此外，还有一些算法（如Kruskal算法和Prim算法）可以用来构造生成树，但它们并不直接计算生成树的总数。
这些算法通常用于找到图的一个生成树，而不是计算所有可能的生成树的数量。
窗体顶端1. 邻接表是图的一种____。
正确答案点评A 顺序存储结构B 链式存储结构C 索引存储结构D 散列存储结构正确答案：B答案讲解：无【试题出处】第6章第3节1窗体底端窗体顶端2. 一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。
正确答案点评A 38,40,46,56,79,84B 40,38,46,79,56,84C 40,38,46,56,79,84D 40,38,46,84,56,79正确答案：C窗体底端窗体顶端3. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。
正确答案点评A 2h-1B 2(h-1)C 2*h-1D 2*h正确答案：A窗体底端窗体顶端4. 一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是_______。
正确答案点评A acbdB dcbaC acdbD dbac正确答案：D窗体底端窗体顶端5. 计算机算法是指______。
正确答案点评A 计算方法B 排序方法C 调度方法D 解决问题的有限运算序列正确答案：D窗体底端窗体顶端6. 关于二叉树的三种遍历，下列说法正确的是____。
正确答案点评A 任意两种遍历序列都不可以唯一决定该二叉树B 任意两种遍历序列都可以唯一决定该二叉树C 先序遍历序列和后序遍历序列可以唯一决定该二叉树D 先序遍历序列和中序遍历序列可以唯一决定该二叉树正确答案：D窗体底端窗体顶端7. 顺序表的特点是______。
正确答案点评A 逻辑上相邻的结点其物理位置不相邻B 逻辑上相邻的结点其物理位置亦相邻C 顺序表不是随机存储结构D 在顺序表中插入和删除操作比在链表上方便正确答案：B窗体底端窗体顶端8. 设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。
Best定理是指以x点为起点的欧拉回路个数sum =
T[x]*∑(out[i]-1)!，其中T[x]表示以x为根的外向生成树个数，out[i]表示i点的出度。
这个定理用于计算有向图中的欧拉回路数量。
具体来说，对于一个有向图，如果存在从起点到终点的路径，使得每条边的方向都是一致的，那么这条路径被称为欧拉路径。
如果这个路径的起点和终点是同一点，那么这条路径被称为欧拉回路。
Best定理中的T[x]表示以x为根的外向生成树个数，生成树是指一个连通无环的树状图，外向生成树指的是从根节点向外延伸的生成树。
∑(out[i]-1)!表示所有出度大于1的节点的欧拉回路个数的乘积。
对于每个出度大于1的节点i，存在(out[i]-1)!种不同的欧拉回路，因为可以从(out[i]-1)个非根节点中选择一个作为下一个节点，然后再从剩下的(out[i]-2)个非根节点中选择一个作为下下个节点，以此类推，直到回到根节点。
因此，Best定理通过计算以x为根的外向生成树个数和所有出度大于1的节点的欧拉回路个数，可以得到整个有向图中的欧拉回路个数。
图论第二章和第四章书后练习题2.2 给出满足下列条件的图或说明这样的图为什么不存在 (a)没有奇点的图。
(b)所有顶点的度为三的图。
(c)阶至少为5的图G ,且对于G 中任意两个邻接的顶点,,v u 均有u deg v deg ≠。
(d)阶至少为5的非完全图H ,且对于H 中任意两个不邻接的顶点,,v u 均有u deg v deg ≠。
解：（a ）（b ）(c)(d)2.4 给出一个阶为6且边数为10的图G ,满足.4)(,3)(=∆=G G δ 解：所求图如下所示：2.6 在一个阶为)1(3≥n n 的图中，若度为n n ,1-和1+n 的顶点数个数均为n ，则n 必为偶数。
证：∵n-1+n+n+1=3n;∴图中仅有度为n+1,n,n-1三种度的顶点∑deg(v)=(n-1)n+n*n+(n+1)n=3n2由图论第一定理知，3n 2为偶数 则n 为偶数。
2.8 设G 为n 阶图，若对G 中任意三个互不邻接的顶点v u ,和w ，都有u deg ,1deg deg -≥++n w v 则G 一定是连通的吗？解：不一定，如下图：2.10 我们已经知道，若n 阶图G 的任意两个不邻接的顶点u 和v 都满足,2deg deg -≥+n v u 则G 可能不连通。
(a) 证明：存在n 阶的连通图G ，它满足：对G 中两个任意不邻接的顶点u 和v ，都有,2deg deg -≥+n v u 且G 有两个不邻接的顶点x 和y ，使得y x deg deg +=2n -。
(b) 证明：若n 阶图G 的任意两个不邻接的顶点u 和v 都满足,2deg deg -≥+n v u 则G 至多有两个连通分支。
(c) (b)中的界是紧的吗？（a ）证：假设deg deg 1u v n +≤-，则由定理4可知G 不是联通的，这与已知矛盾。
∴原结论正确。
（b ）证：假设存在G1，G2,G3 三个连通分支，其阶数分别为n1,n2,n3,且n1+n2+n3≤n;取u ∈G1 v ∈G212123()()()()1123G G G G d u d v d U d v n n n n n +=+≤-+-≤--≤- 矛盾！∴至多有两个连通分支 (c)是的2.12证明：若n 阶图G 满足1)()(-≥+∆n G G δ，则G 是连通的，且4)(≤G diam 。
杨忠道定理杨忠道定理是由中国数学家杨忠道提出的一个重要的数学定理，它在数学领域具有广泛的应用价值。
本文将围绕杨忠道定理展开，介绍其定义、性质和应用。
杨忠道定理，又称为杨氏矩阵树定理，是图论中的一个重要定理。
它是由杨忠道于1963年提出的，用于计算图的生成树的个数。
该定理的核心思想是利用矩阵的行列式性质，将图的邻接矩阵转化为关联矩阵，从而求解生成树的个数。
我们来介绍一下图的邻接矩阵和关联矩阵。
在图论中，邻接矩阵是用矩阵来表示图的结构的一种方式。
对于一个n个顶点的图，邻接矩阵是一个n×n的矩阵，其中第i行第j列的元素表示顶点i和顶点j之间是否存在一条边。
如果存在边，则为1；否则为0。
关联矩阵则是将图的边和顶点之间的关系都表示在矩阵中，是一个n×m的矩阵，其中n为顶点数，m为边数。
杨忠道定理的关键是通过计算邻接矩阵的代数余子式来求解生成树的个数。
具体来说，对于一个n个顶点的图，将其邻接矩阵的第i 行第i列元素替换为该顶点的度数，其他元素不变。
然后计算该矩阵的任意一个n-1阶代数余子式，即去掉其中任意一行和一列后，剩下的元素所构成的(n-1)×(n-1)矩阵的行列式。
最后，将所有的代数余子式相加，即可得到生成树的个数。
杨忠道定理具有以下几个重要性质。
首先，生成树的个数与图的度数有关，即与邻接矩阵的对角元素有关。
其次，生成树的个数与图的连通性有关，只有连通图才存在生成树。
此外，杨忠道定理还可以用于计算图的割集（图中去掉某个边后，图分为两个不连通的部分）的个数和割点（图中去掉某个顶点后，图分为两个不连通的部分）的个数。
杨忠道定理在实际应用中有着广泛的用途。
首先，它可以用于计算网络中的最小生成树，从而优化网络的通信效率。
其次，它可以用于计算电路中的回路个数，从而帮助设计师评估电路的稳定性。
此外，杨忠道定理还可以应用于社交网络中的信息传播研究，帮助分析信息在网络中的传播路径和速度。
详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。
1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。
数据结构（三⼗三）最⼩⽣成树（Prim、Kruskal） ⼀、最⼩⽣成树的定义 ⼀个连通图的⽣成树是⼀个极⼩的连通⼦图，它含有图中全部的顶点，但只有⾜以构成⼀棵树的n-1条边。
在⼀个⽹的所有⽣成树中，权值总和最⼩的⽣成树称为最⼩代价⽣成树（Minimum Cost Spanning Tree），简称为最⼩⽣成树。
构造最⼩⽣成树的准则有以下3条：只能使⽤该图中的边构造最⼩⽣成树当且仅当使⽤n-1条边来连接图中的n个顶点不能使⽤产⽣回路的边 对⽐两个算法，Kruskal算法主要是针对边来展开，边数少时效率会⾮常⾼，所以对于稀疏图有很⼤的优势；⽽Prim算法对于稠密图，即边数⾮常多的情况会更好⼀些。
⼆、普⾥姆（Prim）算法 1.Prim算法描述 假设N={V,{E}}是连通⽹，TE是N上最⼩⽣成树中边的集合。
算法从U={u0，u0属于V}，TE={}开始。
重复执⾏下⾯的操作：在所有u属于U，v 属于V-U的边(u,v)中找⼀条代价最⼩的边(u0,v0)并加⼊集合TE，同时v0加⼊U，直到U=V为⽌。
此时TE中必有n-1条边，则T=(V,{TE})为N的最⼩⽣成树。
2.Prim算法的C语⾔代码实现/* Prim算法⽣成最⼩⽣成树 */void MiniSpanTree_Prim(MGraph G){int min, i, j, k;int adjvex[MAXVEX]; /* 保存相关顶点下标 */int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */lowcost[0] = 0;/* 初始化第⼀个权值为0，即v0加⼊⽣成树 *//* lowcost的值为0，在这⾥就是此下标的顶点已经加⼊⽣成树 */adjvex[0] = 0; /* 初始化第⼀个顶点下标为0 */for(i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i]; /* 将v0顶点与之有边的权值存⼊数组 */adjvex[i] = 0; /* 初始化都为v0的下标 */}for(i = 1; i < G.numVertexes; i++){min = INFINITY; /* 初始化最⼩权值为∞， *//* 通常设置为不可能的⼤数字如32767、65535等 */j = 1;k = 0;while(j < G.numVertexes) /* 循环全部顶点 */{if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值⼩于min */{min = lowcost[j]; /* 则让当前权值成为最⼩值 */k = j; /* 将当前最⼩值的下标存⼊k */}j++;}printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最⼩的边 */lowcost[k] = 0;/* 将当前顶点的权值设置为0,表⽰此顶点已经完成任务 */for(j = 1; j < G.numVertexes; j++) /* 循环所有顶点 */{if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]){/* 如果下标为k顶点各边权值⼩于此前这些顶点未被加⼊⽣成树权值 */lowcost[j] = G.arc[k][j];/* 将较⼩的权值存⼊lowcost相应位置 */adjvex[j] = k; /* 将下标为k的顶点存⼊adjvex */}}}}Prim算法 3.Prim算法的Java语⾔代码实现package bigjun.iplab.adjacencyMatrix;/*** 最⼩⽣成树之Prim算法*/public class MiniSpanTree_Prim {int lowCost; // 顶点对应的权值public CloseEdge(Object adjVex, int lowCost) {this.adjVex = adjVex;this.lowCost = lowCost;}}private static int getMinMum(CloseEdge[] closeEdges) {int min = Integer.MAX_VALUE; // 初始化最⼩权值为正⽆穷int v = -1; // 顶点数组下标for (int i = 0; i < closeEdges.length; i++) { // 遍历权值数组，找到最⼩的权值以及对应的顶点数组的下标if (closeEdges[i].lowCost != 0 && closeEdges[i].lowCost < min) {min = closeEdges[i].lowCost;v = i;}}return v;}// Prim算法构造图G的以u为起始点的最⼩⽣成树public static void Prim(AdjacencyMatrixGraphINF G, Object u) throws Exception{// 初始化⼀个⼆维最⼩⽣成树数组minSpanTree，由于最⼩⽣成树的边是n-1，所以数组第⼀个参数是G.getVexNum() - 1，第⼆个参数表⽰边的起点和终点符号，所以是2 Object[][] minSpanTree = new Object[G.getVexNum() - 1][2];int count = 0; // 最⼩⽣成树得到的边的序号// 初始化保存相关顶点和相关顶点间边的权值的数组对象CloseEdge[] closeEdges = new CloseEdge[G.getVexNum()];int k = G.locateVex(u);for (int j = 0; j < G.getVexNum(); j++) {if (j!=k) {closeEdges[j] = new CloseEdge(u, G.getArcs()[k][j]);// 将顶点u到其他各个顶点权值写⼊数组中}}closeEdges[k] = new CloseEdge(u, 0); // 加⼊u到⾃⾝的权值0for (int i = 1; i < G.getVexNum(); i++) { // 注意，这⾥从1开始，k = getMinMum(closeEdges); // 获取u到数组下标为k的顶点的权值最短minSpanTree[count][0] = closeEdges[k].adjVex; // 最⼩⽣成树第⼀个值为uminSpanTree[count][1] = G.getVexs()[k]; // 最⼩⽣成树第⼆个值为k对应的顶点count++;closeEdges[k].lowCost = 0; // 下标为k的顶点不参与最⼩权值的查找了for (int j = 0; j < G.getVexNum(); j++) {if (G.getArcs()[k][j] < closeEdges[j].lowCost) {closeEdges[j] = new CloseEdge(G.getVex(k), G.getArcs()[k][j]);}}}System.out.print("通过Prim算法得到的最⼩⽣成树序列为: {");for (Object[] Tree : minSpanTree) {System.out.print("(" + Tree[0].toString() + "-" + Tree[1].toString() + ")");}System.out.println("}");}} 4.举例说明Prim算法实现过程 以下图为例： 测试类：// ⼿动创建⼀个⽤于测试最⼩⽣成树算法的⽆向⽹public static AdjacencyMatrixGraphINF createUDNByYourHand_ForMiniSpanTree() {Object vexs_UDN[] = {"V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"};int arcsNum_UDN = 15;int[][] arcs_UDN = new int[vexs_UDN.length][vexs_UDN.length];for (int i = 0; i < vexs_UDN.length; i++) // 构造⽆向图邻接矩阵for (int j = 0; j < vexs_UDN.length; j++)if (i==j) {arcs_UDN[i][j]=0;} else {arcs_UDN[i][j] = arcs_UDN[i][j] = INFINITY;}arcs_UDN[0][5] = 11;arcs_UDN[1][2] = 18;arcs_UDN[1][6] = 16;arcs_UDN[1][8] = 12;arcs_UDN[2][3] = 22;arcs_UDN[2][8] = 8;arcs_UDN[3][4] = 20;arcs_UDN[3][6] = 24;arcs_UDN[3][7] = 16;arcs_UDN[3][8] = 21;arcs_UDN[4][5] = 26;arcs_UDN[4][7] = 7;arcs_UDN[5][6] = 17;arcs_UDN[6][7] = 19;for (int i = 0; i < vexs_UDN.length; i++) // 构造⽆向图邻接矩阵for (int j = i; j < vexs_UDN.length; j++)arcs_UDN[j][i] = arcs_UDN[i][j];return new AdjMatGraph(GraphKind.UDN, vexs_UDN.length, arcsNum_UDN, vexs_UDN, arcs_UDN);}public static void main(String[] args) throws Exception {AdjMatGraph UDN_Graph = (AdjMatGraph) createUDNByYourHand_ForMiniSpanTree();MiniSpanTree_Prim.Prim(UDN_Graph, "V0");} 输出为：通过Prim算法得到的最⼩⽣成树序列为: {(V0-V1)(V0-V5)(V1-V8)(V8-V2)(V1-V6)(V6-V7)(V7-V4)(V7-V3)} 分析算法执⾏过程：从V0开始：-count为0，k为0，closeEdges数组的-lowCost为{0 10 INF INF INF 11 INF INF INF}，adjVex数组为{V0，V0，V0，V0，V0，V0，V0，V0，V0}-⽐较lowCost，于是k为1，adjVex[1]为V0，minSpanTree[0]为（V0，V1），lowCost为{0 0 INF INF INF 11 INF INF INF}-k为1，与V1的权值⾏⽐较，得到新的-lowCost为：{0 0 18 INF INF 11 16 INF 12}，adjVex数组为{V0，V0，V1，V0，V0，V0，V1，V0，V1}-⽐较lowCost，于是k为5，adjVex[5]为V0，minSpanTree[1]为（V0，V5），lowCost为{0 0 18 INF INF 0 16 INF 12}-k为5，与V5的权值⾏⽐较，得到新的-lowCost为{0 0 18 INF 26 0 16 INF 12}，adjVex数组为{V0，V0，V1，V0，V5，V0，V1，V0，V1}-⽐较lowCost，于是k为8，adjVex[8]为V1，minSpanTree[2]为（V1，V8），lowCost为{0 0 18 INF INF 0 16 INF 0}... 三、克鲁斯卡尔（Kruskal）算法 1.Kruskal算法描述 Kruskal算法是根据边的权值递增的⽅式，依次找出权值最⼩的边建⽴的最⼩⽣成树，并且规定每次新增的边，不能造成⽣成树有回路，直到找到n-1条边为⽌。
