文章
7
粉丝
0
获赞
0
访问
3.8k
(1)画出该有权有向图
根据十字链表的存储结构,弧结点(EdgeNode)中的tailvex表示弧尾顶点编号,headvex表示弧头顶点编号,weight表示边的权值,hlink和tlink分别是顶点的出边链表和入边链表的指针。
• 顶点A(编号0)的出边:指向顶点1(B)、顶点2(C)、顶点3(D),权值等可从十字链表中对应弧结点获取。
• 顶点B(编号1)的出边:指向顶点3(D)。
• 顶点C(编号2)的出边:指向顶点4(E)。
• 顶点D(编号3)的出边:指向顶点4(E)、顶点5(F)。
• 顶点E(编号4)的出边:指向顶点5(F)。
• 顶点F(编号5)无出边(从十字链表中对应部分可判断)。
按照上述顶点间的有向边及权值关系,画出有权有向图,顶点间用带箭头的线段表示有向边,线段旁标注权值。
(2)强连通分量相关问题
• 强连通分量数量:通过分析各顶点之间的可达性,可得出该图的强连通分量有3个。
• 添加边使强连通分量数量变为1:至少需要添加2条边。例如,添加从F到A的边,再添加从E到B的边,使图中所有顶点能互相可达,形成一个强连通分量。
• 删除边使顶点数量大于1的强连通分量数量变为0:至少需要删除2条边。比如,删除A到B的边和A到C的边,破坏原本的连通结构,使得没有包含多个顶点的强连通分量。
(3)关键路径相关及十字链表优势
...
登录后发布评论
暂无评论,来抢沙发