南工大第四章-图

1、数据结构与算法上机作业第四章 图一、选择题1、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。A. 1/2B. 1C. 2D. 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条边的无向图，采用邻接表表示，则表头数组大小至少为（假设下标为0的数组参与使用） A 。A. n-1B. n+1C. nD

2、. n+e6、下列说法正确的是 C 。A. 有向图的邻接矩阵一定是不对称的B. 有向图的邻接矩阵一定是对称的C. 无向图的邻接矩阵一定是对称的D. 无向图的邻接矩阵可以不对称7、深度优先遍历类似与二叉树的 A ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历8、广度优先遍历类似与二叉树的 D ：A. 先根遍历B. 中根遍历C. 后根遍历D. 层次遍历9、下列关于开放树(Free Tree)的说法错误的是 C ： A. 具有n个结点的开放树包含n-1条边 B. 开放树没有回路 C. 开放树可以是非连通图 D. 在开放树中任意加一条边，一定会产生回路10、在如下图所示的图中，从顶点a出发

3、，按深度优先遍历，则可能得到的一种顶点的序列为 。 A. a, b, e, c, d, fB. a, c, f, e, b, d C. a, e, b, c, f, dD. a, e, d, f, c, b11、在如上图所示的图中，从顶点a出发，按广度优先遍历，则可能得到的一种顶点的序列为 。A. a, b, e, c, d, fB. a, b, e, c, f, dC. a, e, b, c, f, dD. a, e, d, f, c, b12、设网(带权的图)有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为 C 。A. O(n)B. O(n+e)C. O(n

4、2)D. O(n3)13、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为 O 。A. O(n)B. O(n+e)C. O(n2)D. O(n3)14、最小生成树是指 C 。A. 由连通网所得到的边数最少的生成树。B. 由连通网所得到的顶点数相对较少的生成树。C. 连通网中所有生成树中权值之和为最小的生成树。D. 连通网的极小连通子图。15、下面关于工程计划的AOE网的叙述中，不正确的是 B 。A. 关键活动不按期完成就会影响整个工程的完成时间。B. 任何一个关键活动提前完成，那么整个工程将会提前完成。C. 所有关键活动都提前完成，那么整个工程将会提前完成。D. 某些关键工程

5、若提前完成，那么整个工程将会提前完成。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算法生成最小生成树，过程中产生的边的次序是 C 。A. (v1

6、, 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. v1v2v3v6v4v5v7v8B. v1v2v3v4v5v6v7v8C. v1v6v4v5v2v3v7v8D. v1v6v2v3v7v8v4v520、在下图所示的AOE网中，活动a9的最早开始时间为 B 。A. 13B.

7、 14C. 15D. 1621、在上图所示的AOE网中，活动a4的最迟开始时间为 D A. 2B. 3C. 4D. 522、设图有n个顶点和e条边，当用邻接表表示该图时，则求解最短路径的Dijkstra算法的时间复杂度为 O 。A. O(n)B. O(n+e)C. O(e)D. O(n2)二、填空题1、若无向图G中顶点数为n，则图G至多有 n(n-1)/2 条边；若G为有向图，则图G至多有 n(n-1) 条边。2、图的存储结构主要有两种，分别是 邻接表 和 邻接矩阵 。3、若G 是有向图，则把邻接到顶点v 的顶点数目或边数目称为顶点v 的 入度 ；把邻接于顶点v 的顶点数目或边数目称为顶点v

8、的 出度 。4、已知一个图的邻接矩阵表示，计算第j个顶点的入度的方法是 第j行非0元素的个数 ，计算第j个顶点的出度的方法是 第j列非0元素的个数 。5、若将图中的每条边都赋予一个权，则称这种带权的图为 网络 。6、无论是有向图还是无向图，顶点数n 、边数e 和各顶点的度D(vi)之间的关系为： 。7、若路径上第一个顶点v1 与最后一个顶点vm 重合, 则称这样的简单路径为 回路或环 。8、如果图中任意一对顶点都是连通的, 则称此图是 连通图 ；非连通图的极大连通子图叫做 连通分量 。9、创建一个邻接矩阵图的复杂度是 O（n*n） ；创建一个链接表图的复杂度是 O(n+e) 。10、图的遍历有

9、 深度优先遍历 和广度优先遍历等方法。11、在深度优先搜索和广度优先搜索中，都采用visitedi= 0(false) 的方式设置第i个顶点为new，而采用visitedi= 1（true） 的方式标识第i个结点为old。12、由于深度优先算法的特点，深度优先往往采用 递归 的方式实现。13、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据结构 队列 实现。14、在深度优先搜索和广度优先搜索中，在搜索过程中所经过的边都称为 搜索边 。15、连通而且无环路的无向图称为 开放数 。16、对于含有n个顶点e条边的连通图，利用Prim算法求其最小生成树的时间复杂度为 O(n*n)

10、，利用Kruscal算法求最小生成树的时间复杂度是 O(e*lg e) 。3、顶点表示活动的网简称为 AOV ；边表示活动的网简称为 AOE 。17、一个含有n个顶点的无向连通图，其每条边的权重都是a(a0)，则其最小生成树的权重等于 （n-1）*a 。18、具有n个顶点的有向图，如果采用邻接矩阵表示该图，则求某顶点到其他各顶点的最短路径的Dijkstra算法的时间复杂度是 O(n*n) ；如果采用邻接表表示该图，则时间复杂度为 O(e) 。19、在用Dijkstra算法求单源最短路径的过程中，将顶点集合V划分为两个集合S和V-S，其中S中的点为 最短路径已确定的顶点集合 ，V-S中的点为 最

11、短路径未确定的顶点集合 。20、求每一对顶点之间的最短路径，可以用两种方法，一种是分别对每个顶点采用 算法，另一种方法是 。21、假设有向图的邻接矩阵C的传递闭包为A，则Aij=1表示 。22、有向图的中心点是指 具有最小偏心度的顶点 。三、已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码：#includeusing namespace std;#define max_vexNum 26 / 最大顶点个数 typedef s

12、truct int vex_num, arc_num; / 顶点数 ,边数 int count; /记录当前顶点数 char vexsmax_vexNum; / 顶点向量 double arcsmax_vexNummax_vexNum; / 邻接矩阵 Graph;/添加一个新的顶点 char NewNode(Graph *G,char v)G-vexsG-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 D

13、elete(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+) 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,c

14、har 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=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

15、=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;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

16、 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); NewNode(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); Print(G);if(isEdge(G,A,B)coutA与B右边en

17、dl;return 0; 四、已知一个有向图如下图所示，试给出图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表表示，要求编写两种表示方法的存储结构、相关基本操作，并在主函数中创建该图。代码：#include#include #includeusing namespace std;#define max_n 20 struct ArcNode char adjvex=#; ArcNode * next=NULL; ;typedef struct VNodechar data;ArcNode * first_head; VNode ,Ad

18、jListmax_n;typedef struct AdjList vertices;int vexnum,arcnum;int count=0; 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;

19、 /删除一个顶点void DelNode(Graph * G,char v)int i=FindPosition(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直接的一条边 voi

20、d SetSucc(Graph * G,char v1,char v2)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;ArcNode * FindNode(ArcNode * p,char v2) for(;p;p=p-next) if(p-next-adjvex=v2) break; return p;void Detele(Graph * G,char v1,cha

21、r 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指针指向要删除节点的next指 /针志向的节点实现断开要删除节点的目的/ p-adjvex=p-next-adjvex; p-next = p-next-next; /删除要删除的节点q delete q;/输出领接表 void Print(Graph * G)Ar

22、cNode *p;for(int i=0;icount;i+)/先将 data coutverticesi.data;/从每个顶点的头结点开始遍历 if(G-verticesi.first_head-next!=NULL)p=G-verticesi.first_head-next; while(p!=NULL) coutadjvex; 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

23、,A,D); SetSucc(G,A,B); SetSucc(G,A,C); SetSucc(G,B,C); SetSucc(G,C,D); SetSucc(G,D,B); Print(G); Detele(G,A,C); Detele(G,D,B); Print(G); SetSucc(G,D,C); Print(G);return 0;五、已知一个图的顶点集为a, b, c, d, e，其邻接矩阵如下图，考虑图为无向图和有向图两种情况，分别画出该图。六、已知一个连通图如下图所示，分别给出一个按深度优先遍历和广度优先遍历的顶点序列（假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表示和邻接

24、表表示，要求编写相关基本操作，并在主函数中求出深度优先序列和广度优先序列。代码：#include#include #include#includeusing namespace std;#define max_n 20struct ArcNode char adjvex=#;ArcNode * next=NULL; ;typedef struct VNode char data;ArcNode * first_head; VNode ,AdjListmax_n;typedef struct AdjList vertices;int visitmax_n = 0; /记录是否被访问过int ve

25、xnum,arcnum;int count=0; 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=Fi

26、ndPosition(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 v2) int i=FindPositio

27、n(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,char v2) SetSucc(G,v1,v2);SetSucc(G,v2,v1);ArcNode * FindNode(ArcNode * p,char v2) for(; p; p=p-next) if(p-next-adjvex=v2)break;return p;void Det

28、ele(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指针指向要删除节点的next指/针志向的节点实现断开要删除节点的目的/ p-adjvex=p-next-adjvex;p-next = p-next-next;/删除要删除的节点qdelete q;/输出领接表void P

29、rint(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(Graph * G)for(int i=0;ivisiti=0;void Dfs_part(Graph * G,int i) ArcN

30、ode *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);/恢复 makeVisitNull(G); coutendl;queue qList;void Bfs_part(Graph * G) int t=qList.front();

31、 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);/void BFS(Graph * G,int i) G-visiti=1;qList.push(i);Bfs_part(G);/恢复 makeVisitNull(G);coutendl;Graph * G=new

32、Graph;int main() 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,2,5);SetSucc1(G,3,5);SetSucc1(G,4,6);SetSucc1(G,4,5);Print(G); coutDFS:endl; DFS(G,0); coutBFS:endl; BFS(

33、G,0);return 0;七、基于深度优先搜索算法，写出求无向图所有连通子图的算法，并求连通分量。提示：对于无向图，从任一个顶点出发进行DFS遍历，当本次遍历完成后，其所访问的结点构成一个连通子图；如果还存在没有访问过的结点，则从中任一个结点出发进行DFS遍历，直到所有结点都被访问。每一次调用DFS后都得到此非连通图的一个连通子图，调用DFS的次数就是连通子图的个数。八、网络G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。解：9、 下图是一个无向带权图，请给出该图的邻接矩阵，并分别按Prim算法和Kruskal算法求最小生成树（包括算法代码和画图）。10、代码：#include #i

34、nclude #include #include using namespace std;#define INFINITE 0xFFFFFFFF#define VertexData unsigned int /顶点数据#define UINT unsigned int#define vexCounts 6 /顶点数量char vextex = A, B, C, D, E, F ;struct node VertexData data;unsigned int lowestcost; closedgevexCounts; /Prim算法中的辅助信息typedef struct VertexDat

35、a u;VertexData v;unsigned int cost; /边的代价 Arc; /原始图的边信息void AdjMatrix(unsigned int adjMatvexCounts) /邻接矩阵表示法for (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 =

36、 0; i vexCounts; i+) if (closedgei.lowestcost min & closedgei.lowestcost !=0) min = closedgei.lowestcost;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.low

37、estcost = 0;for (int i = 0; i vexCounts; i+) /初始化辅助数组if (i != s) closedgei.data = s;closedgei.lowestcost = 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 vex

38、Counts; i+) /更新v中顶点最小代价边信息if ( adjMatki closedgei.lowestcost) closedgei.data = k;closedgei.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 =

39、adjMatij;vertexArc.push_back(*temp);bool compare(Arc A, Arc B) return A.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)