下载文档原格式
数据结构中的树与图算法教程第一章树的基本概念与遍历算法树是一种非线性数据结构，它由若干个节点组成，这些节点以层级的方式连接，形成分支的结构。
树中的一个节点被称为根节点，它没有父节点；其他节点可以有一个或多个父节点，这些节点被称为子节点。
树具有分支，但没有循环。
1.1 具体树的概念在树的结构中，每个节点可以有零个或者多个子节点，但是只能有一个父节点。
树具有层级关系，通过连接节点的边表示。
1.2 树的分类常见的树包括二叉树、二叉搜索树、红黑树等。
其中，二叉树是一种特殊的树结构，它的每个节点最多可以有两个子节点。
1.3 树的遍历算法树的遍历算法主要有前序遍历、中序遍历和后序遍历。
前序遍历是以根节点、左子树、右子树的顺序进行遍历；中序遍历是以左子树、根节点、右子树的顺序进行遍历；后序遍历是以左子树、右子树、根节点的顺序进行遍历。
第二章树的存储结构与常见应用2.1 树的存储结构树的存储结构有两种常见的实现方式，分别是链表实现和数组实现。
链表实现利用指针进行节点的连接，数组实现则使用数组的索引来表示节点之间的关系。
2.2 平衡二叉树平衡二叉树是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1。
平衡二叉树的插入和删除操作都可以通过旋转操作进行平衡。
2.3 哈夫曼树哈夫曼树是一种特殊的二叉树，用于编码和解码数据。
哈夫曼树中出现频率高的字符距离根节点较近，而出现频率低的字符距离根节点较远，以实现编码的高效率。
第三章图的基本概念与遍历算法3.1 图的基本概念图是由节点和边组成的非线性数据结构。
节点表示实体，边表示节点之间的关系。
图可以分为有向图和无向图两种类型，有向图的边是有方向的，无向图的边没有方向。
3.2 图的存储结构图的存储结构有邻接矩阵和邻接表两种常见的方式。
邻接矩阵是一个二维数组，用于表示节点之间的连接关系；邻接表是由链表或者数组实现的，用于表示每个节点相邻节点的信息。
3.3 图的遍历算法图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。
数据结构树知识点总结图一、树的定义树是一种抽象的数据结构，它是由n（n≥0）个节点组成的有限集合，其中一个节点被指定为根节点，其他节点被划分为m（m≥0）个互不相交的子集T1、T2、...、Tm，每个子集本身又是一棵树。
树的定义可以用递归方式来描述，即树是由一个根节点和若干颗子树组成的。
其中，根节点没有父节点，每个子树的根节点都是父节点的孩子节点。
二、树的特点1. 树是一种层次结构：树中的节点可以分层次地组织，也就是包含父子关系。
根节点是树的第一层，它的子节点是树的第二层，以此类推。
2. 树是一种非线性结构：树中的节点之间的关系是非线性的，每个节点可以有多个子节点，但只有一个父节点。
3. 树是一种递归结构：树的定义中包含了对子树的定义，因此树是一种递归结构，通过递归的方式可以方便地对树进行操作。
4. 树是一种有序结构：树中的节点之间存在明确定义的顺序关系，因此可以用来表示有序集合。
三、树的基本操作1. 树的创建：创建一棵树需要先创建根节点，然后在根节点上添加子节点，逐层递归地创建子树。
2. 树的遍历：树的遍历是指按照一定顺序访问树中的每个节点，常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。
3. 树的查找：树的查找是指在树中查找指定的节点，包括广度优先搜索（BFS）和深度优先搜索（DFS）两种方式。
4. 树的插入：树的插入是指将新节点插入到树中的指定位置，可以在根节点或指定节点的子节点上进行插入操作。
5. 树的删除：树的删除是指将指定节点从树中删除，可以删除叶子节点、中间节点或整棵子树。
6. 树的修改：树的修改是指对树中的节点进行数值或结构的改变，包括修改节点的值、替换子树等操作。
四、常见类型的树1. 二叉树（Binary Tree）：每个节点最多含有两个子节点的树，包括普通二叉树、满二叉树和完全二叉树等。
2. 平衡二叉树（Balanced Binary Tree）：每个节点的左子树和右子树的高度差不超过1的二叉树。
《数据结构》树的基本操作数据结构是计算机科学中的重要概念，它是指在计算机内存中组织数据的方式。
树是一种重要的数据结构，它具有层次结构和非线性的特点。
树的基本操作包括插入、删除、和遍历。
本文将详细介绍树的基本操作。
首先，我们先了解一下树的基本概念。
树由节点和边组成，每个节点可以有多个子节点，但每个子节点只能有一个父节点。
树有一个根节点，根节点没有父节点。
除了根节点之外，每个节点都有且仅有一个父节点。
节点之间的连接称为边。
树的基本操作之一是插入操作。
插入操作是指在树中添加新节点的过程。
要插入一个节点，需要找到它的父节点，然后将父节点的子节点指针指向新节点。
插入操作的时间复杂度为O(1)，因为它只需要修改指针。
另一个基本操作是删除操作。
删除操作是指将一个节点及其所有子节点从树中移除的过程。
要删除一个节点，需要找到它的父节点，然后将父节点的子节点指针指向它的子节点。
删除操作的时间复杂度取决于树的结构，通常为O(logn)到O(n)之间。
操作是树的另一个重要操作。
操作是指在树中查找一个特定节点的过程。
要一个节点，可以使用深度优先（DFS）或广度优先（BFS）算法。
DFS通过递归地遍历树的子节点，找到与目标节点相同的节点。
BFS通过遍历树的层次结构，逐层地目标节点。
操作的时间复杂度取决于树的深度，通常为O(logn)到O(n)之间。
最后，树的遍历操作是指按照一定顺序访问树中的所有节点。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后递归地遍历左子树和右子树。
中序遍历先递归地遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历先递归地遍历左子树和右子树，最后访问根节点。
树的遍历操作的时间复杂度为O(n)，其中n是树的节点数。
综上所述，树的基本操作包括插入、删除、和遍历。
这些操作在解决各种实际问题和算法中起着重要的作用。
掌握了树的基本操作，可以更好地理解和应用数据结构和算法。
同时，对于日常编程工作和面试准备也是非常有帮助的。
数据库技术知识数据结构的算法对于将要参加计算机等级考试的考生来说，计算机等级考试的知识点辅导是非常重要的复习资料。
以下是收集的数据库技术知识数据结构的算法，希望大家认真阅读!1、数据：数据的基本单位是数据元素。
数据元素可由一个或多个数据项组成。
数据项是数据的不可分割的最小单位2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构顺序存储结构：顺序存储计算公式Li=L0+(i-1)×K顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小b、逻辑上相邻的节点物理上不一定相邻。
c、插人、删除等不需要大量移动节点4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。
5、链表：线性链表(单链表和双向链表等等)和非线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。
(注意结点的插入和删除操作)6、栈：“后进先出”(LIFO)表。
栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等7、队列：“先进先出”线性表。
应用：树的层次遍历8、串：由零个或多个字符组成的有限序列。
9、多维数组的顺序存储：10、稀疏矩阵的存储：下三角矩阵顺序存储其他常见的存储方法还有三元组法和十字链表法11、广义表：由零个或多个单元素或子表所组成的有限序列。
广义表的元素可以是子表，而子表的元素还可以是子表12、树型结构：非线性结构。
常用的树型结构有树和二叉树。
二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
数据结构最基础的十大算法数据结构是计算机科学中的重要分支，它研究如何组织和存储数据以便于访问和修改。
在数据结构中，算法是解决问题的关键。
下面将介绍数据结构中最基础的十大算法。
1. 线性搜索算法线性搜索算法是最简单的算法之一，它的作用是在一个列表中查找一个特定的元素。
该算法的时间复杂度为O(n)，其中n是列表中元素的数量。
2. 二分搜索算法二分搜索算法是一种更高效的搜索算法，它的时间复杂度为O(log n)。
该算法要求列表必须是有序的，它通过将列表分成两半来查找元素，直到找到目标元素为止。
3. 冒泡排序算法冒泡排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过比较相邻的元素并交换它们的位置来排序列表。
4. 快速排序算法快速排序算法是一种更高效的排序算法，它的时间复杂度为O(nlog n)。
该算法通过选择一个基准元素并将列表分成两部分来排序列表。
5. 插入排序算法插入排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过将每个元素插入到已排序的列表中来排序列表。
6. 选择排序算法选择排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。
该算法通过选择最小的元素并将其放在列表的开头来排序列表。
7. 堆排序算法堆排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。
该算法通过将列表转换为堆并进行排序来排序列表。
8. 归并排序算法归并排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。
该算法通过将列表分成两部分并将它们合并来排序列表。
9. 哈希表算法哈希表算法是一种高效的数据结构，它的时间复杂度为O(1)。
该算法通过将键映射到哈希表中的位置来存储和访问值。
10. 树算法树算法是一种重要的数据结构，它的时间复杂度取决于树的深度。
树算法包括二叉树、AVL树、红黑树等。
以上是数据结构中最基础的十大算法，它们在计算机科学中有着广泛的应用。
数据结构树的实验报告数据结构树的实验报告一、引言数据结构是计算机科学中的重要概念，它可以帮助我们组织和管理数据，提高程序的效率和性能。
而树作为一种常见的数据结构，具有广泛的应用。
本实验旨在通过实践操作，深入理解树的基本概念、特性和操作。
二、实验目的1. 掌握树的基本概念和特性；2. 熟悉树的基本操作，如插入、删除、查找等；3. 理解树的遍历算法，包括前序、中序和后序遍历；4. 实现树的基本功能，并验证其正确性和效率。
三、实验过程1. 构建树的数据结构首先，我们需要定义树的数据结构。
树由节点组成，每个节点可以有零个或多个子节点。
我们可以使用面向对象的思想，创建一个节点类和树类。
节点类包含节点值和子节点列表的属性，以及插入、删除子节点等操作的方法。
树类则包含根节点的属性和遍历方法等。
2. 插入和删除节点在树中插入和删除节点是常见的操作。
插入节点时，我们需要找到合适的位置，并将新节点作为子节点添加到相应的位置。
删除节点时，我们需要考虑节点的子节点和兄弟节点的关系，并进行相应的调整。
通过实现这两个操作，我们可以更好地理解树的结构和特性。
3. 查找节点树中的节点可以通过值进行查找。
我们可以使用递归或迭代的方式，在树中进行深度优先或广度优先的搜索。
在查找过程中，我们需要注意节点的存在性和唯一性，以及查找算法的效率。
4. 树的遍历树的遍历是指按照一定的顺序访问树中的所有节点。
常见的遍历方式有前序、中序和后序遍历。
前序遍历先访问根节点，然后递归地访问左子树和右子树；中序遍历先递归地访问左子树，然后访问根节点，最后访问右子树；后序遍历先递归地访问左子树和右子树，最后访问根节点。
通过实现这三种遍历算法，我们可以更好地理解树的结构和遍历过程。
五、实验结果与分析通过实验，我们成功地实现了树的基本功能，并验证了其正确性和效率。
我们可以通过插入和删除节点操作，构建出不同形态的树，并进行查找和遍历操作。
在插入和删除节点时，树的结构会发生相应的变化，但其基本特性仍然保持不变。
数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义树是计算机算法最重要的⾮线性结构。
树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。
树是⼀种以分⽀关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。
{N.沃恩}(树是n(n≥1)个结点组成的有限集合。
{D.E.Knuth})在任意⼀棵⾮空树中：⑴有且仅有⼀个没有前驱的结点----根(root)。
⑵当n>1时，其余结点有且仅有⼀个直接前驱。
⑶所有结点都可以有0个或多个后继。
b. 树是n(n≥0)个结点组成的有限集合。
在任意⼀棵⾮空树中：⑴有⼀个特定的称为根（root）的结点。
⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。
每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）树的固有特性---递归性。
即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。
树的基本操作1、InitTree(&T) 初始化2、DestroyTree(&T) 撤消树3、CreatTree(&T,F) 按F的定义⽣成树4、ClearTree(&T) 清除5、TreeEmpty(T) 判树空6、TreeDepth(T) 求树的深度7、Root(T) 返回根结点8、Parent(T,x) 返回结点 x 的双亲9、Child(T,x,i) 返回结点 x 的第i 个孩⼦10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树12、traverse(T) 遍历树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。
●结点的度: 结点拥有⼦树的数⽬●叶结点: 度为零的结点●分枝结点: 度⾮零的结点●树的度: 树中各结点度的最⼤值●孩⼦: 树中某个结点的⼦树的根●双亲: 结点的直接前驱●兄弟: 同⼀双亲的孩⼦互称兄弟●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。
数据结构树知识点总结大全本文将对树结构的知识点进行详细的总结，包括树的基本概念、树的分类、树的遍历、树的应用以及一些相关的算法和数据结构。
通过本文的学习，读者将对树结构有一个全面的了解，并可以在实际的编程和问题解决中灵活运用树结构。
一、树的基本概念1.1 节点和边1.2 根节点、叶子节点和内部节点1.3 子树和森林1.4 高度和深度1.5 有序树和无序树1.6 二叉树二、树的分类2.1 二叉搜索树2.2 平衡二叉树2.3 B树和B+树2.4 红黑树2.5 AVL树2.6 Trie树2.7 堆和堆排序2.8 Huffman树2.9 伸展树2.10 Splay树三、树的遍历3.1 深度优先遍历3.1.1 前序遍历3.1.2 中序遍历3.1.3 后序遍历3.2 广度优先遍历四、树的应用4.1 数据库索引4.2 文件系统4.3 图形学中的场景图4.4 解析树4.5 代码优化4.6 线段树4.7 树状数组4.8 字典树4.9 贝叶斯分类器中的朴素贝叶斯算法五、树的相关算法和数据结构5.1 查找5.1.1 二叉搜索树的插入和删除5.1.2 二叉搜索树的查找5.1.3 递归查找和非递归查找5.2 排序5.2.1 二叉搜索树的中序遍历5.2.2 堆排序5.2.3 AVL树的平衡调整5.2.4 红黑树的插入和删除5.3 最短路径5.3.1 二叉堆的应用5.3.2 AVL树的应用5.4 动态规划5.4.1 线段树的应用5.4.2 树状数组的应用六、结语树结构是数据结构中非常重要的一部分，它有着广泛的应用领域。
通过本文的学习，读者可以对树结构有一个全面的了解，并可以在实际的编程和问题解决中灵活运用树结构。
希望本文对读者有所帮助，也希望读者可以通过学习树结构，提高自己在算法和数据结构方面的能力，为未来的编程之路打下坚实的基础。
考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。
最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。
《数据结构》课程设计任务书学期：11-12-2 班级：网络10一、设计目的《数据结构》是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。
3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。
4、编程语言任选。
三、设计选题题一：线索二叉树（**）任务：1.建立中序线索二叉树，并且中序遍历；2.求中序线索二叉树上已知结点中序的前驱和后继；需求分析和概要设计：建立中序线索二叉树，并且中序遍历。
首先就是要建立树，再将树中序线索化。
求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。
也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。
详细设计：树的结构体的声明：typedef char TElemtype;typedef enum PointerTag{Link,Thread}; //设置标志：Link为指针，Thread为线索typedef struct BiThrNode{ //树结点结构体TElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;}BiThrNode,*BiThrTree;相关函数的声明：void InitBiTree(BiThrTree &T); //初始化树void CreatBiTree(BiThrTree &T); //建立二叉树void InOrderThreading(BiThrTree &Thrt,BiThrTree &T); //中序线索二叉树void InThreading(BiThrTree p); //线索化int InOrderTraverse_Thr(BiThrTree T); //中序遍历void InOrderThread_BeAf(); //求已知结点中序的前驱和后继初始化树：void InitBiTree(BiThrTree &T){T = new BiThrNode;if(!T) exit(1);T = NULL;}建立二叉树：void CreatBiTree(BiThrTree &T){char ch;cin>>ch;if(ch == '@') T = NULL;else{T = new BiThrNode;if(!T) exit(1);T->data = ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}}中序线索二叉树：void InOrderThreading(BiThrTree &Thrt,BiThrTree &T){Thrt = new BiThrNode; //设置头结点if(!Thrt) exit(1);Thrt->LTag = Link; //头结点左边标志为指针Thrt->RTag =Thread; //右边的为线索Thrt->rchild = Thrt; //有孩子指向头结点本身if(!T) Thrt->lchild = Thrt; //若树根结点为空，则头结点左孩子指向头结点else{ //若根结点不为空，Thrt->lchild = T; //头结点左孩子指向根结点pre = Thrt; //设置指针pre指向头结点InThreading(T); //线索化树Tpre->rchild = Thrt;pre->RTag = Thread;Thrt->rchild = pre;}}线索化树:void InThreading(BiThrTree p){if(p){InThreading(p->lchild); //线索化左子树if(!p->lchild){p->LTag = Thread;p->lchild = pre;}if(!pre->rchild){pre->RTag = Thread;pre->rchild = p;}pre = p;InThreading(p->rchild);}}中序遍历：int InOrderTraverse_Thr(BiThrTree T){BiThrTree p;int i=1;p = T->lchild;while(p!=T){while(p->LTag!=Thread)p = p->lchild;cout<<p->data<<" ";a[i]=p->data;i++;length++;while(p->RTag==Thread&&p->rchild!=T){p = p->rchild;cout<<p->data<<" ";a[i]=p->data; //将结点存于数组中i++;length++;}p = p->rchild;}return OK;}测试结果和设计心得体会：通过对树的中序线索化使我更加清楚树的有关操作算法。
题二：最小生成树问题（***）【问题描述】若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
【系统要求】1．利用克鲁斯卡尔算法求网的最小生成树。
2．利用普里姆算法求网的最小生成树。
3．要求输出各条边及它们的权值。
【测试数据】由学生任意指定，但报告上要求写出多批数据测试结果。
【实现提示】通信线路一旦建成，必然是双向的。
因此，构造最小生成树的网一定是无向网。
设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。
图的存储结构的选取应和所作操作相适应。
为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。
【选作内容】利用堆排序实现选择权值最小的边。
需求分析和概要设计：用克鲁斯卡尔和普里姆算法生成图的最小生成树。
首先要构造出图，然后将图生成树，故要使用邻接矩阵储存图。
详细设计：有关结构体的声明：typedef char VertexType;typedef int VRType;typedef char InfoType;typedef struct ArcCell{VRType adj; //VRType是顶点的关系类型。
无权图用1或0表示相连否。
对带权图，则为权值类型。
InfoType *info; //表示相关信息的指针}ArcCell,AdjMatrix[MAX_VEXTEX_NUM][MAX_VEXTEX_NUM];typedef struct{VertexType vexs[MAX_VEXTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧度数}MGraph;typedef struct{VertexType adjvex;VRType lowcost;}closedge;typedef struct{VertexType begin;VertexType end;VRType weight;}EdgeType;相关函数的声明：int CreateGraph(MGraph &G); //创造图后要返回其值int LocateVex(MGraph G,VertexType u); //求点u在图中的位置int minmum( closedge closedge[MAX_VEXTEX_NUM]);//求最小值函数void MinSpanTree_PRIM(MGraph G,VertexType u); //PRIM最小生成树void MinSpanTree_KRUSKAL(MGraph G); // KRUSKAL最小生成树创造图：int CreateGraph(MGraph &G){int i,j,k,w;VertexType v1,v2;cout<<"请输入顶点数和边数"<<endl;cin>>G.vexnum>>G.arcnum;high=G.arcnum;cout<<"请输入顶点信息"<<endl;for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i) //初始化邻接矩阵{for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj =INFINITY; //最大值∞G.arcs[i][j].info=NULL;}}cout<<"请输入每条边对应的两个顶点(v1,v2)及其权值(w)"<<endl;for(k=0;k<G.arcnum;++k){cin>>v1>>v2>>w;i=LocateVex(G,v1);j=LocateVex(G,v2);edges[k+1].begin=v1;edges[k+1].end=v2;G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;edges[k+1].weight=w;}return OK;}PRIM最小生成树：void MinSpanTree_PRIM(MGraph G,VertexType u){int k,j,i;closedge closedge[MAX_VEXTEX_NUM];cin>>u;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minmum(closedge);cout<<"边：("<<closedge[k].adjvex<<","<<G.vexs[k]<<")权值："<<closedge[k].lowcost<<endl;closedge[k].lowcost=0;for(j=1;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}KRUSKAL最小生成树：void MinSpanTree_KRUSKAL(MGraph G){HeapSort();for(int k=1;k<=G.arcnum;k++)cout<<edges[k].weight<<" ";cout<<endl;int father[MAX_VEXTEX_NUM];int i,j,vf1,vf2;for(i=0;i<G.vexnum;i++)father[i]=-1;i=0;j=0;while(i<G.arcnum&&j<G.vexnum-1){vf1=Find(father,edges[i+1].begin);vf2=Find(father,edges[i+1].end);{if(vf1!=vf2){father[vf2]=vf1;j++;cout<<"边：("<<edges[i+1].begin<<","<<edges[i+1].end<<")权值："<<edges[i+1].weight<<endl;}}i++;}}测试结果和设计心得体会：通过对图的操作更加明白图与树之间的关系。
