第7章图
本章主要内容：
1、图的定义
2、图的存储结构
3、图的遍历操作
4、图的几个典型应用问题
本章重点难点：
1、图的遍历操作
2、典型应用问题
7.1 图的定义与基本操作
7.1.1 图的定义及有关术语
1. 图的定义
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
图 7-1 图的图形表示
在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作
若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和
2. 图的有关术语
与顶点v相关的边的条数称作顶点v的度。从顶点v到顶点u所经过的各条边构成的集合称为一条路径。路径上边或弧的数目称为路径长度。若第一个顶点和最后一个顶点相同，则这条路径是一条回路。若路径中顶点没有重复出现，则称这条路径为简单路径。
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
2．图的基本操作
（1）创建一个图结构 CreateGraph(G)
（2）检索给定顶点 LocateVex(G,elem)
（3）获取图中某个顶点 GetVex(G,v)
（4）为图中顶点赋值 PutVex(G,v,value)
（5）返回第一个邻接点 FirstAdjVex(G,v)
（6）返回下一个邻接点 NextAdjVex(G,v,w)
（7）插入一个顶点 InsertVex(G,v)
（8）删除一个顶点 DeleteVex(G,v)
（9）插入一条边 InsertEdge(G,v,w)
（10）删除一条边 DeleteEdge(G,v,w)
（11）遍历图 Traverse(G,v)
7.2 图的存储结构
7.2.1 邻接矩阵存储结构
1．无向图的邻接矩阵
具有n个顶点的有向图可以用一个nⅹn的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。例如：如图7-2的邻接矩阵所示。
图 7-2 一个无向图及其邻接矩阵
2．无向图的邻接矩阵
具有n个顶点的无向图也可以用一个nⅹn的方形矩阵表示。假设该矩阵的名称为M，则当
图7-3 一个有向图及其邻接矩阵
3．邻接矩阵存储结构定义
在C 语言中，实现邻接矩阵表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 20
typedef struct graph{
Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
} Graph;
7.2.2 邻接表存储结构
1. 邻接表结构
边结点的结构定义是
adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针。如图7-4
图 7-4 图7-2的邻接表
其中elme是顶点内容，firstedge是指向第一条边或弧结点的指针。
2．邻接表结构定义
在C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeLinklist{ //边结点
int adjvex;
struct EdgeLinklist *next;
} EdgeLinklist;
typedef struct VexLinklist{ //顶点结点
Elemtype elem;
EdgeLinklist *firstedge;
} VexLinklist,AdjList[MAX_VERTEX_NUM];
7.2.3 有向图和无向图邻接表的创建算法
1．创建有向图邻接表
void Create_adj(AdjList adj, int n) {
for (i=0;i scanf(&adj[i].elem); adj[i].firstedge=NULL; } scanf(&i,&j); //输入弧 while (i) { s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); //创建新的弧结点 s->adgvex=j-1; s->next=adj[i-1].firstedge; //将新的弧结点插入到相应的位置 adj[i-1].firstegde=s; scanf(&i,&j); //输入下一条弧 } } 2．创建无向图的邻接表 void Create_adj(AdjList adj, int n) { for (i=0;i scanf(&adj[i].elem); adj[i].firstedge=NULL; } scanf(&i,&j); //输入边 while (i) { s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); s1->adgvex=j-1; s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); s2->adgvex=i-1; s1->next=adj[i-1].firstedge; adj[i-1].firstegde=s1; s2->next=adj[j-1].firstedge; adj[j-1].firstegde=s2; scanf(&i,&j); } } 7.3 图的遍历 常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。 7.3.1 深度优先遍历 1．算法思想 深度优先遍历的基本思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。 2．算法实现。 为了便于在算法中区分顶点是否已被访问过，需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来设置访问标志，其初始值visited[i]（0≤i≤n-1）为"0"，表示邻接表中下标值为i的顶点没有被访问过，一旦该顶点被访问，将visited[i]置成"1"。 int visited[0..n-1]={0,0,...0}; void DFS(AdjList adj,int v) { //v是遍历起始点的在邻接表中的下标值，其下标从0开始 visited[v]=1; visite(adj[v].elem); for (w=adj[v].firstedge;w;w=w->next) if (!visited[w->adjvex]) DFS(adj,w->adjvex); } 对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测： int visited[0..n-1]={0,0,...0}; void DFSTraverse(AdjList adj) { for (v=0;v } 7.3.2 广度优先遍历 1．算法思想 对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接 点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。 下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题： （1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的 邻接点。 （2）应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；（3）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。 2．算法实现 int visited[0..n-1]={0,0,...0}; void BFS(AdjList adj,int v) { //v是起点的下标，下标从0开始 InitQueue(Q); //Q是队列 visited[v]=1; visite(adj[v].elem); EnQueue(Q,v); while (!QueueEmpty(Q)) { DeQueue(Q,v); for (w=adj[v].firstedge;w;w=w->next) if (!visited[w->adjvex]) { visited[w->adjvex]=1; visite(adj[w->adjvex].elem); EnQueue(Q,w->adjvex); } } } 7.4 最小生成树问题 7.4.1 图的生成树和森林 对于一个拥有n个顶点的无向连通图，它的边数一定多余n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。图7-5显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。 图7-5 无向连通图的生成树 图7-6 深度生成树和广度生成树 2．最小生成树 在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。 图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边。如图7-7所示 图 7-7 网和网的两个生成树 下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。 生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。 用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有n 个顶点、n-1 条边。 构造最小生成树，要解决以下两个问题： 1.尽可能选取权值小的边，但不能构成回路。 2.选取n-1条恰当的边以连接网的 n个顶点。 1 构造最小生成树的克鲁斯卡尔 (Kruskal) 算法 克鲁斯卡尔算法的基本思想：设有一个有n 个顶点的连通网络N = { V, E },最初先构造一个只有n 个顶点，没有边的非连通图T = { V, }, 图中每个顶点自成一个连通分量。当在E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T 中；否则将此边舍去， 重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。 下图是用克鲁斯卡尔算法构造最小生成树的过程： (a) (b) 图7-8 Kruskal 算法生成最小生成树过程 克鲁斯卡尔算法的形式描述如下： T = (V, φ)； While ( T 中所含边数 < n-1 ) { 从E中选取当前最短边 (u,v); 从E中删除边(u,v); if ((u,v) 并入T之后不产生回路 ) 将边 (u,v) 并入T中； } Kruskal算法 typedef Struct｛ int v1，v2； int len； }edgetype； /* 边的类型：两个端点号和边长*/ int parent[nmax+1]；/*结点双亲的指针数组，设为全局量，nmax为结点数最大值*/ int getroot（int v） /*找结点v所在的树根*/ ｛ int i； i = v； while（parent[i]>0）i = parent[i]； return i； /*若无双亲（初始点），双亲运算结果为其自己*/ ｝ int getedge（edgetype em [ ]，int e） /*找最短边，e为边数*/ ｛int i, j, min = 0; for (i =1 ; i<= e ; i++) if (em [i-1].len return min； ｝ void kruskal（edqetype em [ ]，int n，int e） /*n为结点数，e 为边数*/ ｛int i，p1，p2，m，i0； for（i=1；i<= n；i++）/*初始结点为根，无双亲*/ parent[i ] = -1； /*以后用于累计结点个数，此初值不能置为0*/ m = 1； while（m< n） ｛i0 = getedge（em，e）； /*获得最短边号*/ p1= getroot（em [i0].v1）； p2= getroot（em [i0].v2）; if（p1= = p2）continue； /*连通分量相同，不合并*/ if（p1>p2）｛ parent［p2］= parent［p1］＋parent［p2］；/*p2的双亲中累计结点总数（为负值）*/ parent[pl]= p2； /*p1成为p2的孩子 ｝ else｛ parent[ p1]= parent[p1]＋parent[p2]; parent[p2]= p1; ｝ m++； printf (“%d%d%d\n”，m，em[i0].v1，em [i0].v2 )； ｝ ｝ 算法分析 用Kruskal 算法构造最小生成树的时间复杂度为O （eloge ），与网中边的数目e 有关，因此，它适用于求稀疏图的最小生成树。 2 构造最小生成树的普里姆(Prim)算法： 普里姆算法的基本思想：从连通网络 N = { V , E }中的某一顶点 u 0 出发，选择与它关联的具有最小权值的边(u 0, v )，将其顶点加入到生成树的顶点集合U 中。以后每一步从一个顶点在U 中，而另一个顶点不在U 中的各条边中选择权值最小的边(u , v ),把它的顶点加入到集合U 中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U 中为止。 用普里姆算法构造最小生成树的过程如图7-9所示。 (a) (b) (c) (d) (e) (f) 图7-9 Prim算法生成最小生成树过程 Prim算法的形式描述如下： 置T为任意一个顶点； 求初始候选边集； while（T中结点数＜n） ｛从候选边集中选取最短边（u，v）； 将（u，v）及顶点v，扩充到T中； 调整候选边集； ｝ Prim算法： void prim（graph *g，int u） { int v，k，j，min； for (v =1；v<=g->n；v++) if（v ! = u） ｛minedge[v].end=u； minedge[v].len = g->edges[v][u]；｝ minedge[u].len = 0； for（ k = 1；k< g->n；k++） ｛min = minedge[k].len ； v = k ； for （j =1；j if （minedge[j].len>0&&minedge[j].len if （min=INTMAX ） { printf ( “ 图不连通，无生成树！” ) ； return(0)； } printf(“%d %d”,v, minedge[v].end)； minedge[v].len = -minedge[v].len ； for(j ＝1；j<=g->n ；j++) if （g-> edges [j][v] minedge[j].end = v ； ｝ ｝ ｝ 算法分析 上述算法的初始化时间是O(1)，k 循环中有两个循环语句，其时间大致为： ∑∑∑∑∑ -=-+=-=-=-=≈+221 202 20 )1(2))1()1(n k j n k j n k n k j n k O O O （ 令O(1)为某一正常数C，展开上述求和公式可知其数量级仍是 n 的平方。所以，整个算法的时间复杂性是O(n2) 7.5 拓扑排序与关键路径问题 7.5.1 拓扑排序问题 拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列 vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。 举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。如图7-10所示： 图7-10 课程之间先修关系图 拓扑排序的方法： （1）从图中选择一个入度为0的顶点且输出之； （2）从图中删掉该顶点及其所有以该顶点为弧尾的弧； 反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。 实现拓扑排序的算法。假设有向图以邻接表的形式存储。 基本过程： { 将所有入度为0的顶点入栈； 当栈非空时重复执行下列操作： 从栈中退出顶点k； （1）将k顶点的信息输出； （2）将与k邻接的所有顶点的入度减1。 } #define MAX_VERTEX_NUM 30 //最大顶点个数 type struct EdgeLinklist{ //边结点 int adjvex; struct EdgeLinklist *next; }EdgeLinklist; typedef struct VexLinklist{ //顶点结点 Elemtype elem; int indegree; //记录顶点的入度 EdgeLinklist *firstedge; }VexLinklist,AdjList[MAX_VERTEX_NUM]; 拓扑排序的完整算法。 Status TopologicalSort(AdjList adj) {InitStack(s); for (i=0;i if (adj[i].indegree==0) Push(s,i); while (!StackEmpty(s)) { Pop(s,i); printf(i); for (p=adj[i].firstedge;p;p=p->next) { adj[i].indegree-=1; if (adj[i].indegree==0) Push(s,i); } } } 算法分析： 设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)，所以总的时间复杂度为O(n+e)。 7.5.2 关键路径问题* 1．AOE网（Activity on edge network） 若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 AOE网具有以下两个性质： （1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 （2）只有在进入一某顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。对于AOE网，可采用与AOV网一样的邻接表存储方式。其中，邻接表中边结点的域为该边的权值，即该有向边代表的活动所持续的时间。 下图7-11给出了一个具有15个活动、11个事件的假想工程的AOE网。 图7-11 AOE网 v1,v2,… v11分别表示一个事件； 2．关键路径 由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为源点到终点的最大路径长度（这里的路径长度是指该路径上的各个活动所需时间之和）。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。这就是说，要缩短整个工期，必须加快关键活动的进度。 利用AOE网进行工程管理时要需解决的主要问题是： （1）计算完成整个工程的最短路径。 （2）确定关键路径，以找出哪些活动是影响工程进度的关键。 3. 关键路径的确定 为了在AOE网中找出关键路径，需要定义几个参量，并且说明其计算方法。 （1）事件的最早发生时间ve[k] 第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。 数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题： 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量 1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧 关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B） 数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧 (4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径 习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n 11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。 习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。《数据结构》习题汇编07 第七章 图 试题
数据结构第七章图
数据结构第7章 图习题
数据结构第七章图练习及答案
数据结构第七章图练习及答案
数据结构第7章 图习题
数据结构第七章图练习及答案
数据结构第7章 图习题
相关主题
文本预览