数据基础及结构 9

第七章图数据结构与算法中国海洋大学本章目录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(intj=0;j<G.vexnum;++j){if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;//初始，U={u}for(inti=1;i<G.vexnum;++i){k=minimum(G);//求出加入生成树的下一个顶点(k)if(k==-1)break;//如果没有找到最小边，退出循环cout<<closedge[k].adjvex<<""<<G.vexs[k]<<endl;//输出生成树上一条边closedge[k].lowcost=0;//第k顶点并入U集Prim算法实现代码C语言实现代码for(intj=0;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;}}}}}Prim算法时间复杂性

Kruskal算法算法核心思想排序边权：将图中所有边按权值从小到大排序。贪心选边：依次选择权值最小的边，若该边连接两个不同的连通分量，则加入生成树。终止条件：重复上述过程，直到生成树包含n-1条边（n为顶点数）。关键数据结构并查集(Union-Find)：用于高效判断两个顶点是否属于同一连通分量，以及合并两个连通分量。作用：避免生成环，保证算法的正确性和高效性。Kruskal算法动态演示(1)第一步：边排序核心思想：将图中所有的边按照权值从小到大进行排序。这是构建最小生成树的基础步骤，确保我们总是优先选择权值最小的边。操作步骤：收集图中所有的边依据边的权重进行升序排列生成排序后的边列表算法初始状态示意图Kruskal算法动态演示(2)核心步骤：选边与合并1.贪心选边从排序后的边列表中，依次取出权值最小的边。2.连通性检查(Find)利用并查集的Find操作，检查该边的两个顶点是否属于同一个连通分量。3.合并集合(Union)若不属于同一分量，则将该边加入生成树，并执行Union操作合并两个连通分量。算法执行过程示意图Kruskal算法动态演示(3)第三步：算法终止条件重复执行第二步（选择最小权边并判断环），直到生成树中包含了n-1条边（其中n为图的顶点总数）。此时，所有顶点都已连通，算法结束，成功构造出最小生成树。Kruskal算法动态演示(3)Kruskal算法时间复杂性

首先需将所有边按权值从小到大排序，若图中有e条边，排序耗时为O(e×loge)，这是算法的主要时间开销；接着利用并查集结构依次处理每条边，对每条边执行两次查找操作（判断两顶点所属连通分量）和一次合并操作（若顶点分属不同分量），并查集在路径压缩和按秩合并优化下，单次操作近乎常数时间，总处理边的时间为O(e×α(e))，其中α为阿克曼函数的反函数，可视为常数。因此，算法总时间复杂度为O(e×loge+e×α(e))，近似为O(e×loge)，该复杂度与顶点数n无关，仅由边数e决定，排序步骤的时间复杂度主导了整体效率，体现了克鲁斯卡尔算法在稀疏图中求解最小生成树的高效性。7.4图的应用-拓扑排序问题定义对一个有向无环图（DAG）的顶点进行排序，使得对于图中每一条有向边<u,v>，顶点u在排序中都出现在顶点v之前。应用场景广泛应用于任务调度、课程安排、项目管理等领域。其核心价值在于确定具有依赖关系的任务的执行顺序，确保前置条件满足后再执行后续任务。拓扑排序（Kahn算法）初始化与准备计算所有顶点的入度，构建入度表。将所有入度为0的顶点加入队列。核心处理循环取出队首顶点u，将其加入拓扑序列。遍历u的邻接顶点v，将v的入度减1。条件判断与循环若v的入度变为0，则将v加入队列。重复上述过程，直到队列为空。结果验证若拓扑序列包含所有顶点，则排序成功。否则，说明图中存在环，无法排序。拓扑排序动态演示(1)第一步：初始化与入队计算入度：遍历图中所有顶点，统计每个顶点的入度（即有多少条边指向它）。寻找起点：找出所有入度为0的顶点，这些顶点没有前驱任务，是拓扑排序的起点。加入队列：将入度为0的顶点（如顶点A和顶点B）加入到队列中，准备开始处理。图示：拓扑排序初始状态，入度为0的顶点已入队拓扑排序动态演示(2)第二步：处理顶点与更新入度1.取出顶点并加入序列从队列中取出顶点A，将其加入拓扑序列中。2.遍历邻接顶点遍历A的所有邻接顶点（C和D），将它们的入度减1。3.检查并更新队列若邻接顶点入度变为0（如顶点C），则将其加入队列。图示：拓扑排序执行过程中的第二步状态拓扑排序动态演示(2)Kahn算法实现代码C语言实现代码structGraph{//图的结构定义intvexnum,arcnum;

//顶点数和边数vector<vector<int>>adjList;

//邻接表vector<int>inDegree;

//每个顶点的入度};voidInitGraph(Graph&G,intvexnum){//初始化图G.vexnum=vexnum;G.adjList.resize(vexnum);G.inDegree.resize(vexnum,0);}Kahn算法实现代码C语言实现代码voidAddEdge(Graph&G,intu,intv){//添加边G.adjList[u].push_back(v);

//添加边u->vG.inDegree[v]++;

//v的入度加1}voidCountInDegree(Graph&G){//计算每个顶点的入度for(inti=0;i<G.vexnum;++i){for(intj=0;j<G.adjList[i].size();++j){intv=G.adjList[i][j];G.inDegree[v]++;}}}Kahn算法实现代码C语言实现代码voidKahnTopologicalSort(Graph&G){//Kahn算法实现拓扑排序queue<int>Q;

//用于存储入度为零的顶点vector<int>topoOrder;

//存储拓扑排序结果intcount=0;

//计数器，记录已输出的顶点for(inti=0;i<G.vexnum;++i){//将所有入度为零的顶点入队if(G.inDegree[i]==0){Q.push(i);}}Kahn算法实现代码C语言实现代码while(!Q.empty()){intv=Q.front();

//取出队列中的一个顶点Q.pop();topoOrder.push_back(v);

//将该顶点加入拓扑排序结果++count;

//计数器加1for(inti=0;i<G.adjList[v].size();++i){//遍历该顶点的所有邻接顶点intw=G.adjList[v][i];G.inDegree[w]--;

//邻接顶点的入度减1if(G.inDegree[w]==0){Q.push(w);

//如果邻接顶点的入度变为0，入队}}}Kahn算法实现代码C语言实现代码if(count!=G.vexnum){//检查是否所有顶点都被输出cout<<"图中有回路"<<endl;}else{cout<<"拓扑排序结果:";for(inti=0;i<topoOrder.size();++i){cout<<topoOrder[i]<<"";}cout<<endl;}}7.4图的应用-关键路径问题:

假设以有向网表示一个施工流图，其中，顶点表示事件，弧表示活动，弧上的权值表示活动的持续时间。该网络称之为AOE网络。

假设以该AOE网络表示一个施工流图，则有待研究的问题是：（1）完成整项工程至少需要多少时间？（2）哪些工程是影响整个工程进度的关键？7.4图的应用-关键路径“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。整个工程完成的时间为：从有向图的源点到汇点的最长路径。7.4图的应用-关键路径

如何求关键活动？“事件(顶点)”的最早发生时间ve(j)ve(j)=从源点到顶点Vj的最长路径长度；

这个时间决定了所有以Vj为尾的弧所表示的活动的最早开始时间

“事件(顶点)”的最迟发生时间vl(k)，表示在不推迟整个工程完成的前提下，事件最迟发生的时间。vl(k)=工程完成时间-从顶点Vk到汇点的最长路径长度。7.4图的应用-关键路径

事件发生时间的计算公式：

ve(源点)=0；ve(k)=Max{ve(j)+dut(<j,k>)}vl(汇点)=ve(汇点)；vl(j)=Min{vl(k)–dut(<j,k>)}{{j1j2j3kve(k)=maxve(j)dutjk2dutk1k3vl(j)=minvl(k)7.4图的应用-最短路径问题定义在带权图中，找到从一个顶点（源点）到另一个顶点（终点）的路径，使得路径上所有边的权重之和最小。算法分类单源最短路径从一个源点到其他所有顶点的最短路径。多源最短路径求所有顶点对之间的最短路径。应用场景交通路线规划（如地图导航）网络路由选择（数据传输路径）任务调度与资源分配Dijkstra算法算法核心思想适用场景与策略用于求解单源最短路径问题（要求边权非负）。采用贪心策略，每次从未确定最短路径的顶点中，选择距离源点最近的顶点。松弛操作(Relaxation)将选中的顶点加入已确定集合，以该顶点为中间点，尝试更新所有从源点经过该点到其邻接顶点的距离，寻找更短路径。迭代终止条件重复上述选择与松弛过程，直到所有顶点都被处理完毕，此时即可得到源点到所有其他顶点的最短路径。Dijkstra算法动态演示(1)第一步：初始化(Initialization)距离数组dist[]初始化源点距离为0，其他所有顶点距离设为无穷大(∞)，表示初始状态下仅能确定源点位置。已确定顶点集合S用于存放已找到最短路径的顶点。算法开始时，S为空集，随着迭代逐步加入顶点。核心步骤：选择顶点与松弛操作1.选择最近顶点在未加入集合S的顶点中，找到距离源点最近的顶点u，并将其加入S。2.执行松弛操作遍历u的所有邻接顶点v，若通过u到达v的路径更短，则更新v的最短距离：ifdist[v]>dist[u]+weight(u,v)Dijkstra算法动态演示(3)第三步：最终收敛与结果循环终止条件：重复第二步操作，直到所有顶点都被加入集合S。最终结果：此时，距离数组dist中存储的就是源点到所有顶点的最短路径长度。图示：Dijkstra算法完成状态示意图Dijkstra算法动态演示Dijkstra算法动态演示Dijkstra算法实现代码structArcCell{//边的定义VRTypeadj;

//顶点关系类型，无权图用1或0表示相邻否，有权图为权值};typedefArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵typedefstruct{//图的结构定义VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;

//邻接矩阵intvexnum,arcnum;

//图的当前顶点数和边数}MGraph,Graph;Dijkstra算法实现代码voidShortestPath_DIJ(Graph&G,intv0,vector<vector<bool>>&P,vector<int>&D){//迪杰斯特拉算法vector<bool>final(G.vexnum,false);//标记是否已找到最短路径D.resize(G.vexnum,INFINITY);

//初始化最短路径表P.resize(G.vexnum,vector<bool>(G.vexnum,false));//初始化路径矩阵for(intv=0;v<G.vexnum;++v){D[v]=G.arcs[v0][v].adj;

//初始化最短路径表 if(D[v]<INFINITY){ P[v][v0]=true;

//路径包含v0P[v][v]=true;//路径包含自身 }}D[v0]=0;

//起始点到自身的距离为0final[v0]=true;

//起始点已确定最短路径Dijkstra算法实现代码for(inti=1;i<G.vexnum;++i){

//其余G.vexnum-1个顶点intmin=INFINITY;intu=-1;for(intw=0;w<G.vexnum;++w){if(!final[w]&&D[w]<min){u=w;min=D[w];}}if(u==-1)break;

//如果没有找到下一个顶点，退出循环final[u]=true;

//标记u为已确定最短路径for(intw=0;w<G.vexnum;++w){if(!final[w]&&(min+G.arcs[u][w].adj<D[w])){D[w]=min+G.arcs[u][w].adj;

//更新最短路径for(intk=0;k<G.vexnum;++k){P[w][k]=P[u][k];

//更新路径矩阵}P[w][w]=true;

//路径包含自身}}}}Floyd-Warshall算法算法核心思想基于动态规划思想，通过引入中间顶点k，逐步尝试更新任意两个顶点i和j之间的最短路径。核心在于考虑所有可能的中间节点来松弛路径。适用场景与限制适用于求解多源最短路径问题。算法允许图中存在负权边，但严禁存在负权回路，否则最短路径长度将无意义。状态转移方程通过比较当前已知的最短路径dist[i][j]与经过中间节点k的路径dist[i][k]+dist[k][j]，取较小值作为新的最短路径：dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])Floyd-Warshall算法动态演示第一步：初始化距离矩阵核心操作：将距离矩阵`dist`初始化为图的邻接矩阵。含义解释：`dist[i][j]`表示顶点i到顶点j的初始最短距离，即直达距离。若两点间无直接路径，则记为无穷大(∞)。核心步骤：中间顶点松弛依次将每个顶点k作为中间顶点，检查所有顶点对(i,j)。若通过k中转能缩短路径，则更新距离。松弛操作公式如果dist[i][j]>dist[i][k]+dist[k][j]则更新：dist[i][j]=dist[i][k]+dist[k][j]Floyd-Warshall算法动态演示Floyd-Warshall算法实现代码voidShortestPath_FLOYD(MGraphG,PathMatrix&P,DistancMatrix&D){for(intv=0;v<G.vexnum;++v){for(intw=0;w<G.vexnum;++w){D[v][w]=G.arcs[v][w];for(intu=0;u<G.vexnum;++u){P[v][w][u]=FALSE;}if(D[v][w]<INFINITY){P[v][w][v]=TRUE;P[v][w][w]=TRUE;}}}核心逻辑解析三重循环结构最外层k遍历中间顶点，内层遍历所有顶点对(i,j)，确保所