南工大第四章-图

1、学习文档仅供参考数据结构与算法上机作业第四章图学习文档仅供参考、选择题1 在一个无向图中，所有顶点的度数之和等于所有边数的C 倍。A. 1/2B. 1 C. 2 D. 42、 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的B_ 倍。A. 1/2B. 1C. 2D. 43、 G 是一个非连通无向图，共有28 条边，则该图至少有D个顶点。A. 6B. 7C. 8D. 94、 有 n 个顶点的图的邻接矩阵使用B_ 数组存储的。A. 一维 B. n 行 n 列C.任意行 n 列D. n 行任意列5、 对于一个具有 n 个顶点和 e 条边的无向图，采用邻接表表示，则表头数组大小至少为 设下标为

2、 0 的数组参与使用A。6、以下说法正确的选项是7、深度优先遍历类似与二叉树的8、广度优先遍历类似与二叉树的9、以下关于开放树(Free Tree)的说法错误的选项是A. 具有 n 个结点的开放树包含n-1 条边B. 开放树没有回路A. n-1B. n+1C. n D. n+eA. 有向图B. 有向图的邻接矩阵一定是对称的C.无向图的邻接矩阵一定是对称的D. 无向图的邻接矩阵可以不对称A.先根遍历B.中根遍历C.后根遍历D.层次遍历A.先根遍历B.中根遍历C.后根遍历D.层次遍历学习文档仅供参考C.开放树可以是非连通图学习文档仅供参考D.在开放树中任意加一条边，一定会产生回路10、在如以下图所

3、示的图中，从顶点列为_A. a, b, e, c, d, fC. a, e, b, c, f, d11、在如上图所示的图中，从顶点 为a 出发，按广度优先遍历，则可能得到的一种顶点的序列。C. a, e, b, c, f, dD. a, e, d, f, c, b12、设网(带权的图)有 n 个顶点和 e 条边，则采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为_ C。A. 0( n)B. O(n+e)C. 0( n2)13、 设图有 n 个顶点和 e 条边，求解最短路径的A. O( n)B. O(n+e)C. O( n2)14、 最小生成树是指 _ C 。A. 由连通网所得到的边

4、数最少的生成树。B. 由连通网所得到的顶点数相对较少的生成树。C. 连通网中所有生成树中权值之和为最小的生成树。D. 连通网的极小连通子图。15、下面关于工程计划的 AOE 网的表达中，不正确的选项是 _ BB. a, c, f, e, b, dD. a, e, d, f, c, bA. a, b, e, c, d, fB. a, b, e, c, f, dD. O(n3)Floyd 算法的时间复杂度为OD. O(n3)b学习文档仅供参考A.关键活动不按期完成就会影响整个工程的完成时间。B.任何一个关键活动提前完成，那么整个工程将会提前完成。C. 所有关键活动都提前完成，那么整个工程将会提前完

5、成。D. 某些关键工程假设提前完成，那么整个工程将会提前完成。16、 在 AOE 网中，始点和汇点的个数为C 。A. 1 个始点，假设干个汇点B.假设干个始点，假设干个汇点C假设干个始点，1 个汇点C. 1 个始点，1 个汇点17、 在以下图所示的无向图中， 从顶点 v1 开始采用 Prim 算法生成最小生成树，算法过程中产生的顶点次序为B。A. v1, v3, v4, v2, v5, v6B. v1, v3, v6, v2, v5, v4C. v1, v2, v3, v4, v5, v6D. v1, v3, v6, v4, v2, v518、在上图所示的途中，采用 Cruskal 算法生成最

6、小生成树，过程中产生的边的次序是 _C。A. (v1, v2), (v2, v3), (v5, v6), (v1, v5)B. (v1, v3), (v2, v6), (v2, v5), (v1, v4)C. (v1, v3), (v2, v5), (v3, v6), (v4, v5)D. (v2, v5), (v1, v3), (v5, v6), (v4, v5)19、如以下图所示的图中，其中一个拓扑排序的结果是A。A. v1Tv2Tv3Tv6Tv4 v5 v7 v8B. v1Tv2TV3Tv4TV5Tv6TV7Tv8C. v1Tv6TV4Tv5TV2Tv3TV7Tv8D. v1Tv6Tv2

7、Tv3TV7Tv8Tv4Tv520、在以下图所示的 AOE 网中，活动 a9 的最早开始时间为 _BA. 13B. 14C. 15D. 1621、 在上图所示的 AOE 网中，活动 a4 的最迟开始时间为DA. 2 B. 3 C. 4 D. 522、 设图有 n 个顶点和 e 条边，当用邻接表表示该图时，则求解最短路径的Dijkstra 算法的时间复杂度为O。A. O( n)B. O(n+e)C. O(e)D. O( n2)二、填空题v 的顶点数目或边数目称为顶点v 的_ 入的顶点数目或边数目称为顶点 v 的_出4、已知一个图的邻接矩阵表示，计算第j 个顶点的入度的方法是第 j 行非 0 元素

8、的个数_ ，计算第 j 个顶点的出度的方法是 第 j 列非 0 元素的个数_。5、假设将图中的每条边都赋予一个权，则称这种带权的图为_ 网学习文档仅供参考1、 假设无向图G 中顶点数为n(n-1)n,则图条边。G 至多有n(n_1)/2条边；假设 G 为有向图,2、 图的存储结构主要有两种， 分别是 阵邻接表邻接矩3、假设 G 是有向图，则把邻接到顶点 度_；把邻接于顶点学习文档仅供参考6、 无论是有向图还是无向图，顶点数n、边数 e 和各顶点的度D(vi)之间的关系为：_ 。7、 假设路径上第一个顶点V1与最后一个顶点 Vm重合，则称这样的简单路径为回路或环。8、 如果图中任意一对顶点都是连

9、通的，则称此图是连通图_ ;非连通图的极大连通子图叫做 _连通分量_ 。9、 创建一个邻接矩阵图的复杂度是On*n_ ;创建一个链接表图的复杂度是O(n+e)_ 。10、 图的遍历有深度优先遍历_和广度优先遍历等方法。11、 在深度优先搜索和广度优先搜索中，都采用visitedi= 0(false) 的方式设置第 i 个顶点为 new,而采用 visitedi= 1true的方式标识第 i 个结点为 old。12、 由于深度优先算法的特点，深度优先往往采用递归的方式实现。13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构_ 实现。14、 在深度优先搜索和广度优先搜索

10、中，在搜索过程中所经过的边都称为搜索边_ 。15、 连通而且无环路的无向图称为开放数_ 。16、 对于含有 n 个顶点 e 条边的连通图，利用Prim 算法求其最小生成树的时间复杂度为O(n*n)_ ，利用 Kruscal 算法求最小生成树的时间复杂度是_。3、顶点表示活动的网简称为 _AOV_ ； 边表示活动的网简称为AOE 。17、 一个含有 n 个顶点的无向连通图，其每条边的权重都是a(a0)，则其最小生成树的权重等于 n-1*a_ 。18、 具有 n 个顶点的有向图，如果采用邻接矩阵表示该图， 则求某顶点到其他各顶点的最短 路径的Dijkstra 算法的时间复杂度是 O(n*n)_;如

11、果采用邻接表表示该图，则时间复杂度为_ O(e) 。19、 在用 Dijkstra 算法求单源最短路径的过程中，将顶点集合V 划分为两个集合 S 和 V-S，其中 S 中的点为 _ 最短路径已确定的顶点集合_ ，V-S 中的点为最短路径未确定的顶点集合_ 。学习文档仅供参考20、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用算法，另一种方法是 _。21、 假设有向图的邻接矩阵C 的传递闭包为 A，则 Aij=1 表示_22、 有向图的中心点是指具有最小偏心度的顶点_。三、已知一个无向图如以下图所示，试给出该图的邻接矩阵和邻接表存储示意图画图，分别用矩阵和数组链表图表示，并

12、编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码:#in clude using n amespace std; #defi nemax_vexNum 26 typedef structint vex_num, arc_num;int count;char vexsmax_vexNum;double arcsmax_vexNummax_vexNum; Graph;/添加一个新的顶点char NewNode(Graph *G,char v)/最大顶点个数/顶点数，边数/记录当前顶点数/顶点向量/邻接矩阵学习文档 仅供参考G-ve

13、xsG -count=v;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v) for( int i=0;icount;i+) if(v=G -vexsi) return i;void Delete(Graph *G,char v)/先删除点int i,j;int temp_count= G-count; i=FindPosition(G,v);for(j=i;jvexsj=G -vexsj+1;G-count - ;/ 删除边/先删除行int p=i;/ 记住位置for(i=p;itemp_count -1;i+)学习文档

14、 仅供参考for(j=0;jarcsij=G -arcsi+1j;/再删除列for(i=p;itemp_count -1;i+)for(j=0;jarcsji=G -arcsji+1;/建立 v1 与 v2 的一条边void SetSoucc(Graph * G,char v1,char v2)/先找到对应的定的位置int i,j;int temp_count= G -count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) / 没有找到return ;/找到后 ， Aij=0;vexsji=0;

15、G- arcsij=1;G- arcsji=1;学习文档 仅供参考void DelSucc(Graph * G,char v1,char v2)int i,j;int temp_count= G -count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) / 没有找到return ;/找到后 ， Aij=0;vexsji=0;G- arcsij=0;G- arcsji=0;/判断 v1y 与 v2 是否连接bool isEdge(Graph * G,char v1,char v2)int i,j;

16、int temp_count= G -count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) / 没有找到return -1;if(G -arcsij=1)学习文档 仅供参考return true;return false;void Print(Graph * G)int i,j;for( i=0;icount;i+)for(j=0;jcount;j+)coutarcsij coutendl;学习文档仅供参考coutcount=0;NewNode(G,A);NewNode(G,B);NewNod

17、e(G,C);NewNode(G,D);/插入边SetSoucc(G,A,B);SetSoucc(G,A,D);SetSoucc(G,C,B);Print(G);/删除一个顶点Delete(G,C);Print(G);学习文档 仅供参考删除边DelSucc(G,A,D);Prin t(G);if(isEdge(G,A,B)coutA 与 B 右边endl;return 0;四、已知一个有向图如以下图所示，试给出图的邻接矩阵和邻接表存储示意图画图,用矩阵和数组链表图表示，并编程分别实现该图的邻接矩阵表示和邻接表表示， 两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码：#in cl

18、ude#i nclude #in clude using n amespace std;#defi ne max_n 20struct ArcNode char adjvex=#;分别要求编写学习文档仅供参考ArcNode * next=NULL; ;typedef struct VNodechar data;ArcNode * first_head; VNode ,AdjListmax_n;typedef struct AdjList vertices;int vexnum,arcnum;int count=0; Graph;/新增一个顶点char NewNode(Graph * G,cha

19、r v) G-verticesG -count.data=v;G-verticesG -count.first_head=new ArcNode;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v)学习文档 仅供参考for( int i=0;icount;i+)if(v=G -verticesi.data)return i;/删除一个顶点void DelNode(Graph * G,char v)int i=FindPosition(G,v);/去头ArcNode *p=G - verticesi.first_head;/现

20、在 vertices 中删除int j;for(j=i;jcount -1;j+)G-verticesj=G -verticesj+1;G-verticesj.data=#;G-verticesj.first_head=NULL;G-count - ;/删除边ArcNode *q;while(p!=NULL)q=p;p=p-next;学习文档 仅供参考q=NULL;/设置 v1 到 v2 直接的一条边void SetSucc(Graph * G,char v1,charint i=FindPosition(G,v1);ArcNode *p;p=G-verticesi.first_head;wh

21、ile(p -next!=NULL) p=p-next;ArcNode *q=new ArcNode;q-adjvex=v2;p-next=q;ArcNode * FindNode(ArcNode * p,char v2)for(;p;p=p -next)if(p-next-adjvex=v2) break;v2)学习文档 仅供参考return p;void Detele(Graph * G,char v1,char v2)int i=FindPosition(G,v1);ArcNode *p;/没有找到if(i= -1)return ;p=FindNode(G -verticesi.firs

22、t_head,v2);/因为 p 是上一个节点的位置，用 q 来保存/要删除的节点的地址学习文档 仅供参考ArcNode *q = p -next;/ 通过将上一个节点的 next 指针指向要删除节点的/针志向的节点实现断开要删除节点的目的/ p-adjvex=p -next-adjvex;p-next = p -next -next;/删除要删除的节点 qdelete q;/输出领接表void Print(Graph * G)ArcNode *p;for(int i=0;icount;i+)/先将 datacoutverticesi.data;/从每个顶点的头结点开始遍历if(G -vert

23、icesi.first_head -next!=NULL)p=G-verticesi.first_head -next;while(p!=NULL)coutadjvex;next 指学习文档 仅供参考p=p-next;coutendl;coutendl;Graph * G=new Graph;int main() NewNode(G,A);NewNode(G,B);NewNode(G,C);NewNode(G,D);Print(G);SetSucc(G,A,D);SetSucc(G,A,B);SetSucc(G,A,C);SetSucc(G,B,C);SetSucc(G,C,D);SetSuc

24、c(G,D,B);学习文档仅供参考Prin t(G);Detele(G,A,C);Detele(G,D,B);Prin t(G);SetSucc(G,D,C);Prin t(G);return 0;五、已知一个图的顶点集为a, b, c, d, e,其邻接矩阵如以下图，考虑图为无向图和有向图两种情况，分别画出该图。01001 r10010000I10I10101 10 J六、已知一个连通图如以下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列假设从顶点 v1 出发。并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写 相关基本操作，并在主函数中求出深度优先序列和广度优先序列。代码：

25、#in clude学习文档仅供参考#i nclude #in clude#in cludeusing n amespace std;#defi ne max_n 20 struct ArcNode char adjvex=#;ArcNode * n ext=NULL;；typedef struct VNode char data;ArcNode * first_head; VNode ,AdjListmax_ n;typedef struct AdjList vertices;int visitmax_n = 0; / 记录是否被访问过int vexnum,arcnum;int count=0

26、; Graph;/新增一个顶点char NewNode(Graph * G,char v) 学习文档 仅供参考G-verticesG -count.data=v;G-verticesG -count.first_head=new ArcNode;G-count+;return v;/寻找某个顶点的位置int FindPosition(Graph *G,char v) for( int i=0; icount; i+) if(v=G -verticesi.data)return i;/删除一个顶点 void DelNode(Graph * G,char v) int i=FindPosition

27、(G,v);/去头ArcNode *p=G - verticesi.first_head;/现在 vertices 中删除int j;for(j=i; jcount -1; j+)G-verticesj=G -verticesj+1;G-verticesj.data=#;G-verticesj.first_head=NULL;学习文档 仅供参考G- count - ;/删除边ArcNode *q; while(p!=NULL) q=p; p=p-next; q=NULL;学习文档 仅供参考/设置 v1 到 v2 直接的一条边void SetSucc(Graph * G,char v1,char

28、int i=FindPosition(G,v1);ArcNode *p; p=G-verticesi.first_head; while(p -next!=NULL) p=p-next;ArcNode *q=new ArcNode;q-adjvex=v2;p-next=q;/对于无向图void SetSucc1(Graph * G,char v1,charSetSucc(G,v1,v2);SetSucc(G,v2,v1);v2) v2) 学习文档 仅供参考ArcNode * FindNode(ArcNode * p,char v2) for(; p; p=p -next) if(p -next

29、 -adjvex=v2)break;return p;void Detele(Graph * G,char v1,char v2) int i=FindPosition(G,v1);ArcNode *p;/没有找到if(i= -1)return ;p=FindNode(G -verticesi.first_head,v2);因为 p 是上一个节点的位置，用 q 来保存/要删除的节点的地址ArcNode *q = p -next;/通过将上一个节点的 next 指针指向要删除节点的/针志向的节点实现断开要删除节点的目的/ p-adjvex=p -next-adjvex; p-next = p -

30、next -next; /删除要删除的节点 q delete q;next 指学习文档 仅供参考/输出领接表void Print(Graph * G) ArcNode *p;for(int i=0; icount; i+) /先将 datacoutverticesi.data;/从每个顶点的头结点开始遍历if(G -verticesi.first_head -next!=NULL) p=G-verticesi.first_head -next; while(p!=NULL) coutadjvex;p=p-next;coutendl;coutendl;void makeVisitNull(Gra

31、ph * G)for(int i=0;ivisiti=0;学习文档 仅供参考void Dfs_part(Graph * G,int i) ArcNode *p=G -verticesi.first_head -next;for(; p; p=p -next) int i=FindPosition(G,p - adjvex);if(!G -visiti) G-visiti=1;coutadjvex;Dfs_part(G,i);/深度优先遍历void DFS(Graph * G,int i) coutverticesi.data;G-visiti=1;Dfs_part(G,i);/恢复makeVi

32、sitNull(G);coutendl;queue qList;void Bfs_part(Graph * G) int t= qList.front();学习文档 仅供参考coutverticest.data;qList.pop();ArcNode *p=G -verticest.first_head -next;for(; p; p=p -next) 学习文档 仅供参考int i=FindPosition(G,p - adjvex);if(!G -visiti) G-visiti=1;qList.push(i);if(!qList.empty()Bfs_part(G);BFS(Graph

33、* G,int i) G-visiti=1;qList.push(i);Bfs_part(G);/恢复makeVisitNull(G);coutendl;Graph * G=new Graph;int main() /void学习文档 仅供参考NewNode(G,1);NewNode(G,2);NewNode(G,3);NewNode(G,4);NewNode(G,5);NewNode(G,6);Print(G);SetSucc1(G,1,2);SetSucc1(G,1,4);SetSucc1(G,1,6);SetSucc1(G,2,3);SetSucc1(G,2,4);SetSucc1(G,

34、2,5);SetSucc1(G,3,5);SetSucc1(G,4,6);SetSucc1(G,4,5);Prin t(G);coutDFS:e ndl;DFS(G,O);coutBFS:e ndl;学习文档仅供参考BFS(G,0);return 0;七、基于深度优先搜索算法，写出求无向图所有连通子图的算法，并求连通分量。提示：对于无向图，从任一个顶点出发进行DFS 遍历，当本次遍历完成后，其所访问的结点构成一个连通子图；如果还存在没有访问过的结点，则从中任一个结点出发进行DFS 遍历，直到所有结点都被访问。每一次调用DFS 后都得到此非连通图的一个连通子图，调用 DFS 的次数就是连通子图的

35、个数。八、网络 G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。r081011803013103040110407013070丿解:九、以下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim 算法和 Kruskal 算法求最小生成树包括算法代码和画图。十、代码：#in elude #in elude #in elude #i nclude using n amespaee std;#defi ne INFINITE OxFFFFFFFF#defi ne VertexData un sig ned int / 顶点数据#defi ne UINTun sig ned int#de

36、fi ne vexCou nts 6 / 顶点数量char vextex = A, B, C, D, E, F ;struct node VertexData data;un sig ned int lowesteost; closedgevexCounts; /Prim 算法中的辅助信息typedef struct VertexData u;VertexData v;un sig ned int cost; 边的代价 Arc; /原始图的边信息void AdjMatrix(u nsig ned int adjMatvexCou nts) / 邻接矩阵表示法学习文档仅供参考学习文档 仅供参考f

37、or (int i = 0; i vexCounts; i+)/初始化邻接矩阵for (int j = 0; j vexCounts; j+) adjMatij = INFINITE;int Minmum(struct node * closedge) / 返回最小代价边unsigned int min = INFINITE;int index = -1;for (int i = 0; i vexCounts; i+) if (closedgei.lowestcost min & closedgei.lowestcost !=0) min = closedgei.lowestcost;

38、index = i;return index;void MiniSpanTree_Prim(unsigned int adjMatvexCounts, VertexData s) for (int i = 0; i vexCounts;i+) closedgei.lowestcost = INFINITE;closedges.data = s;/从顶点 s 开始closedges.lowestcost = 0;for (int i = 0; i vexCounts; i+) / 初始化辅助数组if (i != s) closedgei.data = s;学习文档 仅供参考closedgei.l

39、owestcost = adjMatsi;for (int e = 1; e = vexCounts -1; e+) /n -1 条边时退出int k = Minmum(closedge); /选择最小代价边cout vextexclosedgek.data - vextexk endl;/ 加入到最小生成树closedgek.lowestcost = 0; / 代价置为 0for (int i = 0; i vexCounts; i+) / 更新 v 中顶点最小代价边信息if ( adjMatki closedgei.lowestcost) closedgei.data = k;closed

40、gei.lowestcost = adjMatki;void ReadArc(unsigned int adjMatvexCounts,vector &vertexArc) / 保存图的边代价 信息Arc * temp = NULL;for (unsigned int i = 0; i vexCounts; i+) for (unsigned int j = 0; j u = i;temp-v = j;temp-cost = adjMatij;vertexArc.push_back(*temp);学习文档 仅供参考bool compare(Arc A, Arc B) return A.

41、cost B.cost ? true : false;bool FindTree(VertexData u, VertexData v,vectorvector &Tree) unsigned int index_u = INFINITE;unsigned int index_v = INFINITE;for (unsigned int i = 0; i Tree.size(); i+) / 检查 u,v 分别属于哪颗树if (find(Treei.begin(), Treei.end(), u) != Treei.end()index_u = i;if (find(Treei.begin(), Treei.end(), v) != Treei.end()index_v = i;if (index_u != index_v) /u,v 不在一