第8章 图
第8章 图
知识巩固
一．填空题
1．一个连通无向图有5个顶点8条边，则其生成树将要去掉 4 条边。
2．在树结构与图结构中，前驱和后继结点之间分别存在着 1：1 和 1：n 的联系。
3．有n 个顶点的连通图中至少有 n 条边。
4．如果不知一个图是无向图还是有向图，但知道它的邻接矩阵是非对称的，那么这个图必须是_ 有向图_____。
5．在无向图G 的邻接矩阵A 中，有A[I][J]=1，则A[J][I]= 1 。 6．无向图的邻接矩阵A 中所有元素之和表示无向图的边数的 2倍 。
7．无向图的邻接表中所有边表结点之和表示无向图的边数的所有顶点度之和__2倍___。
8．图的遍历方式一般有_深度优先遍历_____和_广度优先遍历_____两种。
9．如果一个有向图的所有顶点可以构成一个拓扑序列，则说明该有向图_存在回路_____。
10．有向图用邻接表存储，则i v 顶点的出度为 1 。
二．选择题
1．在一个无向图中，所有顶点度数之和等于所有边数的（ B ）倍。 A ．1 B ．2 C ．3 D ．4
2．若无向图的顶点数为n ，则该图最多有（ B ）条边。 A ．n-1 B ．n+2 C ．(1)2
n n - D ．(1)2
n n +
3．（ B ）的邻接矩阵是对称矩阵。
A ．有向图
B ．无向图
C ．AOV 网
D ．AO
E 网
4．在有向图的邻接表存储结构中，顶点V 在链表结点出现的次数是（ C ） A ．顶点V 的度 B ．顶点V 的出度 C ．顶点V 的入度 D ．都不对 5．有向图G 的拓扑序列中，若顶点i v 在顶点j v 之前，则下列情形不能出现的是（ D ）
A ．G 中有弧
B ．G 中有一条从i v 到j v 的路经
C ．G 中没有弧
D ．G 中有一条从j v 到i v 的路经
6．在图的存储结构表示中，表示形式唯一的是（ B ） A ．邻接矩阵表示方法 B ．邻接表表示方法
C ．逆邻接表表示方法
D ．邻接表与逆邻接表表示方法
7．有n 个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元
素的之和的（ A ）
A ．一半
B ．2 倍
C ．3倍
D ．1倍
8．无向图G=（V ，E ）其中V={a, b, c, d, e, f}，E={（a, b ）, （a, e ）, （a, c ）, （b, e ）, （c, f ）, （f, d ）, （e, d ）}则对该图进行深度优先遍历，得到的序列正确的是（ D ）
A ．abcedf
B ．acfebd
C ．aebcfd
D ．aedfcb
三．简答题
1．已知有向图的邻接矩阵为n n A ?,试问每个(k)n n A ?（k=1,2,3,….,n）各具有何种 实际意义?
[参考答案]
记（a
(k ）
ij
）=(k)n n A ?,则（a
(k ）
ij
）为由i 到是的长度为k 的路径数。注意，不能理解
为简单路径。
2．对n 个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列 有关问题?
(1)图中有多少条边?
(2)任意两个顶点i 和j 是否有边相连? (3) 任意一个顶点的度是多少? [参考答案]
（1）无向图中边的条数为邻接矩阵非零元素之和的一半或邻接表中邻接结点个数和的一半，有向图中边的条数为邻接矩阵非零元素之和或邻接表中邻接结点个数
（2）在无向图中，当两个顶点i 和j 有边相连时，邻接矩阵n n A ?中aij=1同时aji=1，邻接表顶点i 有邻接顶点j 同时顶点j 有邻接顶点i 。
在有向图中，当两个顶点i 和j 有边相连时，邻接矩阵n n A ?中aij=1或者aji=1，邻接表顶点i 有邻接顶点j 或者顶点j 有邻接顶点i 。
（3）在无向图中，第i 个顶点的度在邻接矩阵n n A ?中表示为a i0+a i1+…a in-1,在邻接表中顶点的度为第i 个顶点的邻接点的个数。
在有向图中，第i 个顶点的度在邻接矩阵 中表示为a i0+a i1+…a in-1,在邻接表
中顶点的度为第i 个顶点的邻接点的个数。
实训演练
一．综合应用题
1.请回答下列问题；
（1）n 个顶点的连通图至少要有几条边？
（2)在无向图中，所有顶点的度之和与边数有何关系？
（3）在一个有向图中，所有顶点的入度之和与所有顶点的出度之和有何关系? （4）具有4个顶点的有向完全图有多少条有向边？ [参考答案]
1) 至少有n-1条边
2) 所有顶点的度之和等于边数的２倍
3) 在有向图中，所有顶点的入度之和等于所有顶点的出度之和 4) 有向边数=４*(4-1)=12
2.分别给出有向图G1的邻接矩阵、邻接表与逆邻接表。
图 G 1
V 1
V 2
V 3
V 4V 5
图 G 2
V 1
V 2
V 3V 4
V 5
1
1
2
2
2
3
3
5
图 G 3
图G1 图G2 图G3
[参考答案] 邻接矩阵为：
???????
?????????=00
1
1
0000000000
0000001110A
邻接表为：
逆邻接表为：
3.分别给出图G2从v5出发按深度优先搜索遍历与广度优先搜索遍历的顶点序列。[参考答案]
从v5出发深度优先搜索序列为：v5v3v2v1v4
从v5出发广度优先搜索序列为：v5v3v4v1v2
4.求出网G3的最小生成树。
[参考答案]
最小生成树为
V1V2
V3
V4
V5
1
1
2
2
5.试编一个算法，求出一个用邻接表表示的有向图中每个顶点的入度。
[参考答案]
1)邻接表类型及变量说明
# define n 6 /*图的顶点个数*/
# define null 0
# define len sizeof(point)
typedef
struct node
{ int adjvex；
struct node *next ；
｝point ；
typedef
struct hnode
{ int vexter ；
point *link ；
}head ；
head ga[n+1]；/*邻接表向量*/
int indeg[n+1]； /*入度向量*/
2) 已知有向图的邻接表ga求入度向量indeg 算法( 其中indeg[k]表
示第k个顶点的入度)。
void deg ( head ga[ ]，indeg[ ] )
{ int k，j；
point *p；
for(k=1；k<=n；k++)
indeg[k]=0；
for(k=1；k<=n；k++)
{ p=ga[k].link；
while (p)
{ j=p->adjvex；indeg[j]++；
p=p->next；
}
}
}
6.请求出图G4给出的有向图所有可能的拓扑序列。
图G4
图 G4
[参考答案]
所有可能的拓朴序列为：
1) v1v4v5v3v2v6
2) v4v1v5v3v2v6
3) v1v4v3v5v2v6
4) v4v5v1v3v2v6
5) v4v1v3v2v5v6
6) v1v4v3v2v5v6
二．算法设计题
1．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
[参考答案]
#define MAXN 50
#define MAXM 100
struct l_node{int ver;
struct l_node *link;};
typedef struct l_node L_NODE;
typedef struct {int ver1;
int ver2;}E_NODE;
L_NODE *head[MAXN];
int visit[MAXN];
E_NODE e[MAXM];
int n,m,u;
void create_adj_list(head,n,e,m)//
L_NODE *head[];
E_NODE e[];
int n,m;
{int i,u,v; L_NODE *p;
for(i=1;i<=n;i++)
head[i]=NULL;
for(i=0;i { u=e[i].ver1; v=e[i].ver2; p=(L_NODE*)malloc(sizeof(L_NODE)); p->ver=v; p->link=head[u]; head[u]=p;} } 2．采用邻接表存储结构，编写一个判断无向图中任意给定的两个顶点之间是否存在一条长度为K的简单路径的算法。（注：一条路径为简单路径指的是其顶点序列中不能含有重现的顶点） [参考答案] int visited[MAXSIZE]; int Exist_path_len(head ga[ ],int i,int j,int k)//判断邻接表方式存 储的有向图G的顶点i到j是否存在长度为k的简单路径 { if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=ga[i].link;p;p=p->next) { l=p->adjvex; if(!visited[l]) if(Exist_path_len(ga,l,j,k-1)) return 1; //剩余路径长度减一 } visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 } return 0; //没找到} 3．编写连通图的深度优先搜索非递归算法。 [参考答案] void Dfs(head ga[ ]，int v) { point *p； printf(“%d”，v)； visted[v]=1； p=ga[v].link； while (p) { if (!visted[p->adjvex]) Dfs(ga，p->adjvex)； p=p->next； ｝｝