数据结构与算法 课件全套 机械自考版 第1--8章 绪论、 线性表---查找.ppt

克鲁斯卡尔算法设E1的初值：E1=Φ，T中只含有图中的所有顶点，顶点个数为n=|V|当E1中边数小于n-1时，重复执行下面的步骤在图G的边集E中选择权值最小的边(u,v)，并从E中删除它如果u和v分别属于T中不同的连通分量，则将边(u,v)加入到E1中去，否则丢掉该边，选择E中的下一条权值最小的边边权值(6,8)2(7,8)2(5,8)3(1,3)4(3,4)5(4,7)5(1,4)6(1,2)6(3,7)6(2,5)7(2,6)7(5,6)10(4,5)14程序克鲁斯卡尔算法中，从|E|条边中选出权值最小的边(u,v)，并检测u和v是不是在同一连通分量上，时间花费为O(|E|log|E|)。所以，克鲁斯卡尔算法适宜求稀疏图的最小生成树第六节有向无环图及其应用图中不存在回路的有向图称为有向无环图（directedacyclinegraph），简称为DAG图比如，表达式树可表示为DAG图拓扑排序有向无环图G=(V,E)的拓扑序列是G中顶点的一个线性序列，并且满足以下关系：对于图G中的所有顶点v和w，如果(v,w)∈E，则在线性序列中v排在w之前求有向无环图拓扑序列的过程称为拓扑排序在有向图中，以顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网络（activityonvertexnetwork），简称为AOV网在AOV网中，若从顶点vi到vj有一条有向路径，则称vi是vj的前驱，vj是vi的后继若(vi,vj)是AOV网中的一条弧，则称vi是vj的直接前驱，vj是vi的直接后继如果vi是vj的前驱或直接前驱，则vi活动必须在vj活动开始之前结束，即vj活动必须在vi活动结束之后才能开始在AOV网中不允许出现回路，因此AOV网必是有向无环图邻接表邻接表表结点的结构对于带权图，可以扩展邻接表的结构，在单链表的每个表结点中增加一个域，用来存储两个顶点间这条边的权表结点结构对于有向图，如果将所有有向弧的方向转向，则得到的新图的邻接表称为原图的逆邻接表例6-8无向图的邻接表有向图的邻接表和逆邻接表用邻接表表示有n个顶点和e条边的无向图时，需要一个由n个元素组成的顺序表（表头结点表）和由总共2e个结点组成的n个单链表表示有n个顶点e条弧的有向图时，需要一个由n个元素组成的顺序表和由总共e个结点组成的n个单链表邻接表的空间复杂度为O(n+e)当图中顶点个数经常变化时，为便于顶点的插入和删除，也可以将图的全部顶点保存在一个单链表中，而不是一维数组中。单链表中的结点结构如下所示指向下一顶点的指针指向邻接点表的指针顶点信息第三节图基本操作的实现采用邻接矩阵存储的图的定义顶点表的相应查询查询边的权值创建图创建无向图创建有向带权图验证图构建函数的正确性找到某顶点的第一个邻接点查找下一个邻接点获取顶点个数及边数intgetNumVertices(MGraphg){ returng.numVertices;}intgetNumEdges(MGraphg){ returng.numEdges;}第四节图的遍历定义6-1给定一个连通图G=(V,E)，从图中的某个顶点出发，经过一定的路线访问图中的所有顶点，使每个顶点被访问且只访问一次，这一过程称为图的遍历深度优先有哪些信誉好的足球投注网站（depthfirstsearch,DFS）遍历广度优先有哪些信誉好的足球投注网站（breadthfirstsearch,BFS）遍历深度优先有哪些信誉好的足球投注网站选择图中任意指定顶点为起始顶点，将其设为当前顶；访问当前顶点v，输出关于v的相关信息将v的访问标志置为VISITED如果v的邻接点中存在未被访问的顶点w，则将w设为当前顶点，转②继续；否则转⑤回退到最近被访问过的且仍有未被访问邻接点的顶点u，转④继续；不能回退时，转⑥如果所有顶点均已访问，则遍历结束，否则，选择未被访问的另一个顶点作为起始顶点，继续上述过程v0,v1,v3,v7,v4,v5,v2,v6DFS算法当图是连通图时，使用DFS算法从某个顶点出发，可以访问到图中的所有顶点。如果图不连通，则一次调用DFS不能访问图中的全部顶点，只能访问初始顶点所在的连通分量中的所有顶点广度优先有哪些信誉好的足球投注网站选择图中指定的顶点v为起始顶点，将其入队列，且其访问标志置为VISITED队列为空时，转⑤；队列不为空时，出队列，设出队列的顶点为w输出关于w的相关信息找到与顶点w相邻接的且访问标志不是VISITED的顶点序列w1,w2,…,wk，依次入队列，转②如果所有顶点均已访问，则遍历结束，否则，选择未被访问的一个顶点作为