文章

8

粉丝

42

获赞

14

访问

1.8k

头像
2025 年 9 月第 1 次 408 月考试卷 - 第42题回答
数据结构
发布于2025年9月25日 11:44
阅读数 59

(1)画出该带权有向图

根据十字链表的存储结构,顶点编号0~6对应A~G,弧结点的tailves(尾顶点)、headves(头顶点)和weight(权值)可确定有向边:

    •    顶点A(0)的出边:A→B(权1)、A→C(权2)

    •    顶点B(1)的出边:B→D(权5)、B→E(权7)

    •    顶点C(2)的出边:C→E(权10)、C→F(权8)

    •    顶点D(3)的出边:D→D(权0,自环)

    •    顶点E(4)的出边:E→B(权3)、E→F(权5)

    •    顶点F(5)的出边:F→G(权6)

    •    顶点G(6)无出边

据此画出有向图,顶点为A、B、C、D、E、F、G,带权有向边如上。

(2)强连通分量、添加/删除边分析

    •    强连通分量数量:3个。分别是{D}(自环,自身强连通)、{A,B,E}(A→B→E→B,A与B、E强连通)、{C,F,G}(C→F→G,无环,各自为强连通分量)。

    •    添加边使强连通分量数量为1:至少添加2条边。例如:G→A、D→C。这样所有顶点可通过路径连通,形成一个强连通分量。

    •    删除...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发