习题7
1）选择题
（1）图中有关路径的定义是（A）。
A．由不同顶点所形成的序列
B．由顶点和相邻顶点对构成的边所形成的序列
C．由不同边所形成的序列
D．上述定义都不是
（2）设无向图的顶点个数为n，则该图最多有（B）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2
（3）一个n个顶点的连通无向图，其边的个数至少为（A）。
A．n-1 B．n C．n+1 D．n log2n
（4）要连通具有n个顶点的有向图，至少需要（B）条边
A．n-1 B．n C．n+1 D．2n
（5）n个结点的完全有向图含有边的数目为（D）。
A．n2B．n(n+1) C．n/2 D．n(n-1)
（6）一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。
A．0 B．1 C．n-1 D．n
（7）在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。
A．1/2 B．2 C．1 D．4
（8）下面结构中最适于表示稀疏无向图的是（C），适于表示稀疏有向图的是（BDE）。
A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表
（9）下列哪些图的邻接矩阵是对称矩阵（B）。
A．有向图B．无向图C．有向网D．无向网
（10）下列有关图遍历的说法不正确的是（C）。
A．连通图深度优先搜索是个递归过程
B．图的广度优先遍历中邻接点的搜索具有“先进先出”的特征C．非连通图不能用深度优先搜索
D．图的遍历要求每个顶点仅被访问一次
（11）某图的邻接表如图7-26所示。
1
2
3
4
5
6
7
图7-26 某图的邻接表
①从顶点v1进行深度优先遍历，遍历过程中要经过的顺序是（A）。
A．v1v2v3B．v1v3v4C．v1v2v4D．v1 v3v5
②从顶点v1进行广度优先遍历，遍历过程中要经过的顺序是（D）。
A．v1v2v3B．v1v3v4C．v1v2v4D．v1 v3v5
（12）一个加权无向连通图的最小生成树（A）。
A．有一棵或者多棵B．只有一棵
C．一定有多棵D．可能不存在
2）判断题
（1）在n个结点的无向图中，若边数大于n-1，则该图必是连通图。
（×）
（2）有e条边的无向图，在邻接表中有e个结点。
（×）
（3）有向图中顶点v的度等于其邻接矩阵中第v行中1的个数。
（×）
（4）强连通图的各顶点间均可达。
（√）
（5）邻接多重表是无向图和有向图的链式存储结构。
（×）
（6）用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
（×）
（7）有n个顶点的无向图，采用邻接矩阵表示，图中的边数等
于邻接矩阵中非零元素之和的一半。
（√）
（8）求最小生成树的普里姆（Prim）算法中边上的权可正可负。
（×）
3）填空题
（1）判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图__。
（2）一个连通图的___生成树_________是一个极小连通子图。
（3）具有10个顶点的无向图，边的总数最多为____45________。
（4）G是一个非连通无向图，共有28条边，则该图至少有_____9_______个顶点。
（5）在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__n___条弧。
（6）如果含n个顶点的图形形成一个环，则它有_____n______棵生成树。
4）解答题
（1）按图7-26的邻接表分别写出从v6出发进行广度优先和深度优先遍历序列。
广度优先：v6 v5 v7 v0 v2 v3 v1 v4
深度优先：v6 v5 v7 v0 v2 v3 v1 v4
（2）证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。
证明：具有n个顶点n-1条边的无向连通图是自由树，即没
有确定根结点的树，每个结点均可当根。
若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。
形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。
（3）画出如图7-27所示的无向网的最小生成树。
v 2v 1v 3v 4
v 5v 6v 7
v 8
13
2265424
31
图7-27 某无向网
（略）
（4）按照Prim 算法，写出从顶点v 2开始构造图7-26的最小生成树的过程。
（略）
（5）按照Sollin 算法，写出构造图7-26的最小生成树的过程。
（略）
（6）按照Dijkstra 算法，写出求图7-26的顶点v 0到其他各个结点的最短路径过程中数组dist 和pre 各分量的变化情况表。
（略）
5）算法题
（1）以邻接多重表作存储结构，写出创建图的算法。
void CreatGraph (AdjList g) //建立有n个顶点和m 条边的无向图的邻接表存储结构
{
int n,m;
scanf("%d%d",&n,&m);
for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量
{scanf(&g[i].vertex); g[i].firstarc=null;}
for (k=1;k<=m;k++)//输入边信息
{
scanf(&v1,&v2);//输入两个顶点
i=GraphLocateVertex (g,v1);
j=GraphLocateVertex (g,v2); //顶点定位
p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点
p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=i;
p->next=g[j].firstarc;
g[j].frstarc=p;
}
}//算法CreatGraph结束
（2）设有向G图有n个点，e条边，编写一个算法根据其邻接表生成其反向邻接表，要求算法复杂度为)
O 。
n
(e
void InvertAdjList(AdjList gin,gout）//将有向图的出度邻接表改为按入度建立的逆邻接表
{
for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。
{gin[i].vertex=gout[i].vertex; gin.firstarc=null; } for (i=1;i<=n;i++) //邻接表转为逆邻接表。
{
p=gout[i].firstarc;//取指向邻接表的指针。
while (p!=null)
{
j=p->adjvex;
s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。
s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s;
p=p->next;//下一个邻接点。
}//while
}//for
}
（3）用Floyd算法，求图7-26中任意顶点之间的最短路径。
（略）。