第七章 图
一、名词解释
1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历
7.图的最小生成树 8.拓扑排序填空题
1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但<x,y>与<y,x>是________的两条弧。
2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为________图，无序偶对用________括号括起来。
3.设x,y∈V，若<x,y>∈E,则<x,y>表示有向图G中从x到y的一条________，x称为________点，y称为________点。若（x,y）∈E，则在无向图G中x和y间有一条________。
4.在无向图中，若顶点x与y间有边（x,y），则x与y互称________，边（x,y）称为与顶点x和y________。
5.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。
6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。
7.无向图中的顶点V的度是________，记为________。若G是一个有向图，则把以顶点V为终点的弧的数目称为V的________，记为________；把以顶点V为始点的弧的数目称为V的________，称为________。有向图中顶点V的度定义为D（V）=________。
8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为________或________。
9.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。
10.连通分量是无向图中的________连通子图。
11.一个连通图的生成树是含有该连通图的全部顶点的一个________。
12.若连通图G的顶点个数为n，则G的生成树的边数为________。如果G的一个子图G’的边数________，则G’中一定有环。相反，如果G’的边数________，则G’一定不连通。
13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。
14.对于无向图的邻接矩阵，顶点vi的度是________________。对于有向图的邻接矩阵，顶点vi的出度OD（vi）为________________，顶点vi的入度ID(vi)是________________。
15.图的存储结构主要有________和________两种。
16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。
17.对无向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
18.对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
19.在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。
20.遍历图的基本方法有________优先搜索和________优先搜索两种。
21.以下是图的深度优先算法，请在________处填充适当的语句。
Dfs(GraphTp g,int v)
{ ArcNodeTp *p;
printf(“%d”,v);
visited[v]=1;
p=________________;
while(p!=NULL)
{if(!________________) Dfs(g,p->adjvex);
p=________________;
}
}
22.以下是图的广度优先搜索算法，请在________处填充适当的语句。
Bfs(GraphTp g,int v)
{QueptrTp Q;
ArcNodeTp *p;
InitQueue(&Q);
printf(“%d”,v);
visited[v]=1;
________________
while(!EmptyQueue(Q))
{________________;
p=g.adjlist[v].firstarc;
while(p!=NULL)
{if(!visited[p->adjvex])
{printf(“%d”,p->>adjvex);
visited[[->adjvex]=1;
EnQueue(&Q,p->adjvex);
}
________________;
}
}
}
23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________。
24.任何连通图的连通分量只有一个，即________。
25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连通图。
26.一个图的________的表示法是惟一的，而________表示法是不惟一的。
27.对无向图，其邻接矩阵是一个关于________对称的矩阵。
28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到第________个结点的入度。
29.________的有向图，其全部顶点有可能排成一个拓扑序列。
30.一个有向图G中若有弧,<Vi,Vj>、<Vj,Vk>和<Vi,Vk>,则在图G的拓扑序列中，顶点Vi、Vj和Vk的相对位置为________。
单项选择题
1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
①G’为G的子图 ②G’为G的连通分量
③G’为G的极小连通子图且V’=V ④G’是G的无环子图
2.任何一个带权的无向连通图的最小生成树（ ）
①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在
3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ）
①O(n) ②O(n+e) ③O(n*n) ④O(n*e)
4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ）
①1 ② n/2 ③ n-1 ④n
5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是 （ ）
①V1,V3,V2,V4,V5 ②V1,V3,V4,V2,V5 ③V1,V2,V3,V4,V5 ④V1,V3,V4,V5,V2
6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
①0.5 ②1 ③2 ④4
7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ）
①0.5 ② 1 ③ 2 ④4
8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历
9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历
10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ）
①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法
11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ）
①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3
12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ）
①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3
13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ）
① 5 ② 6 ③ 7 ④ 8
14.以下说法正确的是 （ ）
①连通图的生成树，是该连通图的一个极小连通子图。
②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。
③任何一个有向图，其全部顶点可以排成一个拓扑序列。
④有回路的图不能进行拓扑排序。
15以下说法错误的是 （ ）
①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。
③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了
③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。
16．以下说法正确的是 （ ）
①连通分量是无向图中的极小连通子图。
②强连通分量是有向图中的极大强连通子图。
③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。
④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。
四、简答及应用
1,简述图的邻接矩阵表示的类型定义
2,简述图的邻接表的类型定义。
3,给出无向图简答题3中g1的邻接矩阵和邻接表。
4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。
5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。
6．求出图简答题6-1的连通分量。
7．求出带权图简答题7-1的最小生成树
8．写出有向图简答题8-1的拓扑排序序列。
9．给出网图简答题9-1的邻接矩阵表示。
10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。
11．对于图简答题11-1从其邻接表中回答下列问题：
图中有多少条弧？
图中是否存在从i到j的弧？
如何求顶点i的出度？
12．图简答题11-1所示为一有向图，请给出该图的下述要求：
每个顶点的入/出度。
邻接矩阵。
邻接表。
逆邻接表。
13．拓扑排序的结果不是唯一的，对图简答题13-1进行拓扑排序，试写出其中任意5个不同的拓扑排序列。
14．对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题：
图中有多少条边？
任意两个顶点i和j是否有边相连？
任意一个顶点的度是多少？
15.已知图G的邻接表如图简答题15-1所试，顶点V1为出发点，完成要求：
深度优先搜索的顶点序列；
广度优先搜索的顶点序列；
由深度优先搜索得到的一棵生成树；
由广度优先搜索得到的一棵生成树。
Vertex fi
16.设有一无向图G=(V,E),其中V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。
按上述顺序输入后，画出其相应的邻接表；
在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。
五、算法设计写出将一个无向图的邻接矩阵转换成邻接表的算法。
写出将一个无向图的邻接表转换成邻接矩阵的算法。
试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。
写出建立一个有向图的逆邻接表的算法。
G为一n个顶点的有向图，其存储结构分别为：
邻接矩阵；
邻接表。
请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。
6．以邻接表作存储结构，给出拓扑排序算法的实现。
一、名词解释
1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历
7.图的最小生成树 8.拓扑排序填空题
1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但<x,y>与<y,x>是________的两条弧。
2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为________图，无序偶对用________括号括起来。
3.设x,y∈V，若<x,y>∈E,则<x,y>表示有向图G中从x到y的一条________，x称为________点，y称为________点。若（x,y）∈E，则在无向图G中x和y间有一条________。
4.在无向图中，若顶点x与y间有边（x,y），则x与y互称________，边（x,y）称为与顶点x和y________。
5.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。
6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。
7.无向图中的顶点V的度是________，记为________。若G是一个有向图，则把以顶点V为终点的弧的数目称为V的________，记为________；把以顶点V为始点的弧的数目称为V的________，称为________。有向图中顶点V的度定义为D（V）=________。
8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为________或________。
9.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。
10.连通分量是无向图中的________连通子图。
11.一个连通图的生成树是含有该连通图的全部顶点的一个________。
12.若连通图G的顶点个数为n，则G的生成树的边数为________。如果G的一个子图G’的边数________，则G’中一定有环。相反，如果G’的边数________，则G’一定不连通。
13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。
14.对于无向图的邻接矩阵，顶点vi的度是________________。对于有向图的邻接矩阵，顶点vi的出度OD（vi）为________________，顶点vi的入度ID(vi)是________________。
15.图的存储结构主要有________和________两种。
16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。
17.对无向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
18.对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
19.在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。
20.遍历图的基本方法有________优先搜索和________优先搜索两种。
21.以下是图的深度优先算法，请在________处填充适当的语句。
Dfs(GraphTp g,int v)
{ ArcNodeTp *p;
printf(“%d”,v);
visited[v]=1;
p=________________;
while(p!=NULL)
{if(!________________) Dfs(g,p->adjvex);
p=________________;
}
}
22.以下是图的广度优先搜索算法，请在________处填充适当的语句。
Bfs(GraphTp g,int v)
{QueptrTp Q;
ArcNodeTp *p;
InitQueue(&Q);
printf(“%d”,v);
visited[v]=1;
________________
while(!EmptyQueue(Q))
{________________;
p=g.adjlist[v].firstarc;
while(p!=NULL)
{if(!visited[p->adjvex])
{printf(“%d”,p->>adjvex);
visited[[->adjvex]=1;
EnQueue(&Q,p->adjvex);
}
________________;
}
}
}
23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________。
24.任何连通图的连通分量只有一个，即________。
25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连通图。
26.一个图的________的表示法是惟一的，而________表示法是不惟一的。
27.对无向图，其邻接矩阵是一个关于________对称的矩阵。
28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到第________个结点的入度。
29.________的有向图，其全部顶点有可能排成一个拓扑序列。
30.一个有向图G中若有弧,<Vi,Vj>、<Vj,Vk>和<Vi,Vk>,则在图G的拓扑序列中，顶点Vi、Vj和Vk的相对位置为________。
单项选择题
1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
①G’为G的子图 ②G’为G的连通分量
③G’为G的极小连通子图且V’=V ④G’是G的无环子图
2.任何一个带权的无向连通图的最小生成树（ ）
①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在
3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ）
①O(n) ②O(n+e) ③O(n*n) ④O(n*e)
4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ）
①1 ② n/2 ③ n-1 ④n
5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是 （ ）
①V1,V3,V2,V4,V5 ②V1,V3,V4,V2,V5 ③V1,V2,V3,V4,V5 ④V1,V3,V4,V5,V2
6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
①0.5 ②1 ③2 ④4
7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ）
①0.5 ② 1 ③ 2 ④4
8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历
9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历
10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ）
①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法
11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ）
①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3
12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ）
①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3
13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ）
① 5 ② 6 ③ 7 ④ 8
14.以下说法正确的是 （ ）
①连通图的生成树，是该连通图的一个极小连通子图。
②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。
③任何一个有向图，其全部顶点可以排成一个拓扑序列。
④有回路的图不能进行拓扑排序。
15以下说法错误的是 （ ）
①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。
③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了
③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。
16．以下说法正确的是 （ ）
①连通分量是无向图中的极小连通子图。
②强连通分量是有向图中的极大强连通子图。
③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。
④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。
四、简答及应用
1,简述图的邻接矩阵表示的类型定义
2,简述图的邻接表的类型定义。
3,给出无向图简答题3中g1的邻接矩阵和邻接表。
4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。
5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。
6．求出图简答题6-1的连通分量。
7．求出带权图简答题7-1的最小生成树
8．写出有向图简答题8-1的拓扑排序序列。
9．给出网图简答题9-1的邻接矩阵表示。
10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。
11．对于图简答题11-1从其邻接表中回答下列问题：
图中有多少条弧？
图中是否存在从i到j的弧？
如何求顶点i的出度？
12．图简答题11-1所示为一有向图，请给出该图的下述要求：
每个顶点的入/出度。
邻接矩阵。
邻接表。
逆邻接表。
13．拓扑排序的结果不是唯一的，对图简答题13-1进行拓扑排序，试写出其中任意5个不同的拓扑排序列。
14．对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题：
图中有多少条边？
任意两个顶点i和j是否有边相连？
任意一个顶点的度是多少？
15.已知图G的邻接表如图简答题15-1所试，顶点V1为出发点，完成要求：
深度优先搜索的顶点序列；
广度优先搜索的顶点序列；
由深度优先搜索得到的一棵生成树；
由广度优先搜索得到的一棵生成树。
Vertex fi
16.设有一无向图G=(V,E),其中V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。
按上述顺序输入后，画出其相应的邻接表；
在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。
五、算法设计写出将一个无向图的邻接矩阵转换成邻接表的算法。
写出将一个无向图的邻接表转换成邻接矩阵的算法。
试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。
写出建立一个有向图的逆邻接表的算法。
G为一n个顶点的有向图，其存储结构分别为：
邻接矩阵；
邻接表。
请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。
6．以邻接表作存储结构，给出拓扑排序算法的实现。
