图的习题{百度文库}.ppt

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B．1 C．2 D．4 一个有n个顶点的无向图最多有 条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 采用邻接表储存的图的深度优先遍历算法类似于二叉树的 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 采用邻接表储存的图的广度优先遍历算法类似于二叉树的 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 5. 已知如下图所示的无向图，请给出该图的： （1）深度优先遍历该图所得顶点序列和边的序列； （2）广度优先遍历该图所得顶点序列和边的序列。 6.对下图所示的连通图，请分别用普里姆（Prim）和克鲁斯卡尔（Kruskal）算法构造其最小生成树。 7.试给出下图中全部可能的拓扑序列。 8. G为一n个顶点的有向图，其存储结构分别为： 邻接矩阵； 邻接表。 请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。 9.如图所示的无向带权图： 写出它的邻接矩阵，并按普里姆Prim算法求出其最小生成树； 写出它的邻接表，并按克鲁斯卡尔Kruskal算法求出其最小生成树； 10.已知一个无向图的邻接表如下图所示，要求： 画出该无向图； 根据邻接表，分别写出用DFS和BFS算法从顶点v0开始的遍历该图后得到的遍历序列，并画出DFS生成树和BFS生成树。 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A．1/2 B．1 C．2 D．4 一个有n个顶点的无向图最多有 C 条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 采用邻接表储存的图的深度优先遍历算法类似于二叉树的 A 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 采用邻接表储存的图的广度优先遍历算法类似于二叉树的 D 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 5. 已知如下图所示的无向图，请给出该图的： （1）深度优先遍历该图所得顶点序列和边的序列； （2）广度优先遍历该图所得顶点序列和边的序列。 6.对下图所示的连通图，请分别用普里姆（Prim）和克鲁斯卡尔（Kruskal）算法构造其最小生成树。 7.试给出下图中全部可能的拓扑序列。 8. G为一n个顶点的有向图，其存储结构分别为： 邻接矩阵；②邻接表。 请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。 (2) 邻接表结构中的边表恰好就是出边表。因此，其表头数组中firstarc域为空的个数等于出度为零的元素个数。 Void sum_zero2 (AdjList a[], int count) /* count的初值为0，a为有向图的邻接表*/ { for (I=0; In; I++) if (a[I].firstarc==NULL) count++; } 9.如图所示的无向带权图： 写出它的邻接矩阵，并按普里姆Prim算法求出其最小生成树； 写出它的邻接表，并按克鲁斯卡尔Kruskal算法求出其最小生成树； 邻接矩阵 邻接表 * * 习 题 【解】 1、深度优先搜索： 顶点序列：1-2-3-4-5-6 边的序列：（1，2）（2，3）（3，4）（4，5）（5，6） 2、广度优先搜索： 顶点序列：1-2-3-6-5-4 边的序列：（1，2）（1，3）（1，6）（1，5）（2，4） 用普里姆（Prim）算法构造该图最小生成树如下图所示（从顶点h开始）： 用克鲁斯卡尔（Kruskal）算法构造该图最小生成树（略） 【解】： 所有可能的拓扑序列有： 1,5,2,6,3,4或1,5,2,3,6,4 5,1,2,6,3,4或5,1,2,3,6,4 1,5,6,2,3,4或1,5,2,3,6,4 5,1,6,2,3,4或5,1,2,3,6,4 【解】 （1）在邻接矩阵上，一行对应于一个顶点，而且每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行是否有非零元素，如果没有则计数器加1。 Void sum_zero1 (int a[ ][ ], int n, int count) /*n为结点个数，count计度数为0的结点数 */ { for (