基本网络使用---浙江广播电视大学玉环学院.pptVIP

1 第4章　树 数据结构 玉环电大计算机教研室 2002年 学习重点 树的定义和基本术语 树的定义和基本术语 二叉树 第5章　图 数据结构 玉环电大计算机教研室 2002年 学习重点 一、图的定义和术语  二、图的存储结构 二、图的存储结构 三、图的遍历 因为深度优先有哪些信誉好的足球投注网站遍历是递归定义的，故容易写出其递归算法。下面的算法5.3是以邻接矩阵作为图的存储结构下的深度优先有哪些信誉好的足球投注网站遍历算法；算法5.4是以邻接表作为图的存储结构下的深度优先有哪些信誉好的足球投注网站遍历算法。 算法5.3 int visited[VAX_VEX]={0}; void Dfs_m( Mgraph *G,int i){ /* 从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/ printf(%3c,G-vexs[i]); visited[i]=1; for (j=0;jVEX_NUM;j++) if((G-arcs[i][j]==1) (!visited[j])) Dfs_m(G,j); } /*Dfs_m */ 　 算法5.4 int visited[VEX_NUM]={0}; void Dfs_L(ALgraph G,int i){ /* 从第i个顶点出发深度优先遍历图G，G以邻接表表示 */ printf(%3c,G[i].data); visited[i]=1; p=G[i].firstarc; while (p!=NULL) { if(visited[p-adjvex]==0) Dfs_L(G,p-adjvex); p=p-nextarc; } } /*dfs_L*/ 　 2、广度优先有哪些信誉好的足球投注网站遍历 　　连通图广度优先遍历类似于树的按层次遍历，其基本思想如下：从图中某个顶点vi为出发点，在访问了vi 之后，依次访问vi的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们未曾访问过的邻接点，直至图中所有顶点都被访问过。 得到的顶点的访问序列为：v0 → v1 → v2 → v3 → v4 → v5 → v6 → v7 。 int visited[VAX_VEX]={0}; void Bfs_m( Mgraph *G,int k){ /* 从第k个顶点出发广度优先遍历图G，G以邻接矩阵表示*/ Int qu[20]，f=0，r=0； printf(%3c,G-vexs[k]); visited[k]=1; While (r！＝f) {　f++ ；I=qu[f]； for (j=0;jVEX_NUM;j++) if((G-arcs[i][j]==1) (!visited[j])) printf(%3c,G-vexs[k]);　visited[j]=1;r++;qu[r]=j; } } /*Bfs_m */ 四、图的最小生成树 (一)生成树的概念 (二)网络的最小生成树 　 如果连通图是一个网络，称该网络中所有生成树中权值总和最小 的生成树为最小生成树（也称最小代价生成树）。（P81图示） MST性质（P81） 1、普里姆算法 　　普里姆算法的基本思想如下：假设G=(V，{E})是连通网，T=(U，{TE})为欲构造的最小生成树。初始时，U={u0}，TE={φ}。重复下述操作：在所有u∈U，v∈V-U的边中，选择一条权值最小的边(u，v)并入TE，同时将v并入U，直到U=V为止。这时产生的TE中具有n-1条边。上述过程中求得的T=(U，{TE})便是G的一棵最小生成树。 普里姆算法演示 2、克 鲁斯卡尔算法 五、最短路径 1、从某源点到其余顶点之间的最短路径 设有向网G=（V，E），以某指定顶点为源点v0，求从v0出发到图中所有其余各项点的最短路径。以图5-5-1所示的有向网络为例，若指定v0为源点，通过分析可以得到从v0出发到其余各顶点的最短路径和路径长度为： v0 → v1 ：无路径 v0 → v2 ：10 v0 → v3 ：50 （经v4） v0 → v4 ：30 v0 → v5 ：60 （经v4、v3）? 如何在计算机中求得从v0到其余各项点的最短路径呢？ 迪杰斯特拉(Dijkstra)于1959年提出了一个按路径长度递增的次序产生最短路径的算法。 其基本思想是：把图中所有顶点分成两组，第一组包括已确定最短路径的顶点(初始只包括顶点v0)，第二组包括尚未确定最短路径的顶点，然后按最短路径长度递增的次序逐个把第二组的顶点加到第一组中去，直至从v0出发可以到达的所有顶点都包括到第一组中。在这过程中，总保持从v0到第一组各顶点的最短路程长度都不大于从v0到第二组的任何顶点的最短路径长度。另外，每一个顶点对应一个距离值，第一组的顶点对应的距离值就是从v0到此顶点的只包括第一组的顶点为中间顶点的最短路径长度。