计算机组成原理第七章补充习题

（2） 任意两个顶点I和j是否有边相连？ （3） 任意一个顶点的度是多少？ 解：

1 对于无向图 （1） 图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的一半。

（2） 若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。

（3） 顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j. 2 对于有向图

（1） 图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。 （2） 若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连 ；

邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。

（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；

邻接表中i得出边表结点个数加上边表中结点I的个数之和。

2、 n个顶点的连通图至少有几条边？强连通图呢？ 解：

①n个顶点的连通图至少有n-1条边。 ②n个顶点的强连通图至少有n条边。 3、 DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？ 解：

①DFS采用了栈；BFS采用了队列。 ②采用BFS。

4、按顺序输入顶点对：（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序列，及DFS和BFS生成树。 解：

依题意构造有向图： ①邻接表

②DFS和BFS序列 DFS序列：4 5 3 1 6 2 BFS序列：4 5 3 6 1 2 ③DFS和BFS生成树 DFS生成树 BFS生成树

5、什么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成树的时间各为多少？他们分别适合于哪个图？

解：①具有n的结点，n-1条边的连通图其生成树是唯一的。

n个结点， e条边的无向连通图求最小生成树的时间分别为

Prim: O(n2); Kruskal:O(e*loge)

Prim适应于稠密图（点少边多）；Kruskal 适应于稀疏图（点多边少）。

6、什么样的DAG的拓扑序列是唯一的？ 解：

设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。

算法设计题

1、 试在无向图的邻接矩阵和邻接表上实现如下算法：

（1） 往图中插入一个顶点 （2） 往图中插入一条边 （3） 删去图中某顶点 （4） 删去图中某条边 解：

（1） 插入给定结点 1 邻接表

viod Inser-ALGraph(ALGraph *G,int k)

{ int i; G->n++;

for(i=G->n;i>k;i--) {

G->adjlist[i].vertex=G->adjlist[i-1].vertex;

G->adjlist[i].firstedge=G->adjlist[i-1].Firstedge; }

G->adjlist[i].vertex=getchar(); G->adjlist[i].firstedge=Null; }

② 邻接矩阵

void Inser-Mgraph (mGraph *G,int k) {int i,j; G->n++;

for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1]; G->cexs[k]=getchar(); for(i=G->n;i>k;i--) { for(j=G->n;j>k;j--)

G->e[i][j]=G->e[i-1][j-1]; G->e[i][j]=0;

for(j=k-1;j>=0;j--)

G->e[i][j]=G->e[i-1][j]; }

for(j=G->n;j>=0;j--)G->e[i][j]=0; for(i=k-1;i>=0;j--) { for(j=g->n;j>k;j--) G->e[i][j]=G->e[i][j-1]; G->e[i][j]=0 } }

⑵插入一条边 1 邻接表

InsertLAGraph (ALGraph *G,int m,INT n) { EdgeNode *E;

EdgeNode *sm=new EdgeNode; EdgeNode *sn=new Edgenode; Sm->adjvex=n;sm->next=Null; Sn->adjvex=m;sn->next=Null;

for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next) { } E=sm;

for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next) { } E=sn; }

2 邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) { G->e[m][n]=1; }

（3）删除某结点 1 邻接表

void DelVALGraph(ALGraph *g,int k) { int I; G->n--;

EdgeNode *e *s;

for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next) { for (s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next)

if(s->adjvex==k) {s=s->next;break;} }

for(i=k;in;i++)

{ G->adjlist[i].vertex=G->adjlist[i+1].vextex;

G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge; } }

2 邻接矩阵

void delvMGraph(mGraph *G,int k) {int i,j; G->n--;

for(i=k;i<=g->n;i++) G->vexs[i]=G->vexs[i+1]; for(i=0;ifor(j=k;j<=n;j++) G->e[i][j]=G->e[i][j]; for(i=k;i<=G->n;i++)

{for(j=0;je[i][j]=G->e[i+1][j]; for(j=k;j<=n;j++) G->e[i][j]=G->e[i+1][j]; } }

(4)删除某条边

○

1 邻接表 void dellALGraph(ALGraph *G,int m,int n) {EdgeNode *s;

for(S=G->adjlist[m].firstedge;

s->adjvex!=k;s=s->next) s=s->next; for(s=G->adjlist[n].firstedge;

s->adjvex!=k;s=s->next) s=s->next; }

②邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) {G->e[m][n]=0; G->e[n][m]=0; }

2、 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(I<>j)之间是否有路径。 解：

/*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex; int vertex;

setuct node *list; } vertexNode

vertexNode *head[maxvn];

bool JUDGE(vertexNode *adjl[maxvn],int n,int j); /*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn]; bool visit[maxvm]; int top,k;

vertexNODE *p; bool yes;

for(k=1;k<=n;k++) visit[k]=false; top=1;

stack[top]=i; visit[i]=True; yes=false; do{ p=adjl[stack[top]];

while(!p=NULL&&visit[p->vertex]p=p->link); if(p==NULL)

top=top-1; /*p之后无邻接结点，退栈*/ else

{i=p->vertex; /*p指向的顶点未访问*/ if(i==j) yes=true; else

{ visit[i]=true; top=top+1; stack[top]=i; }

}while(top1=0&&!yes); return(yes); }

3、 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。 解：

①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/

void DFSM(Mgraph *G,int ) { int j;

printf(搗isit vertex:%c?G->vexs[i]); visitcd[i]=True;

for(j=0;j<=G->n;j++)

if(G->edges[i][j]==1&&!visit[j]) { print(揺dye:%dà %d\\n?i,j); DESM(G,j); } }

②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/

void DFSM(Mgraph *G,int k) { int i,j;

SETNULL(Q); /*置空队Q*/ Printf(‘%/“，G.vexs[k]);

Visited[k]=True; /*标志Vk+1已经访问过*/

ENQUEUE(Q,k); /* 已经访问过的顶点如队列*/ While(!EMPTY(Q)) /*队列非空时执行*/

{i=DEQUEUE(Q); /*队头元素序号出队列*/ for(j=0;j{print(揺dye:%dà %d\\n?i,j); /*访问过的边*/ print(?c\\n?G,vexs[j]); visited[j]=True;

ENQUEUE(Q,j); /*访问过的顶点如队*/ } } } 4、写一算法切连通分量的个数并输出各连通分量的顶点集。 解：

/*修改DFS函数，每当使visited[i]=true时打印printf（“%D”，i）；可输出各连通分量顶点集。*/ {int i; int m=0;

for(i=0;iprintf(揷omp end\\n?; }

printf(摴灿衜个连通分量?; }

5、 设图中各边上的权值均相等，是以邻接矩阵和邻接表为存储结构，分别写出算法：

（1） 求顶点 Vi到Vj(i<>j)顶点的最短路径； （2） 求源点Vi 到其余各顶点的最短路径。 要求输出路径上的所有顶点（提示：利用BFS遍历的思想） 解：

利用BFS的遍历思想，同时构造一棵树，使每个孩子结点均指向双亲，当搜索到目标结点时，则从目标回溯到根结点即可，具体算法如下 ： typedef struct node { int data; struct node *parent; }Tree;

void Path(ALGraph,*G,int i,int j) /*以邻接点存储*/

{ int k; /*求vi到vj的最短路径*/ CirQueue Q; /*将DataType改为 int */ EdyeNode P;

InitQueue(&Q) /*队列初始化*/ Visit[i]=TRVE; /*源点*/

S=(tree)mallo((sizeof(Tree)); 新建一个结点 s->data=i /*树根*/ s->patent=NULL;

EnQueue(&Q,i); /*入队列*/ While(!Queue Empty(&Q)) { k=DeQueue(&Q);

p=G->dajlist[k]->firstdeye; while(P)

{ if(! Visited[p->adjvex]) { visited[p->adjvex]=TRVE;

*S=(Tree*)mallo((sizeof(Tree)); /*新结点*/ s->data=p->adkvex; s->parent->data=k;

EnQueue(&Q,p->adjvex); } /*end if */

if(p->adjvex==j)bread; /*已搜索到j点*/ p-=p->next; } /*end if */

if(p->adjvex==j)break; /*已搜索到j点，结束搜索*/

} /*end if */

while(s!=NULL) /*此时打印出来的路径为反序*/ { printf(?d?G->adjlist[s->data]->vertex) s=s->parent; } （2）求源点到其余各顶点最短路径，则可调用上面算法。

Void PathALL(ALGraph *G.int i) {int j,

for(j=0;fn;j++) if(j!=i) path(G,i,j);

}

对于用邻接矩阵存储的图:

(1) 求顶点vi到顶点vj(i≠j)最短路径

算法思想，采用弗洛伊德算法，可表示为 A[K][i,j]=Min(A k-1[i,j],A k-1[i,k]+A k-1[k.j])(1<=i<=n,1<=j<=n)

其中k表示第k次迭代运算。A[0][i,j]=A[i,j]. #define MAXVEX 100

void floyd(a,c,n) /*c为已知邻接矩阵，a为待求矩阵，n为源点数*/ int a[MAXVEX][MAXVEX] c[MAXVEX][MAXVEX],n; {int i,j,k;

for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=c[i][j];

for(i=1;i<=n;i++) a[i][j]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if(a[i][k]+a[k][j]6、以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路（若存在）。 解：

算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。

Void dfscycle (ALGrph *G,int V4) {int i,j,top=0,V=V4,found=0,w; int Visitde[100],cycle[100]; EdgeNode *P;

i=1;

cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1; P=G[v]->firstedge;

While(p!=NULL!!top>0)&&!found) { while(p!=NULL&&!found)

if(p->adjvex==V4&&i<2)found=1; /*找到回路*/ else if(visited[p->adjvex]==0)p=p->next; /*找到下一个邻接点*/ elst

{w=p->adjvex; /*记下路径，继续搜索*/ visited[w]=1; i++;

cycle[i]=w; top++;

stack[top]=p;

p=G[w]->firstedge; }

if(!found&&top>0) /*沿原路径退回后，另选路径进行搜索*/ { p=attack[top]; top--;

p=p->next; i--; }

} /*end while*/ if(found)

{for(j=1;j<=i;j++)

printf(?d,?cycle[j]); /*打印回路的顶点序列*/ printf(?d,\\n?V); }

else printf(撋栌型ü鉜4的回路！\\n? }