c语言行数据结构第06讲图.ppt

实用数据结构基础 第7章 图 第7章 图 知 识 点 图的逻辑结构及基本术语 邻接矩阵和邻接表的存储结构和特点 深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站两种遍历算法 图的连通性和生成树的概念 最短路径的含义及求最短路径的算法 难 点 图的遍历 最小生成树 最短路径 要 求 熟练掌握以下内容： 图的存储结构 图的遍历算法 了解以下内容： 图的最小生成树和求最小生成树算法 带权有向图的最短路径问题 第7章 目录 7-1 图的定义和术语 7-2 图的存储表示 7-3 图的遍历 7-4 图的连通性 7-5 最短路径 小 结 实验7 图子系统 习题7 7-1 图的定义和术语 图7-1 无向图G1 图7-1 无向图G1 7-2 图的存储表示 7-3 图的遍历 图7-4 图的连通性 按照7-1-2节的定义，它是连通图的一棵生成树，并且由深度优先有哪些信誉好的足球投注网站得到的为深度优先生成树；由广度优先有哪些信誉好的足球投注网站得到的为广度优先生成树。例如，图7-15(a)和(b)所示分别为图7-13连通图G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G) 中的边，实线为集合T(G)中的边。 对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图7-16 (b) 所示为图7-16 (a)的深度优先生成森林，它由三棵深度优先生成树组成。 7-5 最短路径 最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，问题是如何在城市A和城市B之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。 例如在图7-20中，设V1为源点，则从V1出发的路径有（括号里为路径长度）： V1到V2的路径有条：V1→V2(20) V1到V3的路径有条：V1→V3(15),V1→V2→V3(55) V1到V4的路径有条：V1→V2→V4(30),V1→V3→V4(45),V1→V2→V3→V4(85) V1到V5的路径有条：V1→V2→V3→V5(65),V1→V3→V5(25) 选出V1到其它各顶点的最短路径，并按路径长度递增顺序排列如下： V1→V3(15)，V1→V2(20)，V1→V3→V5(25)，V1→V2→V4(30)。 从上面的序列中，可以看出一个规律：按路径长度递增顺序生成从源点到其它各顶点的最短路径时，当前正生成的最短路径上除终点外，其它顶点的最短路径已经生成。迪杰斯特拉算法正是根据此规律得到的。 迪杰斯特拉（Dijkstra）算法的基本思想：设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。初始时S中仅有一个源点，T中含除源点外其余顶点，此时各顶点的当前最短长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中剩余顶点的当前最短路径长度，修改原则是：当v的最短路径长度与v到T中顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复以上过程，直到S中包含所有顶点。 小 结 实验7 图子系统 习题7 显然，以上方法是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。 从图的某一点v出发，递归地进行深度优先遍历的过程如下面算法所示。 ???void DFSTraverseM(MGraph *G) ???{ int i; ????? for(i=0;iG-n;i++) ??????visited[i]=FALSE; // FALSE在c语言中定义为0，以下同 ????? for(i=0;iG-n;i++) ??????if (!visited[i]) ??????DFSM(G,i); ?????} void DFSM(MGraph *G,int i) { int j; printf (\t\t深度优先遍历结点: 结点%c\n,G-vexs[i]); visited[i]=TRUE; // TRUE在c语言中定义为1，以下同 for (j=0;jG-n;j++)