作业6解答.doc

图作业6一、单项选择题1采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（）。（南方名校经典试题）A）先序遍历B）中序遍历C）后序遍历D）层次遍历【分析】图的深度优先搜索与二叉树的先序遍历都类似，都需用递归（也可转换为用栈）实现，而广度优先搜索则与二叉树的层次遍历类似，都是用队列实现，不能用栈或递归实现。【答案：A】2一个n个顶点的连通无向图，其边的个数至少为（）。（南方名校经典试题）A）n-1B）nC）n+1D）nlogn【分析】边数最少的边通图是树，其边数为顶点个数-1。【答案：A】3下面（）可以判断出一个有向图中是否有环（回路）？（北方名校典试题）A）求关键路径B）拓扑排序C）求最短路径D）前面都不正确【分析】对于有向图可用拓扑排序的方法判断是否有环，求最短路径与求关键路径都与环没任何关系。【答案：B】二、综合题1设有带权无向图G如图6-9所示：（南方名校经典试题）图6-9带权无向图G试给出： （1）从V1开始的深度优先遍历；（2）从V1开始的广度优先遍历；（3）从V1开始执行的普里姆（Prim）算法过程中所选边的序列。【解答】（1）从V1开始的深度优先遍历：V1 V2 V4 V8 V5 V3 V6 V7（2）从V1开始的广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8（3）从V1开始执行的普里姆（Prim）算法过程中所选边的序列：(V1,V3)，(V3,V6)，(V3,V7)，(V1,V2)，(V2,V5)，(V2,V4)，(V5,V8)2对如下图所示的有向图G试给出各顶点的入/出度。（南方名校经典试题）有向图G【解答】各顶点的入/出度如下表所示：各顶点的入/出度顶点123456入度302123出度1412123给出如图6-14所示的所有拓扑有序序列。（南方名校经典试题）图6-14有向图示意图【解答】ACBDE、ACDBE、ACDEB、ADCBE、ADCEB4在有向图G中顶点只有编号的信号，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写算法完成下列功能：（北方名校经典试题）（1）编写算法实现由邻接矩阵A建立有向图G的邻接表存储结构；（2）编写算法判断有向图G是否有根，若有，则打印所有根结点的值。注：此题较难，选作。【解答】（1）按行扫描邻接矩阵A将得到的弧建立邻接表的弧结点即可建立有向图G的邻接表存储结构。C+语言版测试程序见6_2_4_1c+，具体算当如下：template void CreateGraph(Digraphm* Gm,Digraphal* &Gl)/由邻接矩阵存储结构建立有向图的邻接表存储结构Gl=new Digraphal;Gl-count=Gm-count;for(int i=0;icount;i+)for(int j=0;jcount;j+)if (Gm-adjacencyij)Gl-neighborsi.insert(Gl-neighborsi.size(),j);/复制Gm到GlC语言版测试程序见6_2_4_1c，具体算当如下：void CreateGraph(AdjMatrix &A,int vexnum,ALGraph &G)/由邻接矩阵A建立有向图G的邻接表存储结构,vexnum为顶点个数int i,j;ArcNode *p;G.kind=DG;/G为有向图G.vexnum=vexnum;/为图顶点个数赋值G.arcnum=0;/弧数初始化为0for(i=0;ivexnum;i+)/初始化图顶点信息G.verticesi.data=i;G.verticesi.firstarc=NULL;for(i=0;i=0;j-)if(Aij=1)/对图G的弧进行处理/生成邻接表的弧p=new ArcNode;p-adjvex=j;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;G.arcnum;/图G的弧数自增1（2）采用深度优先遍历可得到本题的算法，如从某个顶点可遍历到所有其他顶点，则该顶点为根结点，否则不是根结点；对每个顶点遍历一次即可完成任务。C+语言版测试程序见6_2_4_2c+，具体算当如下：bool visitedMAX_VERTEX_NUM;/从第v个顶点出发递归地深度优先遍历图Gtemplate void DFS(Digraphal *G,int v,int &n);template void GraphRoot(Digraphal *G)/判断有向图G是否有根，若有，则打印所有根结点的值bool exist_root=false;int n;for(int v=0;vcount;v+)for(int u=0;ucount;u+)visitedu=false;/初始化访问标志数组n=0;/已访问顶点数DFS(G,v,n);/调用DFSif(n=G-count)/n=G.n()表示v主根顶点if(exist_root=false)/显示存储根顶点coutendl存在根结点:;exist_root=true;coutv ;/显示根顶点 if(exist_root=false)/显示不存在根顶点coutendl不存在根结点.;template void DFS(Digraphal *G,int v,int &n)/从第v个顶点出发递归地深度优先遍历图Gint w;visitedv=true;n+;for(int i=0;ineighborsv.size();i+)G-neighborsv.retrieve(i,w);if(!visitedw)/对v的尚未访问的邻接顶点w调用DFSDFS(G,w,n);C语言版测试程序见6_2_4_2c，具体算当如下：void GraphRoot(ALGraph G)/判断有向图G是否有根，若有，则打印所有根结点的值Status visitedMAX_VERTEX_NUM;/访问标志数组Status exist_root=FALSE;int n;for(int v=0;vG.vexnum;v+)for(int u=0;uG.vexnum;u+)visitedu=FALSE;/初始化访问标志数组n=0;/已访问顶点数DFS(G,v,visited,n);/设用DFSif(n=G.vexnum)/n=G.vexnum表示v主根顶点if(exist_root=FALSE)/显示存储根顶点coutendl存在根结点:;exist_root=TRUE;coutG.ve