文章
8
粉丝
42
获赞
14
访问
1.8k
(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。这样所有顶点可通过路径连通,形成一个强连通分量。
• 删除...
登录后发布评论
暂无评论,来抢沙发