第6章 图
1．选择题
CBCAA CDADD
2．填空题
（1）n-1
（2）1
（3）求矩阵第i列非0元素之和
（4）将矩阵第i行全部置为0
（5）1，0
（6）O(n)，O(e/n)，O(e)
（7）O(n2)，O(n)+O(e)，O(e)+O(n)
（8）O(n2)，O(e)
3．问答题
（1）G1为完全无向图时边最多，即G1最多有n(n-1)/2条边，G1为一棵树时边最少，即G1最少有n-1条。
G2为完全有向图时边最多，即G2最多有n(n-1)条边，G2构成一个首尾相连的环时边最少，即G2最少有n条边。
（2）邻接矩阵适合于稠密图，因为它较紧凑，并且可以快速访问。邻接表适合于稀疏图，因为它很容易地插入和删除边。
（3）各问题判断如下：
①对于邻接矩阵表示的无向图，图中的边数等于矩阵中为1的元素个数除以2；对于邻接表表示的无向图，图中的边数等于边节点的个数除以2。对于邻接矩阵表示的无向图，图中的边数等于矩阵中为1的元素个数；对于邻接表表示的有向图，图中的边数等于边节点的个数。
②对于邻接矩阵表示的无向图或有向图，任意两个顶点i和j，邻接矩阵edges[i][j]为1表示有边相连；否则为无边相连。对于邻接表表示的无向图或有向图，任意两个顶点i和j，若从表头节点g->adjlist[i]出发找到顶点编号为j的边节点，表示有边相连；否则为无边相连。
③对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素等于1的个数；对于邻接矩阵表示的有向图，顶点i的出度等于第i行中元素等于1的个数；入度等于第i列中元素等于1的个数；度数等于它们之和。对于邻接矩阵表示的无向图，顶点i的出度等于g->adjlist[i]为头节点的单链表中节点的个数；入度需要遍历各顶点的边表，若g->adjlist[k]为头节点的单链表中存在顶点编号为i的节点，则顶点i的入度增1；度数等于它们之和。
（4）图G对应的邻接矩阵和邻接表两种存储结构分别如图A-8和图A-9所示。对于图A-9所示的邻接表，从顶点1出发的深度优先遍历和广度优先遍历序列都是12345。
图A-8 一个邻接矩阵
|
1 |
|
2 |
|
3 |
|
4 |
∧ |
|
|
| |||
|
2 |
|
1 |
|
3 |
|
5 |
∧ |
|
|
| |||
|
3 |
|
1 |
|
2 |
|
4 |
|
5 |
∧ | ||||
|
4 |
|
1 |
|
3 |
|
5 |
∧ |
|
|
| |||
|
5 |
|
2 |
|
3 |
|
4 |
∧ |
|
|
|
图A-9 一个邻接表
（5）根据有向图可知：
①邻接矩阵如图A-10所示。
②邻接表如图A-11所示。
③强连通分量如图A-12所示。
④从顶点1出发的深度优先遍历序列为142356。
⑤从顶点3出发的广度优先遍历序列为345612。
图A-10 一个邻接矩阵 图A-11 一个邻接表
图A-12 强连通分量
（6）Aov网B的关键路径如图A-13所示。
图A-13 Aov网B的关键路径
4．上机操作题
（1）给定邻接矩阵g，先创建邻接表G，给g.n个头节点置初值。扫描邻接矩阵g，对于不为0的权值g.edges[i][j]，创建一个节点，其value域值置为g.edges[i][j]，adjvex域值置为j，将其插入到G->adjlist[i]为头节点的单链表开头。最后设置G->n和G->e值。对应算法如下：
void MatToList(AdjMatix g,AdjList *&G) /*将邻接矩阵g转换成邻接表G*/
{
int i,j;
ArcNode *p;
G=(AdjList *)malloc(sizeof(AdjList));
for(i=0;i<g.n;i++) /*给邻接表中所有头节点的指针域置初值*/
{
G->adjlist[i].firstarc=NULL;
strcpy(G->adjlist[i].data,g.vexs[i].data);
}
for(i=0;i<g.n;i++) /*检查邻接矩阵中每个元素*/
for(j=g.n-1;j>=0;j--)
if(g.edges[i][j]!=0) /*邻接矩阵的当前元素不为0*/
{
p=(ArcNode *)malloc(sizeof(ArcNode)); /*创建一个节点*p*/
p->value=g.edges[i][j];p->adjvex=j;
p->next=G->adjlist[i].firstarc; /*将*p链到链表后*/
G->adjlist[i].firstarc=p;
}
G->n=g.n;G->e=g.e;
}
（2）算法如下：
void outdegree(ALGraph *G)
{
intod,i;Enode *p;
for(i=0;i<G->n;i++)
{
od=0;
p=G->adjlist[i].firste;
}
while(p)
{
od + +;
p=p->next;
}
printf("Vexno:%d,outdegree=%d,I,od");
}
（3）算法如下：
void listtomatrix (ALGraph *g1,MGraph *g2)
{
int i,j;
Enode *p;
g2->n=g1->n,
g2->e=g1->e;
for(i=0;i<n;i++)
for(j=0; j<n; j++)
g2->edges[i][j]=0;
for(i=0;i<n;i++)
{
g2->Vexs[i]=g1->adjlist[i].data;
p=g1->adjlist.firste;
while(p)
{
g2->edges[i][p->adjvex]=1;
p=p->next;
}
}
}
（4）采用深度优先搜索算法求从顶点u到v的简单路径算法如下，其中printuv函数的功能是输出从u到v的简单路径。
void printuv(int u,int v)
{
int k;
if(path[v]==-1)
{
printf("\nu->v no path");
return;
}
printf("\nu->v path:%d",v);
for(k=path[v];k!=u;k=path[k])
printf("<-%d",k);
printf("<-%d",u);
}
void dfsp(ALGraph *g,int u,int v)
{
int j;
Enode *p;
visited[u]=1;
for(p=g->adjlist[u],firste;p;p=p->next)
{
if(u= =v)return;
if(visited[p->adjvex]= =0)
{
j=p->adjvex;
path[j]=u;
dfsp(g,p->adjvex,v);
}
}
}
void uvpath(ALGraph*g,int u,int v)
{
int i;
for(i=0;i<g->n;i++)
{
visited[i]=0;path[i]=-1;
}
dfsp(g,u,v);
printuv(u,v);
}