文档库 最新最全的文档下载
当前位置:文档库 › 算法与数据结构第十章作业答案

算法与数据结构第十章作业答案

算法与数据结构第十章作业答案
算法与数据结构第十章作业答案

1.证明对有向图的顶点适当的编号,可使其邻接矩阵为下三角形且主对角线为全0的充要

条件是该图为无环图。

解答:证明:该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧,所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号,在邻接矩阵中,非零元素(A[i][j]=1)自然是落到下三角矩阵中;命题的必要条件是要使上三角为0,则不允许出现弧头顶点编号大于弧尾顶点编号的弧,否则,就必然存在环路。(对该类有向无环图顶点编号,应按顶点出度顺序编号。)

2.已知某图的邻接表如下图所示

(1).写出此邻接表对应的邻接矩阵;

(2).写出由v1开始的深度优先遍历的序列;

(3).写出由v1开始的深度优先的生成树;

(4).写出由v1开始的广度优先遍历的序列;

(5).写出由v1开始的广度优先的生成树;

(6).写出将无向图的邻接表转换成邻接矩阵的算法。

解答:

(1)略

(2)V1V2V5V3V4V6

(3)

(4)V1V2V3V4V5V6

(5)

(6)算法设计(数据结构定义可参考教材或相关资料)

void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//将图的邻接表表示转换为邻接矩阵表示。

{

for (i=1;i<=n;i++) //设图有n个顶点,邻接矩阵初始化。

for (j=1;j<=n;j++)

gm[i][j]=0;

for (i=1;i<=n;i++)

{

p=gl[i].firstarc; //取第一个邻接点。

while (p!=null)

{

gm[i][p->adjvex]=1;

p=p->next; //下一个邻接点

}

}

}//算法结束

3. 已知一图如下图所示:

(1).写出全部拓扑排序;

(2).以v1为源点,以v8为汇点,给出所有事件允许发生的最早时间和最晚时间,并给出关键路径;

(3).求V1结点到各点的最短距离。

解答:

(1) 所有可能的拓扑序列:V1 V2 V3 V4 V6 V5 V7 V8

V1 V3 V3 V4 V6 V5 V7 V8

关键路径有三条:

第一条: V1->V2->V4->V6->V8

第二条: V1->V2->V4->V6->V5->V7->V8

第三条: V1->V3->V5->V7->V8

(3)利用Dijkstra算法或floyd算法求解均可:(求解过程略,但作业需要写出详细过程)V1-V2: 2

V1->V3:3

V1->V4: 6

V1->V5: 13

V1->V6: 10

V1->V7: 16

V1-V8: 16

4. 已知某图的邻接矩阵为A,即若从i到j有边,则A[i,j]=1,否则A[i,j]=0。试编写一算法求矩阵A的传递包C:使得若从i到j有一条或多条路径,则C[i,j]=1,否则C[i,j]=0。

typedef int adjmatrix [ maxvtxnum ] [ maxvtxnum ];

void change( adjmatrix A, adjmatrix C, int n )

{

for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ )

C[ i ][ j ] = A[ i ][ j ]; // 初始化C = A

for ( k = 0; k < n; k++ ) // 改变的Floyd算法

for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ )

C[ i ][ j ] += C[ i ][ k ]+C[ k ][ j ];

for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ )

if ( C[ i ][ j ] ) C[ i ][ j ] = 1; // 把C中非0项置为1

}

算法思想:

(1)利用遍历算法,从每个顶点出发依次进行深度/广度优先遍历,遍历同时置C[i,j]的值。

(2)改写Floyd算法,如两个顶点执行完算法没有路径则置0,否则置1。

相关文档