爱吃甜食

软件技术基础1.3.3图结构图的基本概念图的遍历图的存储图的定义、术语 4.1图的定义和术语 图是由非空的顶点组成的有限集和边的有限集组成。 二元组G=（V，E） V：顶点集合 E：边的集合，即顶点间的关系 图结构中的关系可以是任意的，甚至可以是空集 图是一种对结点的前驱和后继个数不加限制的数据结构图的术语 1）有向图与无向图 由有向边组成的图，称为有向图 有向边以<X，Y>示，又称为弧 X：弧尾 Y：弧头 有向边<X，Y>与<Y，X>不是同一条边 由无向边组成的图，称为无向图 无向边以（X，Y）表示 无向边（X，Y）与（Y，X）是同一条边图的术语 2）权与网 图中边或弧所具有的相关数称为权 一般用于表明从一个顶点到另一个顶点的距离或耗费 带权的图称为网 3）邻接与顶点的度 对于（X，Y）∈E则X，Y互为邻接点 对于<X，Y>∈E则Y是X的邻接结点13图的术语 顶点的度 课堂练习，给出以下顶点的度顶点度为有向图：出度：入度：以该顶点为弧尾的弧数以该顶点为弧头的弧数无向图：顶点的边数总边数＝21∑D（Vi）i=1n和21各顶点度之和＝图的术语 4）路径与回路 路径：图中沿着各条边，从X到Y所经历的顶点序列称为路径 路径：X，b，a，Y 环：第一顶点与最后一个顶点相同的路径称为环 环：X，a，Y，b，X 回路： 序列中不出现重复的路径称为简单路径 有重复的路径称为回路 回路：X，a，b，a，YaXYb图的术语 5）连通、连通图与连通分量 连通：在图中若X与Y之间有路径，则称X，Y是连通的 连通图：任意两个顶点都连通的图称为连通图 没有孤立顶点 连通分量：指无向图中极大连通子图，即有多少个连通子图图的存储邻接矩阵 4.2图的存储 4.2.1邻接矩阵法 （1）给顶点编号 （2）建立邻接（关系）矩阵123412340000101110010110aij表示弧<i，j>1：表示有弧；0:表示无弧任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和图的存储邻接矩阵 4.2.1邻接矩阵法 若边<<顶点2则邻接矩阵为稀疏矩阵。 邻接矩阵的优点：增减边的操作简单 邻接矩阵的缺点： 增减顶点的操作需要搬移大量的元素， 浪费存储空间123412340110101111010110无向图的邻接矩阵是对称的图的存储邻接矩阵的实现 图的邻接矩阵实现typedefstructgraph_m{ elemtypenode[MAXNUM]; intarcs[MAXNUM][MAXNUM];}graph_m;顶点集合边的邻接矩阵二维数组图的存储邻接表 4.2.2邻接表法 一个邻接表由两种结构组成 存放各顶点元素的数组，头结点 各顶点各自的邻接链表，邻接结点3data顶点号元素域邻接链表头指针邻接顶点号下一邻接结点图的存储（课堂练习） 请写出下面这副图的邻接表 1、给顶点编号 2、建立顶点数组 3、建立各顶点的邻接链表 注意，此图为有向图21345图的存储邻接表的实现 邻接表的定义 头结点的定义 邻接结点的定义typedefstructheadnode{ intnode_index; elemtypedata; structadj_node*next_adj;}headnode;typedefstructadj_node{ intnode_index; structadj_node*next_adj;}adj_node;图的存储邻接表 图邻接表的定义typedefstructgraph_l{ headnodenode_list[MAXNUM]; intnode_num;}graph_l;图的存储邻接表21432143注意：有向图与无向图的区别图的存储 图的邻接表存储法的特点 优点 节省存储空间 边的插入和删除操作比较简便 缺点 结构复杂 具有两种不同的基本组成单元图的存储 4.2.3边带权值的图的存储 1）在邻接矩阵中的实现0235 010 1015010a[4][4]=a[i][j]：记录边的权值；为0表示无边23511图的存储 4.2.3边带权值的图的存储 2）在邻接表中的实现 在邻接结点结构中增加一个权值域顶点号边权值124332511103图的遍历 4.3图的遍历 问： 1、对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。 2、图中有回路，遍历算法可能产生死循环。图的遍历深优 4.3.1深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。 （3）对于前两个步骤是递归的图的遍历深优 4.3.1深度优先遍历 （1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。 （2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。 （3）对于前两个步骤是递归的12584637173652841736528413684257或者按以下顺序遍历：注意使用栈支持递归：图的遍历深优 深度优先遍历的特点 “深度”：总是访问顶点的一个相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问 对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。 即栈空时 算法实现（略）有兴趣同学可参看（25－31） 4.3.2、广度优先遍历图的遍历深优 算法实现 （1）需要记录结点的访问状态。 intvisited[顶点号]; （2）需要进行回溯。 lstack_typestack （3）图以邻接表的方式存储 graph_lgraph; （4）算法框架 （5）核心算法图的遍历深优 （4）算法框架 利用栈，不断将顶点的相邻顶点入栈、访问、出栈 算法以栈空结束 框架：第一个被访问的顶点入栈；while（！empty（stack））{核心算法;（即顶点被访问、出\入栈的过程）；}图的遍历深优 （5）核心算法2、找到该顶点的一个未被访问过的相邻顶点3、若找到就将该顶点入栈，并访问，回到14、否则进行回退－－出栈，回到11、从一个顶点开始p=graph.node_list[v];adjp=p->next_adj;while(adjp!=NULL){ if(visited[adjp->node_index]==true) adjp=adjp->next_adj; else break;}if(adjp!=NULL){ v=adjp->node_index; visit（v）；visited[v]=true; push(stack,adjp->node_index);}else v=pop(stack);voiddfs(graph,v){intvisited[MAXNUM];initializevisited[];create_stack(stack);visit(v);visited[v]=true;push(stack,v);while(!empty(stack)){p=graph->node_list[v];adjp=p->next_adj;while(adjp!=NULL){if(visited[adjp->node_index]=true)adjp=adjp->next_adj;elsebreak;}if（adjp!=NULL){v=adjp->node_index;visit(v);visited[v]=true;push(stack,v）；}else{v=pop(stack);}}}经过检查/调试上述算法有误问题出在哪里？在“入栈并访问”的实现谁该入栈，谁该被访问？当前节点入栈（为回退做准备）访问它的相邻未被访问过节点正确做法是：voiddfs(graph,v){intvisited[MAXNUM];initializevisited[];create_stack(stack);visit(v);visited[v]=true;push(stack,v);while(!empty(stack)){p=graph->node_list[v];adjp=p->next_adj;while(adjp!=NULL){if(visited[adjp->node_index]=true)adjp=adjp->next_adj;elsebreak;}if（adjp!=NULL){push(stack,v）；v=adjp->node_index;visit(v);visited[v]=true;}else{v=pop(stack);}}}图的遍历深优 用递归调用实现深度优先遍历算法voiddfs（g，v）{}1访问顶点v；visit（v）；visited[v]=1;p=g[v]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[w]==0)p=p->next_adj;}2取得顶点的一个未被访问过的顶点w；3dfs（g，w）；回到2；4重复2，3直到该顶点所有的相邻顶点都被访问过；dfs(g,w);voiddfs（g，v）{visited[v]=1;p=g[v]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[w]==0)dfs(g,w);p=p->next_adj;}}voiddfs（g，2）{visited[2]=1;p=g[2]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[3]==0)dfs(g,3);p=p->next_adj;}}voiddfs（g，3）{visited[3]=1;p=g[3]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[4]==0)dfs(g,4);p=p->next_adj;}}voiddfs（g，4）{visited[4]=1;p=g[4]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[w]==0)dfs(g,w);p=p->next_adj;}}voiddfs（g，5）{visited[5]=1;p=g[5]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[w]==0)dfs(g,w);p=p->next_adj;}}voiddfs（g，1）{visited[1]=1;p=g[1]->next_adjwhile(p!=NULL){w=p->node_index;if(visited[2]==0)dfs(g,2);p=p->next_adj;}}if(visited[5]==0)dfs(g,5);图的遍历广优 4.3.2、广度优先遍历 访问顶点v后，接着依次访问v的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。1258463712345678注意：8是作为哪个顶点的邻接顶点被访问的？12345678体会队列操作方式：图的遍历广优 广度优先遍历的特点 “广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。 广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已被访问过 算法实现（略）有兴趣同学可参看课件（35－46） 作业图的遍历广优 算法实现分析 （1）需要纪录结点访问状态。 intvisited[顶点号];数组 （2）需要队列辅助操作 lqueue_typequeue； （3）图采用邻接表存储方式 graph_lgraph； （5）算法框架 （4）核心算法图的遍历广优 （4）算法框架 利用队列，不断将顶点出队、入队，直到所有的顶点都被访问过 当队列为空时，算法结束 算法框架第一个顶点入队while(!empty(queue)){核心算法；（即顶点出队，被访问，入队的过程）}图的遍历广优 （5）核心算法1、从队列中取出一个顶点2、逐个访问该顶点的邻接顶点3、未被访问过的邻接顶点依次入队4、当顶点的所有邻接顶点都访问过后，回到1v=dequeue(queue);p=graph.node_list[v];adjp=p->next_adj;while(adjp!=NULL){adjp=adjp->next_adj;}if(visited[adjp->node_index]!=true){v=adjp->node_index;visit(v),visited[v]=true;inqueue(queue,v);}initializevisited[],create_queue(queue);visit(v),visited[v]=true;inqueue(queue,v);while(!empty(queue)){while(adjp!=NULL){if(visited[adjp->node_index]!=true){v=adjp->node_index;visit(v),visited[v]=true;inqueue(queu,v);}adjp=adjp->next;}voidbfs(graph,v){}}v=dequeue(queue);p=graph->node_list[v];adjp=p->next_adj;生成树与图 4.4生成树与最短路径 4.4.1生成树 假设存在这样一颗树： 树结点的集合与图的顶点集合相等 树的分支全部由图的边组成。 称这颗树是这幅图的生成树 生成树是图的: 子集/子图 是一个不包含回路的子图 图的生成树是2143不唯一的！唯一的！生成树与图 4.4.2最小费用生成树 在图所有生成树中，边的权值总和最小的生成树权值6536642416边1－314－622－531－443－642－351－263－565－66将边按权值大小排列生成树与图 算法分析 关键技术： 为什么在（1,4）边选中后不能选（3,6）边－－回路 在选择（3,6）边和（2,3）边时有什么不同，怎样设置条件以区别？ 当时3和6位于同一图中，2、5和3位于不同的图中65366424161－443－642－35生成树与图……1）开始时所有的节点都位于不同的图中2）选择一条连接两个不同子图的最短边3）连接以后两个子图的所有顶点都要改为在一个子图中4）当所有的顶点都位于一个子图中，算法结束。权值边1－314－622－531－443－642－351－26思考既然是颗树，如果选择边数为n－1个时可不可以结束算法呢？算法的优化图的最短路径 4.4.3最短路径 图中两个顶点之间有条路径 最短路径： 是路径中边（弧）的权值总和最小的路径 计算机网络中常使用最短路径算法计算最佳路径 交通网络中使用最短路径算法计算最短旅途多DijkstraAlgorithmFloydAlgorithmDijkstraAlgorithmA1A2A4A3A526512151）初始化时，设A1到其它不直连顶点距离为∞寻找A1到所有节点的最短路径A2A3A4A5顶点距离路径2）选择距离最短的路径3）观察通过新选择的路径是否能更短地到达其它顶点4）选择出的最短路径将不参加下一轮比较5）反复2-4步，直到不剩有顶点265∞A2A3A4A1A2A3－－3更新A1A2A33A1A2A4－－∞A1A2A5－－4A1A2A3A4－－4更新A1A2A3A44A1A2A3A5－－8A1A2A54A1A2A3A4A5－－∞更新算法分析：1)需要路径的集合，（从A到所有其它顶点的路径）－－path[i]当找到一条到该顶点的最短路径时就将该顶点从集合中移出－－s[]顶点集合2)需要最短路径的集合，找出的最短路径逐个放到集合中－－shortest_path[i]3)需要使用邻接矩阵存储的图A[i][j]算法描述：4)输出最短路径的集合shortest_path1)初始化path，根据A[v][i](i∈顶点集合，且i≠v）2)每次从path中选择最短的一条3)将该路径从path中取出并放在shortest_path中4)比较并更改由该路径形成的新的较短路径，回到步骤2x＝find_shortest_path（path）；short_path[i]=path[x];if(path[x]+A[x][i]<path[ji]path[i]=path[x]+(x,i);path_type*shortestpath_DIJ(A[][],V){v为指定的源点for(i=1;i<=VTXNUM;i++){if(i==v)continue;elsepath[i]=(v,i);}if(A[v][i]==0)path[i]==MAXCOST;initialize_path(path);for(n=1;n<=VTXNUM;n++){x=find_shortest_path(path);shortest_path[x]=path[x];s=s+[x];for(i=1;i<=VTXNUM;i++){if(NOTiINs&&x+A[x][i]<path[i])path[i]=path[x]+(x,i);}}returnshortest_path;}s=s+[v];这些赋值语句和加法不是通常语言中的含义表示将（x，i）这条边加入到v到x的路径path[x]中，就形成了从v到x再到i的更短路径作业 教材66页，第23、24题随堂作业写出下面二叉树的先根遍历,中根遍历,后根遍历结果2143随堂作业画出下图的邻接表