习题六和上机答案.docx
- 文档编号:13285901
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:32
- 大小:54.40KB
习题六和上机答案.docx
《习题六和上机答案.docx》由会员分享,可在线阅读,更多相关《习题六和上机答案.docx(32页珍藏版)》请在冰点文库上搜索。
习题六和上机答案
习题六
6-1在下图所示的有向图中,试给出
(1)每一个顶点的入度和出度;
(2)邻接矩阵;
(3)邻接表;
(4)强连通分量。
题6.1
解:
顶点
1
2
3
4
5
6
入度
2
2
1
1
2
3
出度
1
2
2
3
1
2
邻接矩阵:
邻接表:
1
2
3
4
5
6
强连通分量:
1、6、2、4、5。
6-2在下图所示的有向图中:
(1)该图是强连通的吗?
若不是,则给出其强连通分量。
(2)给出图的邻接矩阵、邻接表、逆邻接表。
(3)给出每个顶点的度、入度和出度。
解:
(1)、是强连通图。
(2)、邻接矩阵:
邻接表:
1
2
3
4
逆邻接表:
1
2
3
4
(3)、
结点
1
2
3
4
入度
1
1
1
2
出度
2
1
1
1
度
3
2
2
3
6-3n个顶点的强连通图至少有多少条边,这样的有向图是什么形状?
解:
n-1条。
环行。
6-4对于下图所示的带权的有向图
(1)写出邻接矩阵;
(2)邻接表。
解:
(1)、邻接矩阵:
(2)、邻接表:
1
2
3
4
5
6
6-5分别写出用深度优先搜索法和广度优先搜索法遍历具有6个顶点的完全图的序列。
假设都以v1为出发点。
解:
深度优先遍历:
v1,v2,v3,v4,v5,v6
广度优先遍历:
v1,v2,v3,v4,v5,v6
6-6对下图所示的有向图,从顶点v1出发,分别画出其深度和广度生成树。
题6.6
解:
DFS:
BFS:
6-7实现在邻接表上删除一条边,删除一个结点的算法。
解:
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\n”);return;}/*删除结点p*/
q->next=p->next;
G→arcnum--;/*结点数减一*/
Free(p);
Free(q);
}
Voiddelete_drop(ALGraph*G,intA)/*A是要删除的结点下标*/
{
IntI;
Arcnode*p,*q;
For(i=A;i
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->adjvex==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!
=NULL)/*使相对应的数组每一次加一*/
{
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->vexnum;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].firstarc
G->vertices[i].firstarc=p;
}
G->vexnum=T->vexnum;G->arcnum=T->arcnum;
Free(p);
returnG;
}
6-10实现在邻接距阵存储结构上实现深度优先遍历和广度优先遍历。
解:
Intvisited[maxsize];
VoidDFSTraverse(MGraph*G)/*深度优先遍历*/
{
IntI,visited[maxsize];
For(i=1;i<=G->vexnum;i++)/*标记数组初始化*/
visited[i]=0;
for(i=1;i<=G->vexnum;i++)
if(!
visited[i])
DFS(G,i);/*对还没有访问的结点调用DFS*/
}
VoidDFS(MGraph*G,intv)
{
intI;
Visit[v]=1;/*标记已经调用*/
Printf(“--%d,”,G->vexs[i]);
For(i=1;i<=G->vexnum;i++)/*深度遍历*/
If(!
visited[i]&&G->arcs[v][i])
DFS(G,i);
}
VoidBFSTraverse(MGraph*G)/*广度遍历*/
{
LinkQueueQ;
Intvisited[maxsize],I,j,e;
For(i=1;i<=G->vexnum;i++)visited[i]=0;/*标记数组初始化*/
InitQueue(Q);
For(i=1;i<=G->vexnum;i++)
If(!
visited[i])
{visited[i]=1;Printf(“--%d,”,G->vexs[i]);
EnQueue(Q,i);
While(!
QueueEmtype(Q))
{
e=DeQueue(Q);
For(j=1;j<=G->vexnum;j++)
If(!
visited[j]&&G->arcs[e][j])
{visited[i]=1;Printf(“--%d,”,G->vexs[i]);EnQueue(Q,i);}
}
}
}
6-11实现在邻接表上,深度优先遍历和广度优先遍历的非递归算法。
解:
intsort(charx)/*查找data值对应的num*/
{
inti;
for(i=1;i<=n;i++)
if(a[i].data==x)return(a[i].num);
return(0);
}
intcompare(intx,intb[])/*查找有没有处理过*/
{
inti;
for(i=0;b[i]!
=NULL;i++)
if(x==b[i])return
(1);
return(0);
}
voidDFS(JDa[])/*深度优先遍历*/
{
inti,j,x,y,queue[N],stack[N];
charm;
JD*p;
printf("(DFS)inputthevertexyouwanttosearchfirst:
");getchar();
scanf("%c",&m);
y=sort(m);
if(y==0){printf("notexist!
");return;}
for(i=0;i { queue[i]=NULL; stack[i]=NULL; } i=0;j=-1; p=&a[y]; do { while(p! =NULL) { while(compare(p->num,queue)! =0&&p! =NULL) p=p->next; if(p! =NULL) { printf("%d%c",a[p->num].num,a[p->num].data); stack[++j]=queue[i++]=p->num; p=a[p->num].next; } } p=&a[stack[--j]]; }while(j>=0); printf("\n"); } voidBFS(JD*a)/*广度有限遍历*/ { JD*p; charm; inty,i=0,j=0; intqueue[N]={0}; printf("(BFS)inputthevertexyouwanttosearchfirst: ");getchar(); scanf("%c",&m); y=sort(m); if(y==0){printf("notexist! ");return;} do { p=&a[y]; while(p! =NULL) { if(compare(p->num,queue)==0) { queue[i++]=p->num; printf("%d%c",p->num,a[p->num].data); } p=p->next; } y=queue[++j]; }while(queue[j]! =0); } 6-12自选存储结构,实现判别无向图中任意给定的两个顶点之间是否存在一条长度为K的简单路径的算法。 解: intvisited[MAXSIZE]; intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 { if(i==j&&k==0)return1;//找到了一条路径,且长度符合要求 elseif(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(! visited[l]) if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一 }//for visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中 }//else return0;//没找到 }//exist_path_len 6-13有边集<1,2>,<2,3>,<5,2>,<5,6>,<6,4>,<3,4>,求此图的所有可能的拓扑序列。 若以此顺序输入建立图的邻接表,再在此存储储结构上执行toposort过程。 则得到的拓扑序列是哪一种? 解: 拓朴序列: 1->5->2->3->6->4;1->5->6->2->3->4;1->5->2->6->3->4; 5->1->2->3->6->4;5->1->6->2->3->4;5->1->2->6->3->4; 所得序列: 5->1->6->2->3->4; 6-14对于下列图中AOE_网,求出各活动可能的最早开始时间和可能的最早开始时间,并问: 整个工程的最短完成时间是多少? 哪些活动是关键活动? 是否有哪项活动提高速度后能导致整个工程提前完成? 题6.14 解: 活动 SA SB SD SF SG SI AC BC DC DE DJ FE 可能的最早开始时间 0 0 0 0 0 0 1 6 3 3 3 4 可能的最早开始时间 1 6 3 4 3 1 7 8 10 18 9 30 活动 FH GT GH IH HC CE HK KJ HJ JE ET JT 可能的最早开始时间 4 3 3 1 13 10 13 22 13 31 34 31 可能的最早开始时间 9 35 13 7 17 18 22 31 31 34 44 44 最短完成时间: 44 关键活动: SA、SB、SD、SF、SG、SI、AC、BC、DC、DJ、FH、GH、IH、HC、CE、HK、KJ、JE、ET。 提高速度后能导致整个工程提前完成的活动: SA、SB、SD、SF、SG、SI、AC、BC、DC、DJ、FH、GH、IH、HC、CE、HK、KJ、JE、ET。 6-15对题6.4所示的有向网,试利用Dijkstra算法求从源点1到其他各顶点的最短路径。 解: 顶点 最短路径 长度 1->2 1、3、2 19 1->3 1、3 15 1->4 1、2、6、4 29 1->5 1、3、2、5 29 1->6 1、3、6 25 6-16对下图所示的连通图,请分别用Prim和Kruskal算法构造其最小生成树。 题6-16 解: Struct{/*辅助数组*/ VertexTypeadjvex; VRTypelowcost; }node; VoidMiniSpanTree_Prim(MGraph*G,intu)/*u是默认开始的那个元素的下标*/ { nodeclosedge[maxsize]; inti,k,j; for(i=1;i<=G->vexnum;i++)/*辅助数组初始化*/ if(i! =k&&G->arcs[u][i]) {closedge[i].adjvex=i;closedge[i].lowcost=G->arcs[u][i].adj;} closedge[u].lowcost=0; For(i=1;i { K=10000; For(j=1;j<=G->vexnum;j++)/*取最小的一个权值的点的下标*/ If(closedge[j].lowcost&&closedge[j].lowcost K=j; printf(“(%d---%d)”,closedge[k].adjvex,G->vexs[k]); closedge[k].lowcost=0; for(j=1;j<=G->vexnum;j++)/*更新数组,使其最小*/ if(G->arcs[k][j].adj {closedge[i].adjvex=i;closedge[i].lowcost=G->arcs[u][i].adj;}} } VoidMiniSpanTree_Kruskal(MGarph*G)/*克鲁斯卡尔算法*/ { Inti,j,k,min,x,y,visited[maxsize],t=1; For(i=1;i<=G->vexnum;i++)/*辅助数组初始化*/ Visited[i]=0; For(i=1;i { min=10000; For(j=1;j<=G->vexnum;j++)/*找出小的权值,x,y记下边的两个结点*/ For(k=1;k<=G->vexnum;k++) if(G->arcs[j][k].adj {min=G->arcs[j][k].adj;x=j;y=k;} G->arcs[x][y].adj=0;/*标记已经找过的边*/ If(visited[x]||visited[y]) {printf(“(%d--%d--%d)”,x,min,y);i++;} } } 6-17设计算法,求有向图的深度和广度优先遍历的生成森林。 解: 为建立生成森林,需要先给出建立生成树的算法,然后再在遍历图的过程中,通过一次次地调用这个算法,以建立生成森林。 template : DFS_Tree(constintv,intvisited[],TreeNode //从图的顶点v出发,深度优先遍历图,建立以t(已在上层算法中建立)为根的生成树。 Visited[v]=1;intfirst=1;TreeNode intw=GetFirstNeighbor(v);//取第一个邻接顶点 while(w! =-1){//若邻接顶点存在 if(vosited[w]==0){//且该邻接结点未访问过 p=newTreeNode if(first==1)//若根*t还未链入任一子女 {t->setFirstChild(p);first=0;}//新结点*p成为根*t的第一个子女 elseq->setNextSibling(p);//否则新结点*p成为*q的下一个兄弟 q=p;//指针q总指示兄弟链最后一个结点 DFS_Tree(w,visited,q);//从*q向下建立子树 } w=GetNextNeighbor(v,w);//取顶点v排在邻接顶点w的下一个邻接顶点 } } 下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。 template : DFS_Forest(Tree //从图的顶点v出发,深度优先遍历图,建立以左子女-右兄弟链表表示的生成森林T。 T.root=NULL;intn=NumberOfVertices();//顶点个数 TreeNode int*visited=newint[n];//建立访问标记数组 for(intv=0;v for(v=0;v if(visited[v]==0){//若尚未访问过 p=newTreeNode if(T.root==NULL)T.root=p;//原来是空的生成森林,新结点成为根 elseq->setNextSibling(p);//否则新结点*p成为*q的下一个兄弟 q=p; DFS_Tree(v,visited,p);//建立以*p为根的生成树 } } 6-18设计算法,求有向图的强连通分量。 解: intvisited[MAXSIZE]; intfinished[MAXSIZE]; intcount;//count在第一次深度优先遍历中用于指示finished数组的填充位置 voidGet_SGraph(OLGraphG)//求十字链表结构储存的有向图G的强连通分量 { count=0; for(v=0;v for(v=0;v if(! visited[v])DFS1(G,v); for(v=0;v for(i=G.vexnum-1;i>=0;i--)//第二次逆向的深度优先遍历 { v=finished(i); if(! visited[v]) { printf("\n");//不同的强连通分量在不同的行输出 DFS2(G,v); } }//for }//Get_SGraph voidDFS1(OLGraphG,intv)//第一次深度优先遍历的算法 { visited[v]=1; for(p=G.xlist[v].firstout;p;p=p->tlink) { w=p->headvex; if(! visited[w])DFS1(G,w); }//for finished[++count]=v;//在第一次遍历中建立finished数组 }//DFS1 voidDFS2(OLGraphG,intv)//第二次逆向的深度优先遍历的算法 { visited[v]=1; printf("%d",v);//在第二次遍历中输出结点序号 for(p=G.xlist[v].firstin;p;p=p->hlink) { w=p->tailvex; if(! visited[w])DFS2(G,w); }//for }//DFS2 6-19用Dijstra和Floyed算法求题6.4所示有向网,源点为1的最短路径,写出执行算法过程中各步的状态。 解: Dijstra
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 上机 答案