习题六和上机答案.doc

《习题六和上机答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题六6-1在下图所示的有向图中，试给出(1)每一个顶点的入度和出度；(2)邻接矩阵；(3)邻接表；(4)强连通分量。题6.1解：顶点123456入度221123出度122312邻接矩阵：邻接表：123456强连通分量：1、6、2、4、5。6-2在下图所示的有向图中：（1）该图是强连通的吗？若不是，则给出其强连通分量。（1）给出图的邻接矩阵、邻接表、逆邻接表。（2）给出每个顶点的度、入度和出度。解：（1）、是强连通图。（2）、邻接矩阵：邻接表：1234逆邻接表：1234（3）、结点1234入度1112出度2111度32236-3n个顶点的强连通图至少有多少条边，

2、这样的有向图是什么形状？解：n-1条。环行。6-4对于下图所示的带权的有向图(1)写出邻接矩阵；(2)邻接表。解：（1）、邻接矩阵：（2）、邻接表：1234566-5分别写出用深度优先搜索法和广度优先搜索法遍历具有6个顶点的完全图的序列。假设都以v1为出发点。解：深度优先遍历：v1，v2，v3，v4，v5，v6广度优先遍历：v1，v2，v3，v4，v5，v66-6对下图所示的有向图，从顶点v1出发，分别画出其深度和广度生成树。题6.6解：DFS：V21111VVVV611VVVBFS：V11111VVVVVVV6-7实现在邻接表上删除一条边，删除一个结点的算法。

3、解：Voiddelete_side(ALGraph*G,intA,intB)/*A,B为边的两个结点的下标*/{Arcnode*p,*q;P=q=G->vertices[A].firstarc;/*使p,q指向结点A的后续*/While(p->adjvex!=B&&p!=next){q=p;p=p->next;}/*寻找边，p指向B，q指向p的前一个*/If(p==NULL){printf(“inputerror”);return;}/*删除结点p*/q->next=p->next;Gàarcnum--;/*结点数减一*/Free(p);Free(

4、q);}Voiddelete_drop(ALGraph*G,intA)/*A是要删除的结点下标*/{IntI；Arcnode*p,*q;For(i=A;ivexnum;i++)/*删除结点A*/G->vertices[i]=G->vertices[i+1];G->vexnum--;For(i=1;i<=G->vexnum;i++)/*删除结点的前驱*/{P=q=G->vertices[i].firstarc;While(p!=NULL){If(p->adjvex>A)/*查看是否有结点的信息，有则删除*/p->adjvex--;elseif(p->adj

5、vex==A)/*删除结点*/q->next=p->next;Q=p;p=p->next;}{Free(p);Free(q);}6-8实现计算有向图中各顶点的入度的算法。设有向图用邻接表作为存储结构。解：VoidInDegree(ALGraph*G){IntI,count[maxsize];/*记录与下标相同的结点的入度数组*/Arcnode*p;For(i=1;i<=G->vexnum;i++)/*数组初始化*/Count[i]=0;For(i=1;i<=G->vexnum;i++){P=G->vertices[i].firstarc;While(p!=NUL

6、L)/*使相对应的数组每一次加一*/{Count[p->adjvex]++;p=p->next;}}For(i=1;i<=G->vexnum;i++)；/*输出入度*/Printf(“%sInDegree==%d”,G->vertices[i].data,count[i]);Free(p);}6-9实现将一个已知图的邻接矩阵存储形式转移成邻接表的存储形式。解：ALGraph*change(MGraph*T){ALGraph*G;IntI,j;Arcnode*p;G=(ALGraph)malloc(sizeof(ALGraph));For(i=1;i<=T->ve

7、xnum;i++)/*新图初始化*/{G->vertices[i]=T->vexs[i];G->vertices[i].firstarc=NULL;}For(i=1;i<=T->vexnum;i++)/*矩阵转换成邻接表*/For(j=1;j<=T->vexnum;i++)/*相连则放入邻接表*/If(T->arcs[i][j]){P=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=j;p->next=G->vertices[i].firstarcG->vertices[i].firstarc=p;}G->vexnum=T

8、->vexnum;G->