第3章-2 图.ppt

* 数据结构 之 非线性结构图 * 例 输出序列： 7 3 1 2 4 8 5 6 1 2 3 4 5 6 7 8 有没有其它的输出序列？(从顶点7开始) * 数据结构 之 非线性结构图 * 深度优先算法的说明 若图不连通，则重复遍历过程。 若图中有回路，不同的算法可能导致访问完其它顶点时又回到出发点，且剩余顶点没有访问到。 * 数据结构 之 非线性结构图 * 深度优先算法的分析 图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿第一个结点的链可以找到某个顶点v的所有邻接顶点w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。 * 数据结构 之 非线性结构图 * 广度优先遍历 假设从图中某个顶点v出发，在访问了v之后，依次访问v的各个未曾访问过的邻接点，并保证”先被访问的顶点的邻接点“要先于”后被访问的顶点的邻接点“被访问。 直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的顶点，则任选其中之一作为起点，重新开始上述过程，直至图中所有顶点都被访问到。 对于广度优先遍历，其关键之处在于怎么保证“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问。也就是先到先被访问，这正好是队列的特点，因此可以使用队列来实现． * 数据结构 之 非线性结构图 * bfs实例 无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。如：结点 1 的邻接结点有三个 2、12、11，则先访问结点 2、11，再访问结点 12。 1 2 12 11 3 6 7 10 4 5 8 9 图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：队列 * 数据结构 之 非线性结构图 * bfs算法 选中第一个被访问的结点 V并访问之; 对结点 V 作已访问过的标志； 依次从结点 V 的未被访问过的第一个、第二个、第三个……第 M个邻接结点 W1 、W2、W3…… Wm ，且进行标记； 依次访问结点 W1 、W2、W3…… Wm的邻接结点，且进行标记； 如果还有结点未被访问，则选中一个起始结点，也标记为V，转向第2步； 所有的结点都被访问到，则结束。 * 数据结构 之 非线性结构图 * bfs算法的类C描述——邻接矩阵实现 void bfs_matrix(int i,graph *g) { int q[n+1]; int f=r=0,j; printf(“%d”,g-v[i]); visited[i]=1; q[++r]=i; while(fr) { i = q[++f]; for(j=1;j=n;j++) * 数据结构 之 非线性结构图 * bfs算法的类C描述——邻接矩阵实现(续) if((g-arcs[i][j]==1)(!visited[j])) { printf(“%d”,g-v[j]); visited[j] = 1; q[++r] = j; } } * 数据结构 之 非线性结构图 * bfs算法的类C描述——邻接表实现 void bfs_link(int i,headnode a[]) { int q[n+1]; int f=r=0; link *p; printf(“%d”,a[i].v); visited[i]=1; q[++r]=i; while(fr) { i = q[++f]; p=a[i].next; * 数据结构 之 非线性结构图 * bfs算法的类C描述——邻接表实现(续) while(p){ if(!visited[p-adjvex]){ printf(“%d”,a[p-adjvex].v; visited[p-adjvex] = 1; q[++r] = p-adjvex;} p = p-next; } } * 数据结构 之 非线性结构图 * 广度优先算法的分析 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。此外，每个顶点被访问一次，共n次。因此，遍历图的时间复杂性为O(n+e)。 数据结构 之 非线性结构图 * 数据结构 之 非线性结构图 * 3.3 图 * 数据结构 之 非线性结构图 * 图的概念和术语 图：图中结点之间的