数据结构与算法 课件 魏振钢 第6-10章 树和二叉树 -算法思想

第6章树和二叉树1问题导入：层次化数据的高效解决方案

现实中的层次数据实例文件系统目录、企业组织架构、网页DOM树等，均体现数据元素间逐层递进的层次关系。

线性结构的局限性线性表、数组难以高效存储多对多层次数据，导致存储效率低、操作复杂。

树结构的核心优势自然刻画“一个对象拥有多个子对象”关系，灵活表达层次化组织，操作（查找/插入等）效率高。

二叉树的典型应用凭借结构简洁性，广泛应用于编译原理、数据压缩、人工智能、数据库索引等领域。目录01.树的定义和基本术语02.二叉树的定义、性质与存储03.遍历二叉树04.线索二叉树05.树和森林06.应用案例6.1树的定义和基本术语树的定义定义树是n(n≥0)个结点的有限集。在一棵非空树中：1.有且仅有一个特定的称为根（root）的结点。2.当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，...，Tm，每个集合本身又是一棵树，并且称为根的子树。图示图：典型的树结构示例（节点A为根节点）

树的抽象数据类型定义

数据对象与数据关系数据对象D是具有相同特性的数据元素集合；数据关系R为二元关系，含唯一根结点，其余结点划分为互不相交的子树。

查找类基本操作包括求根结点（Root(T)）、当前结点值（Value(T，cur_e)）、双亲（Parent(T，cur_e)）、左孩子（LeftChild(T，cur_e)）、树深度（TreeDepth(T)）等。

插入与删除操作插入操作如InsertChild(T，p，i，c)（将树c插入为p的第i棵子树）；删除操作如DeleteChild(T，p，i)（删除p的第i棵子树）。

遍历与初始化操作遍历操作TraverseTree(T，Visit())按某种次序访问所有结点；初始化操作包括InitTree(T)（置空树）、CreateTree(T，definition)（按定义构造树）。树的基本术语（一）基本概念结点：包含数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数目。例如，A的度为3。叶子（终端结点）：度为0的结点。例如，E，K，L，G，H，I，M。非终端结点（分支结点）：度不为0的结点。例如，A，B，C，D，F。树的度：树内所有结点度的最大值。此树的度为3。树的示例树的基本术语（二）基本概念孩子/双亲：结点子树的根称为该结点的孩子，该结点称为孩子的双亲。例如，D是A的孩子，A是D的双亲。兄弟：同一个双亲的孩子之间互称兄弟。例如，H，I，J互为兄弟。祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙：某结点子树中的结点都是该结点的子孙层次：从根开始定义，根为第一层，其孩子为第二层，依此类推。深度（高度）：树中结点的最大层次。此树的深度为4。森林：m(m≥0)棵互不相交的树的集合。6.2二叉树二叉树的定义与基本形态二叉树的递归定义二叉树或为空树，或由一个根结点加上两棵互不相交的左子树和右子树组成，左、右子树本身也是二叉树。二叉树的5种基本形态包括：空二叉树、仅有根结点、根+左子树、根+右子树、根+左子树+右子树。二叉树与普通树的区别二叉树每个结点最多有2个子树且左右子树有序；普通树结点子树数无限制且子树无序。二叉树的五种基本形态形态说明空二叉树只有根结点的二叉树根结点只有左子树根结点只有右子树根结点既有左子树又有右子树图示二叉树的性质核心性质

二叉树的性质核心性质

二叉树的性质核心性质

特殊二叉树：满二叉树与完全二叉树满二叉树的定义与特点

完全二叉树的定义与特点与满二叉树前n个结点编号一一对应，叶子结点仅在最后两层，左子树深度≥右子树深度。满二叉树与完全二叉树的异同相同点：每层结点从左至右排列；不同点：满二叉树所有层结点数均满，完全二叉树最后一层可不满但需从左到右连续。二叉树的性质核心性质

二叉树的性质核心性质

二叉树的顺序存储二叉树的顺序存储示例存储原理顺序存储结构使用一组连续的存储单元来存放二叉树中的结点。通常是按照从上到下、从左到右的顺序对二叉树的结点进行编号，然后将结点存入数组中对应下标的位置。

适用场景特别适合完全二叉树。对于完全二叉树，顺序存储可以充分利用存储空间，且通过简单的公式就能计算出父子节点的位置。二叉树的链式存储（二叉链表）存储原理链式存储结构用指针来表示结点之间的逻辑关系。最常用的是二叉链表，每个结点包含三个域：数据域(data)、左指针域(lchild)、右指针域(rchild)。//----二叉树的二叉链表表示----typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左、右孩子指针}BiTNode,*BiTree;图示与说明二叉链表结构灵活，可表示任意二叉树，存储空间利用率高。二叉树的链式存储（三叉链表）存储原理若需快速查找结点双亲,可增加一个指向其双亲结点的指针域,形成三叉链表。///----二叉树的三叉链表表示----typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左、右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;图示与说明

二叉树的存储结构对比顺序存储结构使用一维数组按层次存储完全二叉树，编号为i的结点存于下标i处，适用于满二叉树和完全二叉树，空间利用率高。

链式存储结构：二叉链表每个结点含数据域、左孩子指针和右孩子指针，n个结点有n+1个空链域，适用于非完全二叉树，操作灵活。

链式存储结构：三叉链表在二叉链表基础上增加双亲指针域，可快速查找双亲结点，空间开销略增，适用于需频繁访问双亲的场景。

存储结构对比与适用场景顺序存储适合完全二叉树的紧凑存储；链式存储适合任意二叉树，尤其是频繁插入删除的场景。6.3遍历二叉树遍历的定义与意义遍历的概念与搜索路径

遍历二叉树是按某条搜索路径巡访每个结点，使每个结点被访问且仅被访问一次。访问含义广泛，如输出信息等，是获取树中信息的关键操作。按层次遍历路径

从上到下、从左到右按层次依次访问结点，是一种直观易懂的搜索路径。先左后右遍历路径

先遍历左子树，再遍历右子树，基于此有先序、中序、后序三种有效遍历组合。先右后左遍历路径

假如用L、D、R分别表示遍历左子树、访问根结点和遍历右子

树。先遍历右子树，再遍历左子树，有DRL、RDL、RLD等组合，应用场景相对较少。递归遍历算法：先序、中序、后序操作定义：若二叉树为空则空操作，否则先访问根结点，再递归先序遍历左子树，最后递归先序遍历右子树。算法实现通过递归调用完成。先序遍历递归定义与实现01操作定义：若二叉树为空则空操作，否则先递归中序遍历左子树，再访问根结点，最后递归中序遍历右子树。实现方式与先序类似，仅访问根结点时机不同。中序遍历递归定义与实现02操作定义：若二叉树为空则空操作，否则先递归后序遍历左子树，再递归后序遍历右子树，最后访问根结点。其递归实现体现了左右子树遍历完成后访问根的特点。后序遍历递归定义与实现03二叉树的遍历——先序遍历操作定义访问根结点。先序遍历左子树。先序遍历右子树。示例与结果ABCDEFGHK二叉树的遍历——先序遍历算法二叉树的遍历——中序中序遍历(LDR)1.中序遍历左子树。2.访问根结点。3.中序遍历右子树。BDCAHGKFE二叉树的遍历——后序中序遍历(LRD)1.后序遍历左子树。2.后序遍历右子树。3.访问根结点。DCBHKGFEA二叉树的遍历——层次遍历操作定义与思路层次遍历是指从上到下、从左到右依次访问二叉树的每一层节点。实现思路：通常借助队列（Queue）来实现。示例与结果遍历结果：A→B→C→D→E二叉树的遍历——非递归遍历算法算法思路利用栈模拟递归过程，从根结点开始，向左走到尽头并将结点入栈，栈顶元素出栈访问后，移动到其右孩子，重复操作直至栈空且指针为空。线性结构与树结构核心对比

结构关系线性结构：元素仅含单一前驱/后继（一对一）；树结构：结点可含多个子结点（一对多），呈现“根-子-孙”层级。

存储与复杂度线性结构：存储为顺序/链式，简单易实现；树结构：非线性嵌套，支持递归定义，操作复杂度更高但表达更灵活。

访问与遍历线性结构：通过索引/指针顺序访问（如栈LIFO、队列FIFO）；树结构：遍历方式多样（前序/中序/后序/层次），适配复杂逻辑关系。

典型应用线性结构：表达式计算、任务调度（强顺序性场景）；树结构：目录索引、XML文档、AI决策树（层次化数据场景）。

遍历算法的应用01统计叶子结点个数先序遍历二叉树，遍历过程中判断结点是否为叶子（左右孩子均为空），若是则计数器增1。算法6-4通过递归实现该功能。

02求二叉树深度基于后序遍历，先分别求左、右子树深度，二叉树深度为左右子树深度最大值加1。算法6-5体现了这一递归求解过程。

03复制二叉树后序遍历待复制二叉树，先复制左、右子树，再创建当前结点副本并连接子树。算法6-6通过递归完成二叉树的复制操作。

04遍历是二叉树操作的基础遍历可用于求结点双亲、孩子，判定层次等操作，也可在遍历中生成结点建立存储结构，是实现二叉树各种操作的核心基础。6.4线索二叉树线索二叉树的概念与作用问题背景：传统二叉链表的局限二叉链表存储结构中，仅能直接获取结点的左、右孩子信息，无法直接得知其前驱和后继。n个结点的二叉链表存在n+1个空链域，造成空间浪费。核心思路：利用空链域存储线索通过修改空指针域，存储结点在遍历序列中的前驱和后继信息，将非线性结构线性化，实现高效访问。基本定义：线索与线索二叉树线索：指向结点前驱或后继的指针；线索链表：增加标志域（LTag/RTag）的二叉链表；线索二叉树：加上线索的二叉树，可实现快速遍历。

线索二叉树的存储结构结点结构：标志域与指针域结点包含lchild（左指针）、LTag（左标志）、data（数据）、RTag（右标志）、rchild（右指针）。LTag/RTag为0表示指针指向孩子，为1表示指向线索。

标志域的含义LTag=0：lchild指向左孩子；LTag=1：lchild指向前驱。RTag=0：rchild指向右孩子；RTag=1：rchild指向后继。二叉树线索化对二叉树进行某种次序遍历并转换为线索二叉树的过程称为线索化中序线索二叉树

对应的中序序列为B

D

C

AHGKF

E建立线索链表线索化本质二叉链表空指针改造为前驱/后继线索，通过遍历过程动态修改空指针实现。

中序线索化关键指针遍历时维护pre（刚访问结点）与p（当前结点），pre始终指向p的前驱结点。

线索化核心目标利用空指针存储遍历顺序关系，解决传统二叉链表仅存父子关系、无法直接获取前驱后继的问题。

voidInThreading(BiThrTreep){if(p){//对以p为根的非空二叉树进行线索化InThreading(p->lchild);//左子树线索化if(!p->lchild)//建立前驱线索{p->LTag=Thread;p->lchild=pre;}if(!pre->rchild)//建立后继线索{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化}}//InThreading建立线索链表StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点Thrt=newBiThrNode();//创建头结点if(!Thrt)returnerror;//内存分配失败返回错误Thrt->LTag=Link;Thrt->RTag=Thread;//建立头结点Thrt->rchild=Thrt;//右指针回指if(!T){Thrt->lchild=Thrt;//若二叉树空,则左指针回指}else{Thrt->lchild=T;pre=Thrt;InThreading(T);//中序遍历进行线索化pre->rchild=Thrt;//最后一个结点线索化pre->RTag=Thread;Thrt->rchild=pre;}returnOK;}线索二叉树遍历

遍历高效性：无需栈辅助线索二叉树遍历时间复杂度为O(n)，通过线索直接访问前驱/后继，避免递归或栈空间开销，适用于频繁遍历场景。

双向线索链表的优势添加头结点，左指针指向根，右指针指向中序最后一个结点；首结点左线索和尾结点右线索均指向头结点，支持双向遍历（从首结点顺后继或从尾结点顺前驱）。StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点,头结点的左链lchild指向根结点,可参见线索化算法//中序遍历二叉线索树T的非递归算法,对每个数据元素调用函数Visit()p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时,p==Twhile(p->LTag==Link)p=p->lchild;//找到第一个结点if(!Visit(p->data))returnerror;//访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;//p进至其右子树根}returnok;}6.5树和森林树的存储结构（一）：双亲表示法定义与思想双亲表示法是一种顺序存储结构，用一组连续的存储空间来存储树的结点。每个结点包含两个域：数据域和双亲域。数据域存储结点的数据信息，双亲域存储该结点的双亲在数组中的位置。结构定义与图示#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;//数据域intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;}PTree;数组中每个元素代表一个节点，parent值为-1表示根节点。树的存储结构（二）：孩子表示法定义与思想孩子表示法是将每个结点的孩子结点排列起来，以单链表作为存储结构，称为孩子链表。n个结点共有n个孩子链表（叶子结点的单链表为空），然后将n个结点的数据和n个孩子链表的头指针组成一个顺序表。结构定义与图示//-----树的孩子链表存储表示-----typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;每个节点作为一个表头，其后链接的是它所有的孩子节点。树的存储结构（三）：孩子兄弟表示法定义与思想孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟结点。结构定义与图示typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;每个节点有两个指针，一个指向它的第一个孩子，另一个指向它的下一个兄弟。

树的存储结构双亲表示法以连续空间存储树的结点，每个结点包含数据域和指示双亲位置的指示器。优点是便于查找双亲结点，缺点是求孩子结点需遍历整个结构。

孩子表示法将每个结点的孩子结点排列成单链表，头指针组成顺序存储的线性表。优点是便于涉及孩子的操作，可与双亲表示法结合使用。

孩子兄弟表示法每个结点包含数据域、指向第一个孩子的指针和指向下一个兄弟的指针。能有效反映树的层次结构和结点关系，便于实现树的各种操作。树转换为二叉树：核心思想与步骤核心思想将树的孩子关系转换为二叉树的左孩子关系，将树的兄弟关系转换为二叉树的右孩子关系。这是树转二叉树的本质。转换三步骤加线：在所有兄弟结点之间加一条连线。抹线：对树中每个结点，只保留它与第一个孩子结点的连线。旋转：顺时针旋转整棵树，调整结构。森林与二叉树的转换

转换对应关系森林与二叉树存在一一对应关系，树的二叉链表表示与二叉树的存储结构相同，只是解释不同，森林的第一棵树子树森林对应二叉树左子树，剩余树对应右子树。森林转换为二叉树转换步骤1.将森林中的每一棵树分别转换为二叉树。2.将第一棵二叉树作为结果二叉树的根。3.将第二棵二叉树的根节点作为第一棵二叉树根节点的右孩子。4.依次类推，将后续二叉树连接为前一棵树的右子树。核心思想森林中的树与树之间是兄弟关系，因此在转换为二叉树时，它们依次作为前一棵树的右子树，从而将整个森林串联成一棵完整的二叉树。二叉树转换为森林转换步骤1.若二叉树B为空，则转换的森林F为空。2.若二叉树B非空，F首棵树根为二叉树B的根；首棵树的子树森林由B的左子树转换而成的森林，剩余森林由B右子树转换

树和森林的遍历树的遍历先根遍历：先访问根结点，再依次先根遍历各子树；后根遍历：先依次后根遍历各子树，再访问根结点；按层次遍历：自上而下、自左至右访问每个结点。

森林的遍历先序遍历：访问第一棵树的根，先序遍历其根的子树森林，再先序遍历剩余树的森林；中序遍历：中序遍历第一棵树根的子树森林，访问根，再中序遍历剩余树的森林。

与二叉树遍历的关系树的先根、后根遍历分别对应二叉树的先序、中序遍历；森林的先序、中序遍历即为其对应二叉树的先序、中序遍历。

树的计数基本概念相似二叉树指结构相同但结点数据不同；等价二叉树要求结构和数据都相同。树的计数问题是求具有n个结点的不同形态树的数目。

二叉树的计数

树的计数推导

6.6应用案例

哈夫曼树及其应用01哈夫曼树的定义与关键概念哈夫曼树（最优二叉树）是带权路径长度最短的二叉树，权值越大的结点离根越近。路径是结点间的路线，路径长度为边的数量，带权路径长度（WPL）是所有叶子结点权值与路径长度乘积之和。

02哈夫曼算法步骤1.初始化：将n个权值构造成n棵单根结点二叉树；2.选择与合并：选取权值最小的两棵树作为左右子树，构造新树，根权值为两子树权值之和；3.更新集合：将新树加入集合，删除原两棵树；4.重复操作至集合只剩一棵树。

03哈夫曼树构造实例以权值{7，5，2，4}为例，构造过程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最终WPL=7×1+5×2+4×3+2×3=35，为最优结构。

04哈夫曼编码在数据压缩中的应用以字符出现频率为权值构建哈夫曼树，左分支赋0、右分支赋1，从根到叶子路径形成前缀编码。高频字符编码短，低频字符编码长，实现数据压缩，且解码唯一无歧义。

哈夫曼树及其应用01哈夫曼树的定义与关键概念哈夫曼树（最优二叉树）是带权路径长度最短的二叉树，权值越大的结点离根越近。路径是结点间的路线，路径长度为边的数量，带权路径长度（WPL）是所有叶子结点权值与路径长度乘积之和。

02哈夫曼算法步骤1.初始化：将n个权值构造成n棵单根结点二叉树；2.选择与合并：选取权值最小的两棵树作为左右子树，构造新树，根权值为两子树权值之和；3.更新集合：将新树加入集合，删除原两棵树；4.重复操作至集合只剩一棵树。

03哈夫曼树构造实例以权值{7，5，2，4}为例，构造过程：先合并2和4得6，再合并5和6得11，最后合并7和11得18，最终WPL=7×1+5×2+4×3+2×3=35，为最优结构。

04哈夫曼编码在数据压缩中的应用以字符出现频率为权值构建哈夫曼树，左分支赋0、右分支赋1，从根到叶子路径形成前缀编码。高频字符编码短，低频字符编码长，实现数据压缩，且解码唯一无歧义。01哈夫曼编码的实现哈夫曼树的存储结构采用动态数组存储哈夫曼树结点，每个结点含权值、双亲及左右孩子指针typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表02从叶子到根逆向求编码算法从叶子结点出发，通过双亲指针逆向追溯至根，左孩子记0、右孩子记1，将编码存入工作空间，最后复制到编码表。需动态分配编码空间，时间复杂度O(n²)。03从根遍历求编码算法（无栈非递归）利用结点状态标志（0：未访问，1：左子树访问，2：右子树访问），遍历哈夫曼树，左分支加0、右分支加1，遇到叶子结点时登记编码。无需栈辅助，空间效率更高。04编码与解码过程分析编码：根据字符权值构建哈夫曼树，生成前缀编码；解码：从根开始，按编码序列（0左1右）遍历树，直至叶子结点得到字符，实现无歧义解码。哈夫曼树无度为1的结点，含n个叶子时共有2n-1个结点。人工智能中的决策树决策树的概念与构建过程决策树是树结构，分支结点表示特征测试，叶子结点代表类别或决策结果。构建从根开始，选择最优特征划分数据，递归划分至满足停止条件（如最大深度、样本同类别）。在分类任务中的应用用于医学诊断（症状→疾病）、垃圾邮件过滤（关键词→是否垃圾邮件）等。通过学习特征与类别关系，对新样本沿决策路径分类，如根据“年龄”“收入”预测用户购买行为。在回归任务中的应用预测连续值，如房地产房价（面积、户型等特征→房价）。通过划分数据空间，使叶子结点样本值接近平均值，新样本按特征路径找到对应叶子结点得预测值。决策树的优点与缺陷优点：可解释性强（结构直观）、处理非线性关系能力好、对数据要求低（无需假设分布）。缺陷：易过拟合（需剪枝）、对数据敏感（微小变化影响结构）、大规模数据计算复杂度高。6.7本章小结

知识体系梳理基本概念与术语树是n(n≥0)个结点的有限集，有且仅有一个根结点，其余结点可分为互不相交的子树。核心术语包括度（结点子树数量）、叶子（度为0的结点）、层次（根为第一层）、深度（最大层次）等。二叉树是特殊树结构，每个结点最多有左、右两棵子树，具有5种基本形态。

二叉树性质与存储结构二叉树性质：第i层至多2^(i-1)个结点；深度为k的二叉树至多2^k-1个结点；叶子结点数=度为2的结点数+1。存储结构分为顺序存储（适合满二叉树和完全二叉树）和链式存储（二叉链表含数据域及左、右指针，三叉链表增加双亲指针）。

遍历算法与线索二叉树遍历算法包括先序（根→左→右）、中序（左→根→右）、后序（左→右→根）及层次遍历，时间复杂度均为O(n)。线索二叉树通过利用空链域存储前驱/后继线索，实现高效遍历，无需栈辅助，时间复杂度O(n)。知识体系梳理

树与森林的转换及应用树与二叉树可通过孩子-兄弟表示法转换，森林转换为二叉树时，第一棵树的子树森林转为左子树，其余树转为右子树。应用案例包括哈夫曼树（最优二叉树，用于数据压缩编码）和决策树（机器学习中用于分类与回归）。学习意义与后续展望树结构的核心地位树和二叉树是处理层次化数据的基础结构，在文件系统、组织架构、DOM文档等场景中广泛应用。其非线性特性弥补了线性结构在表达多对多关系时的不足，为高效查找、插入、删除操作提供支撑。对后续学习的影响掌握树结构是学习高级数据结构（如B树、红黑树、堆）和算法（如动态规划、图论）的前提。二叉树的递归思想、遍历策略可迁移至复杂问题求解，如表达式解析、路径规划等。未来应用领域拓展在人工智能领域，决策树模型可用于医疗诊断、风险评估；在大数据处理中，哈夫曼编码优化存储与传输；在区块链技术中，默克尔树保障数据完整性。随着技术发展，树结构将在更多交叉领域发挥作用。感谢观看Q&A欢迎提问与交流第七章图数据结构与算法中国海洋大学本章目录01.图的定义和术语02.图的存储03.图的遍历04.图的应用（最短路径、最小生成树等）05.本章小结问题导入：复杂交通网络中的最优路径规划任务背景：复杂的交通网络作为旅行规划师，需规划从城市A到城市Z的路线。网络包含20个城市节点和上百条连接道路。每个道路（边）都带有不同的权重属性，如收费、时间、拥堵指数等，构成了一个典型的带权图结构。核心挑战：多约束条件优化旅行团需求苛刻，需要同时满足“最短时间”、“预算内费用”以及“避免频繁换乘”等多重目标。在如此复杂的网络中，如何快速找到一条平衡各方利益的最优路径，是本次任务的核心难点。问题本质：图结构的最短路径问题面对这样的交通“图”，我们需要利用图论算法来解决。将城市抽象为顶点(Vertex)，将道路抽象为边(Edge)，将费用和时间抽象为权重(Weight)。寻找最优路径的过程，本质上就是在一个带权图中寻找最短路径的过程，这正是我们本章要探讨的核心算法。7.1图的定义和术语图的定义(Graph)图是用于表示多对多关系的非线性数据结构，形式化表示为G=(V,E)。其中V是顶点的集合，E是边的集合。顶点(Vertex/Node)图的基本构成单元，表示实体或对象。例如在交通网络中代表城市，在社交网络中代表用户。边(Edge)表示顶点之间的关系，记为(v,w)或<v,w>。例如道路连接城市，好友关系连接用户。邻接点与关联边邻接点：若顶点v和w之间存在边，则称v和w互为邻接点。关联边：边e与顶点v和w相关联。无向图vs有向图无向图(UndirectedGraph)定义：边没有方向，表示双向关系。示例：社交网络中的好友关系（A是B的好友，B也是A的好友）。表示：边记为(v,w)。有向图(DirectedGraph)定义：边有方向，表示单向关系。示例：网页间的超链接（从A指向B，B不一定指向A）。表示：边记为<v,w>。有权图vs无权图无权图(UnweightedGraph)边仅表示关系的存在，没有附加信息。可以认为边的权重为1，仅关注节点间的连通性。有权图(WeightedGraph/Network)边带有附加的数值信息（权重/Weight），表示关系的强度、成本或距离。例如：交通网络中道路的长度或通行时间。稠密图vs稀疏图稀疏图(SparseGraph)边数远小于最大可能边数的图。顶点之间连接较为松散。无向完全图(Undirected)一种特殊的稠密图。任意两个顶点之间都存在边，连接最紧密。有向完全图(Directed)任意两个顶点之间都存在两条方向相反的边，边数达到最大值。无向图的基本术语度(Degree)顶点v的度是与v相关联的边的数目，记为D(v)。它反映了顶点的连接紧密程度。路径(Path)从顶点v到顶点w的顶点序列，相邻顶点间有边相连。路径长度是边的数目。无向图的基本术语连通图(ConnectedGraph)图中任意两个顶点之间都存在路径，意味着整个图是一个整体，没有孤立的部分。生成树(SpanningTree)连通图的极小连通子图，包含所有顶点和n-1条边（n为顶点数），无环结构。有向图的基本术语顶点的度(Degree)入度(In-degree)以顶点v为终点的边的数目，记为ID(v)。出度(Out-degree)以顶点v为起点的边的数目，记为OD(v)。总度(TotalDegree)D(v)=ID(v)+OD(v)。强连通图(StronglyConnected)定义有向图中任意两个顶点v和w之间，既存在从v到w的路径，也存在从w到v的路径。图的基本术语7.1.2图的基本操作结构的建立和销毁CreateGraph:创建图结构DestroyGraph:销毁图结构对顶点的访问操作LocateVex/GetVex:查找顶点PutVex:修改顶点信息对邻接点的操作FirstAdjVex:求第一个邻接点NextAdjVex:求下一个邻接点插入或删除顶点InsertVex:插入顶点DeleteVex:删除顶点插入和删除边InsertArc:插入边(弧)DeleteArc:删除边(弧)图的遍历操作DFSTraverse:深度优先遍历BFSTraverse:广度优先遍历7.2图的存储-邻接矩阵核心概念定义基本思想：使用二维数组（矩阵）来表示图中顶点间的邻接关系。矩阵结构：矩阵的行和列都对应顶点。元素含义：arcs[i][j]的值表示顶点i和顶点j之间是否有边以及边的权重。C语言结构定义实现//最大顶点数与边结构体定义#defineMAX_VERTEX_NUM20typedefstructArcCell{intadj;//边权值或相邻标志InfoType*info;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的邻接矩阵存储结构typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;}MGraph;7.2图的存储-邻接矩阵核心概念定义基本思想：使用二维数组（矩阵）来表示图中顶点间的邻接关系。矩阵结构：矩阵的行和列都对应顶点。元素含义：arcs[i][j]的值表示顶点i和顶点j之间是否有边以及边的权重。C语言结构定义实现//最大顶点数与边结构体定义#defineMAX_VERTEX_NUM20typedefstructArcCell{intadj;//边权值或相邻标志InfoType*info;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的邻接矩阵存储结构typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;}MGraph;邻接矩阵示例无向无权图(a)特点：矩阵对称，arcs[i][j]=1表示有边，0表示无边。有向无权图(b)特点：矩阵不一定对称，arcs[i][j]=1表示有从i到j的边。无向有权图(c)特点：矩阵对称，arcs[i][j]存储权重，无边则为∞。有向有权图(d)特点：矩阵不一定对称，arcs[i][j]存储权重，无边则为∞。算法7-3：构造图的邻接矩阵表示(1)核心代码：CreateGraph函数StatusCreateGraph(MGraph&G){//采用数组（邻接矩阵）表示法，构造图Gscanf(&G.kind);switch(G.kind){caseDG:returnCreateDG(G);//构造有向图GcaseDN:returnCreateDN(G);//构造有向网GcaseUDG:returnCreateUDG(G);//构造无向图GcaseUDN:returnCreateUDN(G);//构造无向网Gdefault:returnERROR;}}核心逻辑：根据图的类型（DG/DN/UDG/UDN），通过switch-case语句动态调用对应的创建函数。算法7-3：构造图的邻接矩阵表示(2)CreateUDN函数实现(C语言)StatusCreateUDN(MGraph&G){//采用数组（邻接矩阵）表示法，构造无向网scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//构造顶点向量for(inti=0;i<G.vexnum;++i){scanf("%s",&G.vexs[i]);}//初始化邻接矩阵为无穷大for(inti=0;i<G.vexnum;++i)for(intj=0;j<G.vexnum;++j)G.arcs[i][j].adj=INFINITY;for(intk=0;k<G.arcnum;++k){//输入边信息并填充矩阵VertexTypev1,v2;intw;scanf("%s%s%d",&v1,&v2,&w);inti=LocateVex(G,v1),j=LocateVex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i]=G.arcs[i][j];//关键：无向图的对称性}returnOK;}邻接矩阵的优缺点分析核心优势(Advantages)查找快速判断两点是否有边或获取权重，时间复杂度为O(1)。实现简单基于二维数组结构，逻辑直观，易于编程实现和理解。适合稠密图对于边数接近顶点数平方的稠密图，空间利用率较高。主要局限(Disadvantages)空间复杂度高空间复杂度为O(n²)，对于稀疏图会浪费大量存储空间。插入删除困难插入或删除顶点需要重构整个矩阵，操作成本较高。7.2.2图的存储-邻接表邻接表定义为每个顶点建立一个单链表，链表节点表示邻接顶点及边信息。整个图由顶点数组和若干邻接链表组成，适用于稀疏图存储。结构示意图C语言实现代码typedefstructArcNode{//边节点结构定义intadjvex;//邻接点索引structArcNode*nextarc;//指向下一条边}ArcNode;typedefstructVNode{//顶点结构定义VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一个边节点}VNode;typedefstruct{//图结构定义VNodeadjlist[MAX_V];//顶点数组intvexnum,arcnum;//顶点数和边数}ALGraph;邻接表示例构建原理与特点基本结构：以一个简单的无向图为例，图中的每个顶点作为链表的头节点，其后链接的是所有与其直接相连的顶点。存储优势：相比邻接矩阵，邻接表更节省空间，尤其适合存储边数较少的稀疏图（SparseGraph）。查询效率：查找特定顶点的所有邻居非常高效，但判断两个顶点是否相连则需要遍历链表。算法：构造图的邻接表表示核心构建步骤1.初始化顶点数组读取顶点数和边数，初始化每个顶点的邻接表头指针为NULL。2.创建并插入边节点逐条读取边信息，定位顶点位置，动态分配边节点并插入到链表头部。3.无向图双向插入对于无向图，同一条边需在两个顶点的邻接表中各插入一次，确保图的对称性。C语言实现代码(CreateUDG)for(inti=0;i<G.vexnum;++i){//初始化顶点数组scanf("%s",&G.adjlist[i].data);G.adjlist[i].firstarc=NULL;}for(intk=0;k<G.arcnum;++k){//逐条输入边信息并插入inti=LocateVex(G,v1),j=LocateVex(G,v2);//插入到v1的邻接表ArcNode*p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.adjlist[i].firstarc;G.adjlist[i].firstarc=p;//无向图：插入到v2的邻接表p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=G.adjlist[j].firstarc;G.adjlist[j].firstarc=p;}邻接表的优缺点分析核心优势空间效率高空间复杂度为O(n+e)，避免了邻接矩阵的空间浪费，非常适合稀疏图。便于增删顶点插入或删除顶点操作相对容易，仅需调整顶点数组和相关链表指针。便于遍历邻接点遍历一个顶点的所有邻接点非常方便，直接遍历其对应的链表即可。局限性与挑战查找边效率低判断两点间是否有边需遍历链表，时间复杂度为O(n)，不如矩阵查找迅速。实现相对复杂涉及链表的动态内存分配和指针操作，代码实现比邻接矩阵稍显复杂。十字链表ABDCEF十字链表ABCDEF0123451305430125

212343

顶点firstinfirstout

弧尾

弧头tlink

hlink

十字链表typedefintStatus;typedefintVertexType;typedefintInfoType;structArcBox{//边的结构表示inttailvex,headvex;//该边尾和头顶点的位置ArcBox*hlink,*tlink;//分别指向弧头顶点和弧尾顶点的下一条弧InfoType*info;//该边相关信息的指针};structVexNode{//顶点的结构表示VertexTypedata;//顶点信息ArcBox*firstin,*firstout;//分别指向该顶点的第一条入边和出边};structOLGraph{//有向图的结构表示VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)intvexnum,arcnum;//有向图的当前顶点数和弧数};十字链表intLocateVex(OLGraph&G,VertexTypev){//定位顶点for(inti=0;i<G.vexnum;++i){if(G.xlist[i].data==v){returni;}}return-1;//如果未找到，返回-1}voidInput(InfoType&info){//输入边的信息cin>>info;//示例输入，根据实际需求修改}StatusCreateDG(OLGraph&G){//创建有向图cin>>G.vexnum>>G.arcnum;for(inti=0;i<G.vexnum;++i){ cin>>G.xlist[i].data;G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;}十字链表for(intk=0;k<G.arcnum;++k){VertexTypev1,v2;cin>>v1>>v2;inti=LocateVex(G,v1);intj=LocateVex(G,v2);if(i==-1||j==-1){cerr<<"Vertexnotfound!"<<endl;returnERROR;}ArcBox*p=newArcBox;p->tailvex=i;p->headvex=j;p->hlink=G.xlist[j].firstin;//指向j顶点原第一条入边p->tlink=G.xlist[i].firstout;//指向i顶点原第一条出边p->info=NULL;G.xlist[j].firstin=p;//更新j顶点的入边链表G.xlist[i].firstout=p;//更新i顶点的出边链表//如果需要输入边的信息，取消以下注释//Input(*p->info);}returnOK;}邻接多重表

邻接多重表是无向图的另一种链式存储结构。

边的结点结构

mark

ivexilink

jvex

jlink

info其中：Mark为标志域；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边；info为指向和边相关的各种信息的指针域。邻接多重表邻接多重表typedefstructEbox{ VisitIfmark;//访问标记 intivex,jvex;//该边依附的两个顶点的位置 structEBox*ilink,*jlink;//分别指向依附这两个顶点的下一条边 InfoType*info;//该边信息指针}EBox;typedefstructVexBox{ VertexTypedata; EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstruct{//邻接多重表 VexBoxadjmulist[MAX_VERTEX_NUM]; intvexnum,edgenum;//无向图的当前顶点数和边数 }AMLGraph;7.3图的遍历-深度优先搜索(DFS)DFS基本思想核心策略：“先走到底，再回头”。从起始顶点出发，尽可能深地探索路径。递归过程：访问一个邻接顶点，然后以该顶点为新起点，递归进行搜索。回溯机制：当一个顶点的所有邻接顶点都被访问过时，回溯到上一个顶点，继续访问其他未访问分支。核心实现机制数据结构：通常利用递归调用栈（系统栈）或显式使用栈（Stack）数据结构来实现。算法特征：体现了“深度”优先的策略，优先纵向深入探索，而非横向铺开。关键操作：标记已访问的顶点，避免重复访问，确保每个顶点仅被访问一次。DFS算法动态演示(1)第一步：访问起始顶点选择起点：选择图中的任意一个顶点作为遍历的起始点（例如顶点A）。标记状态：将该顶点标记为“已访问”，避免后续重复访问。输出结果：将该顶点加入结果序列，完成第一步操作。DFS算法动态演示(2)第二步：递归访问邻接顶点起始与访问：从起始顶点A出发，访问其第一个未访问的邻接顶点（如顶点B），标记为已访问并输出。递归深入：以B为新的起点，递归地重复此过程，继续访问B的邻接顶点，体现“深度优先”的核心思想。DFS算法动态演示(3)第三步：回溯过程(Backtracking)终止条件：当访问到顶点（如顶点D）且其所有邻接顶点都已被访问时，无法再继续深入。回溯操作：递归函数返回，回到上一个顶点（如顶点B），继续寻找未访问的分支。循环直至完成：重复“深入-回溯”的过程，直到图中所有顶点都被访问完毕。DFS算法动态演示(3)DFS算法实现代码算法核心逻辑访问标记数组

使用布尔数组`visited`记录顶点状态，避免重复访问。深度优先递归

从起点出发，沿着一条路径尽可能深地探索，直到尽头再回溯。邻接矩阵遍历

通过双重循环检查矩阵中的邻接关系(`G.arcs[v][w].adj==1`)。非连通图处理

`DFSTraverse`函数确保所有连通分量都被访问。C语言实现代码//图的种类：有向图、有向网、无向图、无向网typedefenum{DG,DN,UDG,UDN}GraphKind;structArcCell{

//边的定义

intadj;

//顶点关系类型，无权图用1或0表示相邻否，有权图为权值

InfoType*info;

//该边相关信息的指针，如边权};//邻接矩阵typedefArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

DFS算法实现代码typedefstruct{

//图的结构定义VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;

//邻接矩阵intvexnum,arcnum;

//图的当前顶点数和边数GraphKindkind;

//图的种类标志}MGraph,Graph;boolvisited[MAX_VERTEX_NUM];

//访问标志数StatusVisit(intv){//访问函数cout<<"Visitedvertex:"<<v<<endl;returnOK;}DFS算法实现代码intFirstAdjVex(constGraph&G,intv){//获取第一个邻接顶点for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni;}}return-1;//没有邻接顶点}intNextAdjVex(constGraph&G,intv,intw){//获取下一个邻接顶点for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni;}}return-1;//没有下一个邻接顶点}DFS算法实现代码voidDFS(Graph&G,intv){//深度优先搜索visited[v]=TRUE;//标记为已访问Visit(v);//访问第v个顶点for(intw=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)){if(!visited[w]){DFS(G,w);//对v的尚未访问的邻接顶点，递归调用DFS}}}voidDFSTraverse(Graph&G,Status(*Visit)(intv)){//深度优先搜索遍历memset(visited,FALSE,sizeof(visited));//初始化访问标志数组for(intv=0;v<G.vexnum;++v){if(!visited[v]){DFS(G,v);//对尚未访问的顶点调用DFS}}}7.3图的遍历-广度优先搜索(BFS)BFS基本思想：层层递进，先广后深从起始顶点出发，先访问其所有邻接顶点（第一层），然后依次访问这些邻接顶点的邻接顶点（第二层），以此类推，直到所有顶点都被访问。这种方式如同水面波纹向外扩散。核心实现机制：队列(Queue)利用队列（先进先出）来维护访问顺序，确保先被访问的顶点的邻接顶点优先被处理，完美体现了“广度”优先的策略。BFS算法动态演示(1)第一步：初始化队列与起始顶点选择起始顶点选定图中的起始节点（如顶点A）作为遍历的起点。标记访问状态将起始顶点标记为“已访问”，避免后续重复处理。入队操作将已访问的起始顶点加入队列，作为后续处理的依据。BFS初始状态示意图BFS算法动态演示(2)第二步：出队与邻接访问1.队首出队将队列头部的顶点（A）取出，作为当前访问节点。2.访问邻接顶点遍历当前节点（A）的所有未访问邻接点（B,C），标记为已访问。3.新节点入队将新发现的邻接点（B,C）依次加入队列尾部，等待下一层处理。队列操作示意图BFS算法动态演示(3)第三步：循环遍历与队列操作核心操作：重复第二步，依次将队首顶点出队，访问其所有未访问的邻接顶点，标记并入队。终止条件：直到队列为空，所有顶点都被访问。算法特点：最终的访问顺序体现了“层次遍历”的特点，即由近及远地访问图中的节点。BFS算法动态演示BFS算法实现代码（邻接矩阵）核心实现代码(C语言)核心逻辑解析队列管理机制使用数组模拟队列，通过front和rear指针实现先进先出（FIFO），确保访问顺序。访问标记数组visited[]数组记录节点状态，防止重复访问，避免死循环。广度优先遍历循环取出队首节点，遍历其所有邻接点，将未访问的邻接点入队，层层向外扩展。intFirstAdjVex(constGraph&G,intv){//获取第一个邻接顶点for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni;}}return-1;//没有邻接顶点}intNextAdjVex(constGraph&G,intv,intw){

//获取下一个邻接顶点for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni;}}return-1;//没有下一个邻接顶点}BFS算法实现代码voidBFSTraverse(Graph&G,Status(*Visit)(intv)){//广度优先搜索遍历memset(visited,FALSE,sizeof(visited));//初始化访问标志queue<int>Q;

//辅助队列for(intv=0;v<G.vexnum;++v){if(!visited[v]){

//尚未访问Q.push(v);

//入队列

visited[v]=TRUE;

//标记为已访问

Visit(v);

//访问while(!Q.empty()){intu=Q.front();

//队头元素

Q.pop();

//出队for(intw=FirstAdjVex(G,u);w!=-1;w=NextAdjVex(G,u,w)){if(!visited[w]){

//为u的尚未访问的邻接顶点visited[w]=TRUE;

//标记为已访问

Visit(w);

//访问

Q.push(w);

//入队列}}}}}7.4图的应用-无向图的连通分量和生成树对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。深度优先生成树/森林广度优先生成树/森林7.4图的应用-无向图的连通分量和生成树无向图的连通分量和生成树Typedefstruct{…}//图的结构定义//见邻接矩阵定义typedefstructCSNode{//孩子-兄弟链表的节点定义VertexTypedata;//顶点信息structCSNode*firstchild;//指向第一个孩子structCSNode*nextsibling;//指向下一个兄弟}CSNode,*CSTree;boolvisited[MAX_VERTEX_NUM];//访问标志数组intFirstAdjVex(constGraph&G,intv){//获取第一个邻接顶点for(inti=0;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni；}return-1;//没有邻接顶点}intNextAdjVex(constGraph&G,intv,intw){//获取下一个邻接顶点for(inti=w+1;i<G.vexnum;++i){if(G.arcs[v][i].adj!=0){//如果存在边returni;}}return-1;//没有下一个邻接顶点}无向图的连通分量和生成树voidDFSTree(Graph&G,intv,CSTree&p){//深度优先搜索生成树visited[v]=TRUE;//标记为已访问for(intw=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)){if(!visited[w]){//如果w未被访问CSTrees=(CSTree)malloc(sizeof(CSNode));//创建新节点s->data=G.vexs[w];//设置顶点信息s->firstchild=NULL;s->nextsibling=NULL;if(p->firstchild==NULL){//如果p没有孩子p->firstchild=s;//设置s为p的第一个孩子}else{//如果p已经有孩子CSTreeq=p->firstchild;while(q->nextsibling!=NULL){//找到最后一个兄弟q=q->nextsibling;}q->nextsibling=s;//将s添加为最后一个兄弟} DFSTree(G,w,s);//递归生成以w为根的子树 } }}无向图的连通分量和生成树voidDFSForest(Graph&G,CSTree&T){//深度优先生成森林T=NULL;//初始化森林为空memset(visited,FALSE,sizeof(visited));//初始化访问标志数组CSTreeq=NULL;//q用于指向当前生成树的根for(intv=0;v<G.vexnum;++v){if(!visited[v]){//如果v未被访问CSTreep=(CSTree)malloc(sizeof(CSNode));//创建新节点p->data=G.vexs[v];//设置顶点信息p->firstchild=NULL;p->nextsibling=NULL;if(!T){//如果是第一棵生成树T=p;//设置T为第一棵生成树的根

}else{//如果不是第一棵生成树q->nextsibling=p;//将p设置为前一棵生成树的兄弟} q=p;//更新q为当前生成树的根DFSTree(G,v,p);//生成以p为根的生成树}}}7.4图的应用-有向图的强连通分量取图中任意一个顶点u作为起始点进行DFS，当DFS当前访问的顶点v不存在任何一条边e，e=<v,v'>，v'为未访问过的顶点时，顶点v就是一个强连通分量；当DFS当前访问的顶点v存在一条边e，e=<v,v'>，顶点v'为已经访问的顶点且还未访问完成的顶点（存在一个从顶点v到顶点v'的回路）时，顶点v到顶点v'所在路径（DFS过程中）中的顶点都在一个强连通分支中，该顶点集合记为V'，再验证其他顶点u，是否存在顶点x∈V'，边<u,x>∈E，并且存在顶点x'∈V'，边<x',u>∈E。若存在，则将顶点u也加入到强连通分量V'中；若不存在，则V'就是一个强连通分量。从图G中去除V'中的顶点以及与V'中的顶点相关联的边，再次进行DFS求取下一个强连通分量，直至图G中不存在任何顶点。7.4图的应用-最小生成树(MST)问题定义在一个连通的带权无向图中，寻找一个包含所有顶点的无环子图（树），使得所有边的权重之和最小。这个子图即为最小生成树(MinimumSpanningTree)。应用场景广泛应用于网络布线、道路建设、电路设计等领域。核心目标是在保证所有节点连通的前提下，使用最小的成本（如距离、费用、时间）构建连接网络。7.4图的应用-最小生成树(MST)ABDCEF32234413ABDCEF22313最小生成树，权重之和为11ABDCEF32413不是最小生成树，权重之和为13不是最小生成树，存在回路ABDCEF32231Prim算法算法核心思想1.初始化起点生成树初始状态仅包含一个起始顶点，随后逐步扩展。2.贪心选择最小边每次从“已加入顶点”和“未加入顶点”之间，选择权值最小的边。3.扩展与终止将选中的边对应的顶点加入生成树，重复此过程直到所有顶点都被包含。Prim算法动态演示(1)第一步：初始化与起点选择选择起始顶点：选择任意顶点（如顶点A），将其加入生成树的顶点集合U。初始化lowcost数组：创建数组lowcost，其中lowcost[v]表示顶点v到集合U的最小权值边的权重。初始时，只有起点的权值为0，其余为无穷大。Prim算法动态演示(2)核心步骤解析：贪心选择与更新1.贪心选择顶点在未加入集合U的顶点中，找到lowcost值最小的顶点v，将其加入U，并将对应的最小权值边加入生成树。2.更新lowcost数组遍历新顶点v的所有邻接顶点w。若w未加入U且边(v,w)的权值小于lowcost[w]，则更新lowcost[w]为该边权值，确保始终记录连接生成树的最短路径。Prim算法动态演示(3)第三步：完成最小生成树迭代过程：重复第二步的贪心策略，每次选择权值最小的边，将新的顶点加入集合U。终止条件：当所有顶点都被加入到集合U中时，算法结束。最终结果：此时被选中的边构成了图的最小生成树(MST)，它连接了所有顶点且总权重最小。Prim算法动态演示(3)Prim算法实现代码核心思想与数据结构lowcost数组记录图中各顶点到生成树集合的最小边权值。visited数组标记顶点是否已被加入到最小生成树中。算法步骤1.初始化距离数组。2.循环选择最近顶点并入树。3.更新剩余顶点的距离。C语言实现代码struct{//图的邻接矩阵定义最小生成树的辅助数组VertexTypeadjvex;

//u到v的最小权值边的顶点VRTypelowcost;

//边的权值}closedge[MAX_VERTEX_NUM];intLocateVex(Graph&G,VertexTypeu){

//定位顶点for(inti=0;i<G.vexnum;++i){if(G.vexs[i]==u){returni;}}return-1;//未找到}Prim算法实现代码C语言实现代码intminimum(Graph&G){

//寻找最小代价边的顶点intmin=INT_MAX;intk=-1;for(inti=0;i<G.vexnum;++i){if(closedge[i].lowcost!=0&&closedge[i].lowcost<min){min=closedge[i].lowcost;k=i;}}returnk;}Prim算法实现代码C语言实现代码voidMiniSpanTree_P(Graph&G,VertexTypeu){//普里姆算法intk=LocateVex(G,u);//找到起始顶点u的位置for(int